图论之拓扑排序 poj 2367 Genealogical tree

题目链接 http://poj.org/problem?id=2367

题意就是给定一系列关系，按这些关系拓扑排序。

#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=200;
int ans;
int n;
int in[maxn];        //记录入度
int num[maxn];       //记录答案
vector<int>E[maxn];  //记录边
void topo_sort()     //拓扑排序
{queue<int>q;for(int i=1; i<=n; i++)if(!in[i]){q.push(i);in[i]=-1;}while(!q.empty()){int now=q.front();num[ans]=now;ans++;q.pop();for(int i=0; i<E[now].size(); i++)if(in[E[now][i]]>0)in[E[now][i]]--;for(int i=1; i<=n; i++)if(!in[i]){in[i]=-1;q.push(i);}}return ;
}
int main()
{while(~scanf("%d",&n)){memset(num,0,sizeof(num));memset(in,0,sizeof(in));for(int i=0;i<maxn;i++)E[i].clear();ans=0;for(int i=1; i<=n; i++){int x;while(scanf("%d",&x)){if(!x)break;E[i].push_back(x);in[x]++;}sort(E[i].begin(),E[i].end());}topo_sort();printf("%d",num[0]);for(int i=1; i<n; i++)printf(" %d",num[i]);puts("");}return 0;
}