[已解决]真心话大冒险

客天恺_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++一样，自己对注释来

#include <stdio.h>

int MaxDepth(int* tree,int N){
        int i,j;
        for (i=0;i<N;++i) tree[i]--;
        
        int indegree[N];
        memset(&indegree,0,sizeof(indegree));
        for (i=0;i<N-1;++i){
                indegree[tree[i]]++;
        }
        
        int leafnode[N];
        memset(&leafnode,-1,sizeof(leafnode));
        j=0;
        for (i=0;i<N;++i){
                if (indegree[i]==0){
                        leafnode[j++]=i;
                }
        }
        
        int depth[N];
        memset(&depth,-1,sizeof(depth));
        
        for (i=0;i<j;++i){
                int a=leafnode[i];
                int d=0;
                while (d>depth[a]){
                        depth[a]=d++;
                        if (a==N-1) break;
                        a=tree[a];
                }
        }
        
        return depth[N-1];
}

int main(){
        int N,i;
        scanf("%d",&N);
        if (N<=0) return;
        
        int tree[N];
        for (i=0;i<N;++i){
                scanf("%d",tree+i);
        }
        
        printf("\n%d",MaxDepth(tree,N));
}

跳转到最佳答案楼层

Croper

//此题目相当于求一个使用父指针表示法的树的最大深度
//根据题意，由于保证数据有解，树中不可能出现环，不需要特殊讨论

#include <vector>
#include <iostream>
using namespace std;

int Maxdepth(vector<int> tree) {
        for (int& i : tree) i--;   //-1是为了让下标与tree中的值更好匹配

        int N = tree.size();       //统计每个点的入度（当然忽略最后一个点的指向）    
        vector<int> indegree;
        indegree.resize(N,0);
        for (int i = 0; i <N-1; ++i) {
                indegree[tree[i]]++;
        }

        vector<int> leafnode;
        for (int i = 0; i <N; ++i)          //入度为零的即为叶节点
                if (indegree[i] == 0) leafnode.push_back(i);

        vector<int> depth;                  //这里的深度是反向表示的，且-1，即叶节点深度为0，根节点具有最大深度
        depth.resize(tree.size(), -1);        
        for (int i : leafnode) {           //从每个叶节点开始遍历，直到根节点或此节点深度大于需要覆写的深度；
                int d = 0;
                while (d > depth[i]) {
                        depth[i] = d++;
                        if (i == N - 1) break;
                        i = tree[i];
                }
        }

        return depth[N - 1];               //根节点的深度即为需要求的结果
}

int main() {
        int N;
        vector<int> tree;
        cin >> N;
        tree.resize(N);
        for (int i = 0; i < N; ++i) {
                cin >> tree[i];
        }
        
        cout << Maxdepth(tree);
        system("pause");
}

客天恺_hqkcq

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

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

Croper

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

#include <stdio.h>

int MaxDepth(int* tree,int N){
        int i,j;
        for (i=0;i<N;++i) tree[i]--;
        
        int indegree[N];
        memset(&indegree,0,sizeof(indegree));
        for (i=0;i<N-1;++i){
                indegree[tree[i]]++;
        }
        
        int leafnode[N];
        memset(&leafnode,-1,sizeof(leafnode));
        j=0;
        for (i=0;i<N;++i){
                if (indegree[i]==0){
                        leafnode[j++]=i;
                }
        }
        
        int depth[N];
        memset(&depth,-1,sizeof(depth));
        
        for (i=0;i<j;++i){
                int a=leafnode[i];
                int d=0;
                while (d>depth[a]){
                        depth[a]=d++;
                        if (a==N-1) break;
                        a=tree[a];
                }
        }
        
        return depth[N-1];
}

int main(){
        int N,i;
        scanf("%d",&N);
        if (N<=0) return;
        
        int tree[N];
        for (i=0;i<N;++i){
                scanf("%d",tree+i);
        }
        
        printf("\n%d",MaxDepth(tree,N));
}