【GPLT】 2018年天梯赛全国总决赛 L2-2 小字辈（c++）

题目：

这一题并不是很难，属于常规的图论遍历题，这里我是用的bfs（dfs应该也可以，但明显bfs简单一些）。

本人写的时候写了很多没必要头文件，自己可以根据内容删去，必要的我会写上注释

如有错误，请指正。

知识点：bfs，邻接表，队列

代码如下（本人喜欢多换行，所以可能看起来比较长，但其实内容不多）：

 1 #include//必要
 2 #include//必要
 3 #include
 4 #include//必要，也可以自己写个模拟队列
 5 #include
 6 #include<string>//必要
 7 #include
 8 using namespace std;
 9 const int N=1e7+10;
10 int e[N],ne[N],idx,h[N];//邻接表用
11 int n;
12 int d[N],b[N];
13 void add(int a,int b)
14 {
15     e[idx]=b,ne[idx]=h[a],h[a]=idx++;
16 }
17 void bfs(int root)
18 {
19     queue<int> q;//建个队列
20     q.push(root);//
21     while(q.size())
22     {
23         int t=q.front();//取出点
24         q.pop();
25         for(int i=h[t];i!=-1;i=ne[i])//存储的是下标
26         {
27             int j=e[i];
28             if(d[j]==0)//如果没有遍历过
29             {
30                 d[j]=d[t]+1;//辈分加1
31                 q.push(j);//放进队列
32             }
33         }
34     }
35 }
36 int main()
37 {
38     cin>>n;
39     int x;
40     int root;
41     memset(h,-1,sizeof h);//初始化表头
42     for(int i=1;i<=n;i++)
43     {
44         cin>>x;
45         if(x!=-1) add(x,i);//建立练习，注意是x，i不是i，x。因为x是父亲，应该是父亲走向儿子
46         else
47         {
48             root=i;//找到老祖宗（根结点）
49             d[root]=1;
50         }
51     }
52     bfs(root);
53     int ma=0;
54     for(int i=1;i<=n;i++)
55     {
56         ma=max(ma,d[i]);//寻找(数字)最大的辈分
57     }
58     cout<endl;
59     int cnt=0;//下面的只是为了输出没什么实际内容，就是单纯的把最小辈分人的编号放在另外一个数组
60     for(int i=1;i<=n;i++)
61     {
62         if(d[i]==ma)
63         {
64             b[cnt++]=i;
65         }
66     }
67     for(int i=0;i)
68     {
69         if(i!=cnt-1) cout<" ";
70         else cout<endl;//输出要求
71     }
72     return 0;
73 }

GPLT

【GPLT】 2018年天梯赛全国总决赛 L2-2 小字辈（c++）

相关

标签