拓扑排序的流程:首先遍历所有点,将入度为零的点加入队列,然后依次遍历出队的点的所有临边,并将临点的入度-1,若为0则加入队列。一趟流程走位,队列中的顺序就是拓扑排序的顺序
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N=110, M=N*N/2;
int e[M],h[N],w[M],ne[M],idx;
int q[N],din[N];
int tt,hh,n;
vector<int> vec;
void add(int a,int b,int c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void topsort(){
for(int i=1;i<=n;i++)
if(!din[i])
q[tt++]=i;
while(tt!=hh){
int t=q[hh++];
vec.push_back(t);
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
if(--din[j]==0)
q[tt++]=j;
}
}
}
int main(){
cin>>n;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++){
int w;
while(cin>>w,w){
add(i,w,1);
din[w]++;
}
}
topsort();
for(int i=0;i<n;i++) printf("%d ",q[i]);
return 0;
}