菜单 学习猿地 - LMONKEY

VIP

开通学习猿地VIP

尊享10项VIP特权 持续新增

知识通关挑战

打卡带练!告别无效练习

接私单赚外块

VIP优先接,累计金额超百万

学习猿地私房课免费学

大厂实战课仅对VIP开放

你的一对一导师

每月可免费咨询大牛30次

领取更多软件工程师实用特权

入驻
198
0

家谱树

原创
05/13 14:22
阅读数 20350
【问题描述】
    有个人的家族很大,辈分关系很混乱,请你帮整理一下这种关系。
    给出每个人的孩子的信息。
    输出一个序列,使得每个人的后辈都比那个人后列出。
【输入格式】
    第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
 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int rd[1000];
 5 int ch[1000];
 6 int stack[1000];
 7 int a[1000][1000];
 8 int main()
 9 {
10     int n;
11     cin>>n;
12     for(int i=1;i<=n;i++)
13      {
14          int x;
15           do{
16               cin>>x;
17               if(x!=0)
18                {
19                  ch[i]++;
20                  a[i][ch[i]]=x;
21                  rd[x]++;
22              }
23               }while(x!=0);
24     }
25      int top=0,sum=0;
26      for(int i=1;i<=n;i++)
27       {
28           if(rd[i]==0)
29            {
30                stack[++top]=i;
31            }
32       }
33      do
34      {
35         int i=stack[top];
36           cout<<i<<" ";
37           top--;
38           sum++;
39         for(int j=1;j<=ch[i];j++)
40         {
41            rd[a[i][j]]--;
42            if(rd[a[i][j]]==0)
43             {
44                 stack[++top]=a[i][j];
45              }
46          }
47       }while(sum!=n);
48       return 0;
49           
50       
51 }

 

发表评论

0/200
198 点赞
0 评论
收藏