[poj2367]Genealogical tree_拓扑排序

int v[100100];//入度
bool map[110][110]={false};//是否存在控制与被控制
int ans[110];//出队序列
int tot;
int n;void toposort()
{
	queue<int>q;
	for(int i=1;i<=n;i++)
	{
		if(!v[i]) q.push(i);
	}
	while(q.size())//其实toposort不同于spfa和bfs在于时间复杂度是O(n)的
	{
		int x=q.front(); q.pop(); ans[++tot]=x;//直接更新
		for(int i=1;i<=n;i++)
		{
			if(map[x][i]==1)
			{
				v[i]--;
				if(v[i]==0) q.push(i);
			}
		}
	}
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int v[100100];//入度
bool map[110][110]={false};//是否存在控制与被控制
int ans[110];//出队序列
int tot;
int n;void toposort()
{
	queue<int>q;
	for(int i=1;i<=n;i++)
	{
		if(!v[i]) q.push(i);
	}
	while(q.size())//其实toposort不同于spfa和bfs在于时间复杂度是O(n)的
	{
		int x=q.front(); q.pop(); ans[++tot]=x;//直接更新
		for(int i=1;i<=n;i++)
		{
			if(map[x][i]==1)
			{
				v[i]--;
				if(v[i]==0) q.push(i);
			}
		}
	}
}
void original()
{
	memset(map,false,sizeof map);
	memset(ans,0,sizeof ans);
	tot=0;
	memset(v,0,sizeof v);
}
int main()
{
	while(~scanf("%d",&n))
	{
		original();
		for(int a,i=1;i<=n;i++)
		{
			while(1)
			{
				scanf("%d",&a);
				if(!a) break;
				v[a]++;
				map[i][a]=1;
				map[a][i]=1;
			}
		}
		toposort();
		for(int i=1;i<=tot;i++)
		{
			printf("%d ",ans[i]);
		}
		puts("");
	}
	return 0;
}