PAT甲级1021 Deepest Root ：[C++题解]树的最大深度、并查集、dfs求树的深度

本文主要是介绍PAT甲级1021 Deepest Root ：[C++题解]树的最大深度、并查集、dfs求树的深度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 题目分析
- 题目链接

题目分析

在这里插入图片描述
分析：
考察知识点：并查集、dfs、树的深度

给定n个结点，n-1条边，只要能保证只有1个连通分量，就是一棵树。否则的话就不是树，它是不连通的。

用并查集来看是否只有一个连通块，对于n个结点，n-1条边，如果不只有一个连通块，那么就是存在环。

判环自然想到并查集。关于并查集的知识点和板子，请参阅笔者的另一篇文章并查集板子:acwing836. 合并集合

无环则是树，有环则不是树。

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

这题时间限制是2m，对C++来说，1m = $\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;}
}