PAT（甲级）1021 Deepest Root (25point(s))-蒲公英云

PAT（甲级）1021 Deepest Root (25point(s))

桃扇骨 2024-05-08 06:01 189阅读 0赞

题目

题目链接

思路

题目大意：给一张图，这个图有点特殊，没有环且边数等于节点数-1，即是一棵树；每个节点都可能是根节点，要求是输出那些作为根节点时树的深度最大的节点；
首先要判断是不是联通的，可以用并查集做，可以用图的DFS遍历做；
然后如果是联通的话，需要找到那些作为根节点时树的深度最大的节点；这里有一个方法，那就是DFS两次，第一次从任意一个节点出发，假设从1号节点出发，DFS时会遍历所有点，并得到每个点的深度，我们把那些深度最大的点记录下来，存放在temp中；第二次从temp 数组的任意一个元素出发，再次记录下深度最大的点，这两个集合取并集，就是想要的答案；（证明太难了，我选择记住）
注意：这其实是一个树的遍历问题，但是树是用邻接表存的，所以DFS时要记录父节点，避免走回头路；

代码

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
const int maxn = 1e4 + 10;
vector<int> graph[maxn];//图
int n;//节点个数
int father[maxn];//father数组和联通分量
int isRoot[maxn];//存放以他为根节点 ，这一联通分枝有几个元素
set<int> temp, ans;
int maxDepth = 0;//最大的深度
int findFa(int a){
     int b = a, temp;
     //寻找父节点
     while(father[a] != a) a = father[a];
     //压缩路径
     while(father[b] != b){
          temp = father[b];
          father[b] = a;
          b = temp;
     }
     return a;
}
void myUnion(int a, int b){
     int faA = findFa(a), faB = findFa(b);
     if(faA != faB){
          father[faB] = faA;//B向A合并
          //更新isRoot数组
          isRoot[faA] += isRoot[faB];
          isRoot[faB] = 0;
     }
}
void DFS(int root, int depth, int pre){
     //如果当前这个节点的深度大于全局的，需要把之前的temp数组清空
     if(depth > maxDepth){
          temp.clear();
          temp.insert(root);
          maxDepth = depth;
     }
     else if(depth == maxDepth) temp.insert(root);//等于全局，直接加进去
     for(int i = 0; i < graph[root].size(); i ++){
          //用遍历图的方式遍历树，需要防止走回头路
          if(graph[root][i] != pre){
               DFS(graph[root][i], depth + 1, root);
          }
     }
}
int main()
{
     //初始化father数组
     for(int i = 0; i < maxn; i ++) father[i] = i;
     memset(isRoot, 1, sizeof(isRoot));
     scanf("%d", &n);
     //读入边
     for(int i = 1; i < n; i ++){
          int u, v;
          scanf("%d%d", &u, &v);
          myUnion(u, v);
          graph[u].push_back(v);
          graph[v].push_back(u);
     }
     //计算联通分量
     int num = 0;
     for(int i = 1; i <= n; i ++){
          if(isRoot[i] != 0) num ++;
     }
     if(num != 1) printf("Error: %d components\n", num);
     else{
          //计算从第一个点出发能到达的最远的点，将最远的点存放在temp中
          DFS(1, 1, -1);
          ans = temp;
          maxDepth = 0;//注意把最大深度还原到零
          DFS(*temp.begin(), 1, -1);
          //将第二次的节点与第一次的节点合并，二者取并集是最后的答案
          for(auto it = temp.begin(); it != temp.end(); it ++){
               ans.insert(*it);
          }
          //输出结果
          for(auto it = ans.begin(); it != ans.end(); it ++){
               printf("%d\n", *it);
          }
     }
     system("pause");
     return 0;
}