拓撲排序

對于一張有向無環(huán)圖，我們想在上面做動態(tài)規(guī)劃，但一個節(jié)點只有在所有父親都轉移到他后，才能向后轉移。P1983 [NOIP2013 普及組] 車站分級

對于一張有向無環(huán)圖，一個節(jié)點只有在所有父親都操作后，才能輪到它操作。P1954 [NOI2010] 航空管制

拓撲排序解決這類問題，每次選擇入度為 0 的節(jié)點刪除，并將他的出邊所連的節(jié)點入讀減 1 。

// 拓撲排序求最長路
// 車站分級中核心代碼
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define sf scanf
#define pf printf
#define mp make_pair
#define fo(i,x,y) for(register int i = x;i<=y;++i)
#define go(i,x,y) for(register int i = x;i>=y;--i)
using namespace std;
const int maxn = 1005;
const int maxm = 1005;
int cnt;
int in[maxn+maxm],dp[maxn+maxm];
vector<int> e[maxn+maxm];
queue<int> q;
void top_sort(){
	fo(i,1,cnt) dp[i] = -1;
	fo(i,1,cnt)
		if(in[i] == 0)
			dp[i] = 0,
			q.push(i);
	while(q.size()){
		int now = q.front();
		q.pop();
		for(auto v:e[now]){
			in[v]--;
			if(in[v] == 0){
				if(now > n)
					dp[v] = max(dp[v],dp[now]+1);
				else
					dp[v] = max(dp[v],dp[now]);
				q.push(v);
			}
		}
	}
}