C++ APCS實作題 2017/10 3 : 樹狀圖分析

樹狀圖的結構以及 DFS ( 深度優先搜索 ) ，另外用了 height[] 來儲存高度以降低複雜度。

#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<(b);i++)

long long n;
vector<long long> child[100010];
long long p[100010],height[100010];

void dfs(long long a){
    height[a]=0;
    for(long long v:child[a]){
        dfs(v);
        height[a]=max(height[a],height[v]+1);
    }
    return;
}

int main(){
    cin>>n;
    For(i,1,n+1){
        long long chN;cin>>chN;
        For(j,0,chN){
            long long ch;cin>>ch;
            child[i].push_back(ch);
            p[ch]=i;
        }
    }
    int root;
    for(root=1;root<=n;root++){
        if(p[root]==0) break;
    }
    dfs(root);
    long long total=0;
    for(int i=1;i<=n;i++) total+=height[i];
    cout<<root<<"\n";
    cout<<total<<"\n";
    return 0;
}