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

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

##### 题目 #####

[题目链接][Link 1]

##### 思路 #####

**题目大意**：给一张图，这个图有点特殊，没有环且边数等于节点数-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;
    }

[Link 1]: https://pintia.cn/problem-sets/994805342720868352/problems/994805482919673856