很裸的一道拓扑排序题,发现都是用数组模拟队列写的,这里提供STL队列的写法以供参考。
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n;
struct node{
int to,next;
}e[N*N>>1];
int h[N],tot;
void add(int u,int v){e[tot].to=v, e[tot].next=h[u], h[u]=tot++;}
int din[N];
int ans[N],cnt;
void topsort(){
queue<int> q;
for(int i=1;i<=n;i++)
if(din[i]==0) q.push(i), ans[++cnt]=i;
while(q.size()){
int hd=q.front(); q.pop();
for(int i=h[hd];~i;i=e[i].next){
int go=e[i].to;
if(--din[go]==0){
q.push(go);
ans[++cnt]=go;
}
}
}
}
int main(){
memset(h,-1,sizeof h);
cin>>n;
for(int i=1;i<=n;i++){
int to;
while(cin>>to,to) {
add(i,to);
din[to]++;
}
}
topsort();
for(int i=1;i<=cnt;i++) cout<<ans[i]<<' ';
cout<<endl;
return 0;
}