裸拓扑排序。
拓扑排序
用一个队列实现,先把入度为0的点放入队列。然后考虑不断在图中删除队列中的点,每次删除一个点会产生一些新的入度为0的点。把这些点插入队列。
注意:有向无环图
g[] : g[i]表示从点i连出去的边
L[] :拓扑排序的结构
code:
#include <cstdio> #include <cstring> #include <queue> using namespace std; const int maxn = 100 + 5; vector<int> g[maxn]; int du[maxn], n, m, L[maxn]; bool toposort() { memset(du, 0, sizeof du ); for(int i=0; i<n; ++i) for(int j=0; j<g[i].size(); ++j) du[g[i][j]]++; int tot = 0; queue<int> Q; for(int i=0; i<n; ++i) if(!du[i]) Q.push(i); while(!Q.empty()) { int x = Q.front(); Q.pop(); L[tot++] = x+1; for(int j=0; j<g[x].size(); ++j) { int t = g[x][j]; du[t]--; if(!du[t]) Q.push(t); } } if(tot == n) return 1; else return 0; } int main() { int x, i; while(~scanf("%d",&n)) { for(int i=0; i<n; ++i) { g[i].clear(); while(scanf("%d",&x),x) { g[i].push_back(x-1); } } if(toposort()) { for(i=0; i<n-1; ++i) { printf("%d ",L[i]); } printf("%d\n",L[i]); } } return 0; }