[C++知识库]PTA甲级 1021 Deepest Root (C++)

A graph which is connected and acyclic can be considered a tree. The height of the tree depends on the selected root. Now you are supposed to find the root that results in a highest tree. Such a root is called the deepest root.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer $N(\le 10^4)$ which is the number of nodes, and hence the nodes are numbered from 1 to $N$. Then $N?1$ lines follow, each describes an edge by given the two adjacent nodes’ numbers.

Output Specification:

For each test case, print each of the deepest roots in a line. If such a root is not unique, print them in increasing order of their numbers. In case that the given graph is not a tree, print Error: K components where K is the number of connected components in the graph.

Sample Input 1:

5
1 2
1 3
1 4
2 5

Sample Output 1:

3
4
5

Sample Input 2:

5
1 3
1 4
2 5
3 4

Sample Output 2:

Error: 2 components

Caution:

求一个图中最深的根：先从一个结点dfs后保留最高高度拥有的结点们，然后从这些结点中的其中任意一个开始dfs得到最高高度的结点们，这两个结点集合的并集就是所求

来源：https://blog.csdn.net/liuchuo/article/details/52294178

Solution:

// Talk is cheap, show me the code
// Created by Misdirection 2021-09-03 21:11:45
// All rights reserved.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

int n;
int edges[10010][10010];
vector<int> ans;

int computeComponent(){
    int cnt = 0;
    int ans = 0;
    unordered_map<int, bool> visited;

    while(cnt < n){
        queue<int> q;
        int pos = 1;

        while(visited[pos] == true) pos++;

        visited[pos] = true;
        q.push(pos);
        while(!q.empty()){
            int size = q.size();
            cnt += size;

            for(int i = 0; i < size; ++i){
                int tmp = q.front();
                q.pop();

                for(int j = 1; j <= n; ++j){
                    if(edges[tmp][j] != 0 && !visited[j]){
                        q.push(j);
                        visited[j] = true;
                    }
                }
            }
        }

        ans++;
    }

    return ans;
}

void dfs(int idx){
    unordered_map<int, bool> visited;
    queue<int> q;

    visited[idx] = true;
    q.push(idx);
    int cnt = 0;

    while(cnt < n){
        int size = q.size();
        cnt += size;

        for(int i = 0; i < size; ++i){
            int tmp = q.front();
            q.pop();
            if(cnt == n){
                ans.push_back(tmp);
                continue;
            }

            for(int j = 1; j <= n; ++j){
                if(edges[tmp][j] != 0 && !visited[j]){
                    q.push(j);
                    visited[j] = true;
                }
            }
        }
    }

    return ;
}

int main(){
    
    scanf("%d", &n);

    for(int i = 0; i < n - 1; ++i){
        int a, b;
        scanf("%d %d", &a, &b);

        edges[a][b] = 1;
        edges[b][a] = 1;
    }

    int component = computeComponent();
    if(component > 1) printf("Error: %d components\n", component);
    else{
        dfs(1);
        if(ans[0] != 1) dfs(ans[0]);
        else if(ans.size() > 1) dfs(ans[1]);

        sort(ans.begin(), ans.end());
        for(int i = 0; i < ans.size(); ++i){
            if(i > 0 && ans[i] == ans[i - 1]) continue;
            printf("%d\n", ans[i]);
        }
    }


    return 0;
}