客天恺_hqkcq 发表于 2019-3-30 13:14:49

真心话大冒险

题目描述：
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 14:23:26

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

#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]++;
        }

        vector<int> leafnode;
        for (int i = 0; i <N; ++i)          //入度为零的即为叶节点
                if (indegree == 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) {
                        depth = d++;
                        if (i == N - 1) break;
                        i = tree;
                }
        }

        return depth;               //根节点的深度即为需要求的结果
}

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

客天恺_hqkcq 发表于 2019-3-30 15:09:53

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


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

Croper 发表于 2019-3-30 16:05:17

本帖最后由 Croper 于 2019-3-30 16:14 编辑

和c++一样，自己对注释来#include <stdio.h>

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

int main(){
        int N,i;
        scanf("%d",&N);
        if (N<=0) return;
       
        int tree;
        for (i=0;i<N;++i){
                scanf("%d",tree+i);
        }
       
        printf("\n%d",MaxDepth(tree,N));
}
页: [1]
查看完整版本: 真心话大冒险