Zerojudge c463
題敘
https://zerojudge.tw/ShowProblem?problemid=c463
給一棵樹，求其根與高度和
高度定義為節點到距離最近的葉節點距離
想法
找根可以利用根沒有父節點的特性，可以透過記錄每個點是否有父節點找到
找到根後就可以從根開始DFS，尋找各節點的高度並回傳，且葉節點高度為0
Code
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
39
40
41
42
43
44
45
46
47
48
49
|
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
int n,t;
long long ans=0;
vector<int> Next[100005];
bool par[100005];
long long dfs(int now,int last){
bool end=true;
long long h=0;
for(auto i: Next[now]){
if(i==last)
continue;
long long tmp = dfs(i,now);
h=max(h,tmp);
ans+=tmp;
end=false;
}
if(end)
return 0;
return h+1;
}
int main(){
IOS
cin>>n;
for(int i=1 ; i<=n ; i++){
cin>>t;
for(int j=0,tmp ; j<t ; j++){
cin>>tmp;
Next[i].push_back(tmp);
Next[tmp].push_back(i);
par[tmp] = true;
}
}
int root=0;
for(int i=1 ; i<=n ; i++){
if(!par[i]){
root=i;
cout<<root<<"\n";
break;
}
}
ans += dfs(root,-1);
cout<<ans<<"\n";
return 0;
}
|
複雜度
找根的時間複雜度為 $O(n)$
DFS會遍歷每個點，且每個點便利的時間複雜度為 $O(1)$，DFS時間複雜度為 $O(n)$
總時間複雜度 $O(n)$