旅行计划（拓扑排序）

传送门

第一道拓扑排序题目，应该算是模板题吧，先放在这。

#include <iostream>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

const int N = 2000010;
struct Edge{
	int u, v, w, next;
}edge[N];
int n, m, tot, head[N], indegree[N], cnt[N];

void add(int a, int b){
	edge[tot].v = b;
	edge[tot].next = head[a];
	head[a] = tot ++;
}
queue<int> q;

void topsort(){
	for(int i = 1; i <= n; i ++){
		if(indegree[i] == 0)
			q.push(i);
		cnt[i] ++;
	}
		
	while(q.size()){
		int u = q.front();
		q.pop();
		for(int i = head[u]; i != -1; i = edge[i].next){
			int to = edge[i].v;
			indegree[to] --;
			if(indegree[to] == 0)
				q.push(to);
			cnt[to] = max(cnt[to], cnt[u] + 1);
		}
	}
}
int main(){
	memset(head, -1, sizeof head);
	cin >> n >> m;
	for(int i = 1; i <= m; i ++){
		int a, b;
		cin >> a >> b;
		add(a, b);
		indegree[b] ++;
	}
	topsort();
	for(int i = 1; i <= n; i ++)
		cout << cnt[i] << endl;
	return 0;
}