d459 - 一棵小樹
題目描述
題目給定一棵以節點 1 為根的樹，要求輸出每個節點以下（包含自身）的節點數量。
解題思路
這題可以使用深度優先搜尋 (DFS) 來解決。從根節點 1 開始，遞迴地計算每個節點以下的節點數量。對於每個節點，我們遍歷它的所有子節點，遞迴地計算子節點以下的節點數量，然後將這些數量加總，再加上自身節點，即可得到該節點以下的節點總數。
複雜度分析
- 時間複雜度: O(N)，其中 N 是節點的數量。因為 DFS 會遍歷所有節點和邊。
- 空間複雜度: O(N)，主要來自於
t(鄰接表) 和ans陣列，以及 DFS 的遞迴呼叫堆疊。在最壞情況下，樹可能是一個鏈狀結構，遞迴深度為 N。
程式碼
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;
int n,x,y;
vector <int> t[20001];
int ans[20001];
int dfs(int it,int fa){
if(t[it].size()==0){
ans[it]=1;
return 1;
}
int tmp=1;
for(int i=0;i<t[it].size();++i){
if(t[it][i]!=fa)tmp+=dfs(t[it][i],it);
}
ans[it]=tmp;
return tmp;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n;
for(int i=1;i<n;++i){
cin >> x >> y;
t[y].push_back(x);
t[x].push_back(y);
}
dfs(1,1);
for(int i=1;i<=n;++i){
cout << setw(5) << right << i << '-' << setw(5) << right << ans[i] << "\n";
}
}