拓扑排序是什么意思？

拓扑排序 对于一张有向无环图，我们想在上面做动态规划，但一个节点只有在所有父亲都转移到他后，才能向后转移。P1983 [NOIP2013 普及组] 车站分级 对于一张有向无环图，一个节点只有在所有父亲都操作后，才能轮到它操作。P1954 [NOI2010] 航空管制 拓扑排序解决这类问题，每次选择入度为 0 的节点删除，并将他的出边所连的节点入读减 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); } } } }