樹狀圖的結構以及 DFS ( 深度優先搜索 ) ，另外用了 height[] 來儲存高度以降低複雜度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #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;
}
|