大意:火星人的种族关系比较混乱。宗族管理委员会进行开会发言等活动时,又想遵守先长辈,后晚辈的顺序。 于是有下面的问题:
编写一个程序对给定的人员,决定一个先后顺序, 这个顺序必须遵守先长辈,后晚辈的原则。
input:
首行为N, 1 <= N <= 100 ,N为总人数。根据百年传统,给人员用自然数编号为1至N。以下的N行,第I行为第I个人的子孙列表,子孙的顺序是任意的,用空格隔开,且以0为结束。子孙列表可以是空的。
output:
在一行内输出发言的顺序。 如有多个顺序满足条件,则输出任一个。至少会有一个满足的顺序的。
input:
5
0
4 5 1 0
1 0
5 3 0
3 0
output:
2 4 5 3 1【参考程序】:
#include<iostream>//简单的拓扑排序
using namespace std;
int into[101],map[101][101];
int ans[101];
int n;
int main()
{
scanf("%d",&n);
memset(map,0,sizeof(map));
memset(into,0,sizeof(into));
int x;
for (int i=1;i<=n;i++)
{
scanf("%d",&x);
while (x)
{
map[i][x]=1;
into[x]++;
scanf("%d",&x);
}
}
for (int i=1;i<=n;i++)
{
int k=0;
for (int j=1;j<=n;j++)
if (into[j]==0)
{
k=j;
break;
}
if (k==0) break;
into[k]=256;
ans[i]=k;
for (int j=1;j<=n;j++)
if (map[k][j])
into[j]--;
}
for (int i=1;i<=n-1;i++) printf("%d ",ans[i]);
printf("%d\n",ans[n]);
return 0;
}