洛谷 P1137. 旅行计划

问题描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 100010, M = 2 * N;
int n, m;
int head[N], e[M], ne[M], idx;
int d[N], ans[N];

void add(int x, int y) {
	e[idx] = y;
	ne[idx] = head[x];
	head[x] = idx++;
}

int main() {
	memset(head, -1, sizeof head);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y;
		add(x, y);
		d[y]++;
	}

	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (!d[i]) {
			q.push(i);
			ans[i] = 1;
		}
	}

	while (q.size()) {
		int x = q.front();
		q.pop();

		for (int i = head[x]; i != -1; i = ne[i]) {
			int y = e[i];
			d[y]--;
			if (!d[y]) {
				q.push(y);
				ans[y] = ans[x] + 1;
			}
		}
	}

	for (int i = 1; i <= n; i++) cout << ans[i] << endl;

	return 0;
}