[已解决]真心话大冒险

客天恺_hqkcq

题目描述：
Leslie非常喜欢真心话大冒险的游戏。这一次游戏的规则有些不同。每个人都有自己的真心话，一开始每个人也都只知道自己的真心话。
每一轮每个人都告诉指定的一个人他所知道的所有真心话，那么Leslie想知道，多少轮后他能知道所有人的真心话呢？题目保证数据有解。
输入：
第一行一个数n，表示一共有n个人，编号为1~n, Leslie为第n个人。n<=1000
第二行有n个数，第i个数表示第i个人要传递真心话的对象。
输出：
输出一个数x，表示第x轮后Leslie知道了所有的真心话。

输入样例：
4
2 4 2 1
输出样例：
2

最佳答案

月排行榜 / 总排行榜

Croper

2019-3-30 16:05:17

和c++一样，自己对注释来

1. #include <stdio.h>
   
2. 
   
3. int MaxDepth(int* tree,int N){
   
4.         int i,j;
   
5.         for (i=0;i<N;++i) tree[i]--;
   
6.        
   
7.         int indegree[N];
   
8.         memset(&indegree,0,sizeof(indegree));
   
9.         for (i=0;i<N-1;++i){
   
10.                 indegree[tree[i]]++;
    
11.         }
    
12.        
    
13.         int leafnode[N];
    
14.         memset(&leafnode,-1,sizeof(leafnode));
    
15.         j=0;
    
16.         for (i=0;i<N;++i){
    
17.                 if (indegree[i]==0){
    
18.                         leafnode[j++]=i;
    
19.                 }
    
20.         }
    
21.        
    
22.         int depth[N];
    
23.         memset(&depth,-1,sizeof(depth));
    
24.        
    
25.         for (i=0;i<j;++i){
    
26.                 int a=leafnode[i];
    
27.                 int d=0;
    
28.                 while (d>depth[a]){
    
29.                         depth[a]=d++;
    
30.                         if (a==N-1) break;
    
31.                         a=tree[a];
    
32.                 }
    
33.         }
    
34.        
    
35.         return depth[N-1];
    
36. }
    
37. 
    
38. int main(){
    
39.         int N,i;
    
40.         scanf("%d",&N);
    
41.         if (N<=0) return;
    
42.        
    
43.         int tree[N];
    
44.         for (i=0;i<N;++i){
    
45.                 scanf("%d",tree+i);
    
46.         }
    
47.        
    
48.         printf("\n%d",MaxDepth(tree,N));
    
49. }

复制代码

跳转到最佳答案楼层

Croper

1. //此题目相当于求一个使用父指针表示法的树的最大深度
   
2. //根据题意，由于保证数据有解，树中不可能出现环，不需要特殊讨论
   
3. 
   
4. #include <vector>
   
5. #include <iostream>
   
6. using namespace std;
   
7. 
   
8. int Maxdepth(vector<int> tree) {
   
9.         for (int& i : tree) i--;   //-1是为了让下标与tree中的值更好匹配
   
10. 
    
11.         int N = tree.size();       //统计每个点的入度（当然忽略最后一个点的指向）   
    
12.         vector<int> indegree;
    
13.         indegree.resize(N,0);
    
14.         for (int i = 0; i <N-1; ++i) {
    
15.                 indegree[tree[i]]++;
    
16.         }
    
17. 
    
18.         vector<int> leafnode;
    
19.         for (int i = 0; i <N; ++i)          //入度为零的即为叶节点
    
20.                 if (indegree[i] == 0) leafnode.push_back(i);
    
21. 
    
22.         vector<int> depth;                  //这里的深度是反向表示的，且-1，即叶节点深度为0，根节点具有最大深度
    
23.         depth.resize(tree.size(), -1);        
    
24.         for (int i : leafnode) {           //从每个叶节点开始遍历，直到根节点或此节点深度大于需要覆写的深度；
    
25.                 int d = 0;
    
26.                 while (d > depth[i]) {
    
27.                         depth[i] = d++;
    
28.                         if (i == N - 1) break;
    
29.                         i = tree[i];
    
30.                 }
    
31.         }
    
32. 
    
33.         return depth[N - 1];               //根节点的深度即为需要求的结果
    
34. }
    
35. 
    
36. int main() {
    
37.         int N;
    
38.         vector<int> tree;
    
39.         cin >> N;
    
40.         tree.resize(N);
    
41.         for (int i = 0; i < N; ++i) {
    
42.                 cin >> tree[i];
    
43.         }
    
44.        
    
45.         cout << Maxdepth(tree);
    
46.         system("pause");
    
47. }

复制代码

客天恺_hqkcq

Croper 发表于 2019-3-30 14:23

能用C语言吗  不懂c++  谢谢啦

Croper

和c++一样，自己对注释来

1. #include <stdio.h>
   
2. 
   
3. int MaxDepth(int* tree,int N){
   
4.         int i,j;
   
5.         for (i=0;i<N;++i) tree[i]--;
   
6.        
   
7.         int indegree[N];
   
8.         memset(&indegree,0,sizeof(indegree));
   
9.         for (i=0;i<N-1;++i){
   
10.                 indegree[tree[i]]++;
    
11.         }
    
12.        
    
13.         int leafnode[N];
    
14.         memset(&leafnode,-1,sizeof(leafnode));
    
15.         j=0;
    
16.         for (i=0;i<N;++i){
    
17.                 if (indegree[i]==0){
    
18.                         leafnode[j++]=i;
    
19.                 }
    
20.         }
    
21.        
    
22.         int depth[N];
    
23.         memset(&depth,-1,sizeof(depth));
    
24.        
    
25.         for (i=0;i<j;++i){
    
26.                 int a=leafnode[i];
    
27.                 int d=0;
    
28.                 while (d>depth[a]){
    
29.                         depth[a]=d++;
    
30.                         if (a==N-1) break;
    
31.                         a=tree[a];
    
32.                 }
    
33.         }
    
34.        
    
35.         return depth[N-1];
    
36. }
    
37. 
    
38. int main(){
    
39.         int N,i;
    
40.         scanf("%d",&N);
    
41.         if (N<=0) return;
    
42.        
    
43.         int tree[N];
    
44.         for (i=0;i<N;++i){
    
45.                 scanf("%d",tree+i);
    
46.         }
    
47.        
    
48.         printf("\n%d",MaxDepth(tree,N));
    
49. }

复制代码