游客 注册 | 登录
中文 | En

3693 - 家谱树

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。
    给出每个人的孩子的信息。
    输出一个序列，使得每个人的后辈都比那个人后列出。

题目输入

   第1行一个整数N（1<=N<=100），表示家族的人数。
    接下来N行，第I行描述第I个人的儿子。
    每行最后是0表示描述完毕。

题目输出

输出一个序列，使得每个人的后辈都比那个人后列出。
    如果有多解输出任意一解。

输入/输出样例

输入格式

 5
 0
 4 5 1 0
 1 0
 5 3 0
 3 0

输出格式

2 4 5 3 1

C++解答

#include<iostream>
#include<cstring>
using namespace std;
int graph[100][100]; //邻接阵
int indegree[100]; //记录顶点的入度
int n; //n为顶点个数
int main()
{
    memset(graph,0,sizeof(graph));
	memset(indegree,0,sizeof(indegree));
	cin>>n;
	int e;
	for(int i=1;i<=n;i++)
	{
		while(cin>>e)
		{
			if(e!=0)
			{
		        graph[i][e]=1;
		        indegree[e]++;
		        continue;
			}
			else
				break;
		}
	}
	for(int i=1;i<=n;++i) //遍历n次每次找出一个顶点
    {
		for(int j=1;j<=n;++j) //遍历所有的结点
		{
			if(indegree[j]==0)
			{
				indegree[j]--; //该顶点的入度为-1，防止该顶点被在此遍历到，相当于删除。
				cout<<j<<' ';
				for(int k=1;k<=n;++k)
				{
					if(graph[j][k])
						indegree[k]--; //与该顶点关联的顶点的入度递减
				}
				break;
			}
		}
	}
	//while (1);
}
请先登陆