文章目錄

• • 題目分析
  • 題目鏈接

題目分析

分析：
考察知識點：并查集、dfs、樹的深度

給定n個結點，n-1條邊，只要能保證只有1個連通分量，就是一棵樹。否則的話就不是樹，它是不連通的。

用并查集來看是否只有一個連通塊，對于n個結點，n-1條邊，如果不只有一個連通塊，那么就是存在環。

判環自然想到并查集。關于并查集的知識點和板子，請參閱筆者的另一篇文章并查集板子:acwing836. 合并集合

無環則是樹，有環則不是樹。

然后怎么求樹的最大深度呢？

這題時間限制是2m，對C++來說，1m = $1\times 10^8$次運算，2m =$2\times 10^8$次運算. 數據范圍是1e4，對于判斷樹的最大深度，我們可以暴力枚舉所有的結點當作根結點，用bfs或者dfs求樹的深度是O(n)的復雜度。 所以 暴力的時間 是O(n^2)，1e4 * 1e4 =1e8可以過。

ac代碼

#include<bits/stdc++.h> using namespace std;const int N =10010,M =2*N; //N表示結點數量，M表示邊的數量，無向邊，存兩個有向邊int n; //鄰接表 int e[N],ne[N],h[N],idx; //并查集 int p[N];//并查集找根結點 int find(int x) {if(p[x]!=x) p[x] =find(p[x]);return p[x]; }//鄰接表加邊 void add(int a, int b){e[idx]=b, ne[idx] =h[a], h[a] =idx++; }//當前這個點到葉子結點的最大深度 // u是當前結點， father表示u的父節點，當沒有的時候記為-1 int dfs(int u ,int father){int depth =0;//遍歷當前點的所有子結點for(int i =h[u]; i!= -1; i=ne[i]){int j = e[i];if(j == father) continue;depth =max(depth, dfs(j ,u)+1);}return depth; }int main(){cin>>n;int k =n; //連通塊的數量，初始化為結點數memset(h ,-1 ,sizeof h);//并查集初始化，開始時每個結點是獨立的集合，此時的特點是父節點==自己 p[x] ==xfor(int i=1;i<=n; i++) p[i] =i;for(int i=0;i<n-1;i ++){int a, b;cin>> a>> b; //讀入邊if(find(a) != find(b)){ //a和b不在一個集合中k--;p[find(a)] =find(b); //a和b連在一起}add(a,b),add(b,a); //add是添加有向邊，此題是無向邊，所有添加兩邊}//不是一棵樹if(k>1) printf("Error: %d components",k);else{vector<int> nodes; //存儲所有可能的結果int max_depth =-1; for(int i=1;i<= n; i++){//遍歷每個結點int depth = dfs(i,-1); //以該結點為根，求該節點到葉子結點的最大深度if(depth > max_depth){max_depth =depth;nodes.clear(); //比以前的深度大，以前的便無用了，清空。nodes.push_back(i); //當前點加進來}else if(depth == max_depth) nodes.push_back(i);}for(auto v:nodes) cout<<v<<endl;} }

題目鏈接

PAT甲級1021 Deepest Root

總結

以上是生活随笔為你收集整理的PAT甲级1021 Deepest Root ：[C++题解]树的最大深度、并查集、dfs求树的深度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。