1021. Deepest Root(25) [병렬 검색 + 심층 검색] -PAT(Advanced Level) Practise

제목 정보

1021. Deepest Root (25)
시간 제한 1500ms 메모리 제한 65536kB 코드 길이 제한 16000B
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 (<=10000) 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

문제풀이의 방향

및 검색+심층 검색

AC 코드

#include 
#include 
#include 
#include 
using namespace std;
int un[10005];
vector<bool> vis(10005);
vector<vector<int> > mp(10005);
int getfa(int a){
    return un[a] = (un[a] == a) ? a : getfa(un[a]);
}
void unin(int a, int b){
    un[getfa(a)] = un[getfa(b)];
}

int high(int id){
    int h = 0;
    vis[id] = true;
    for (int i = 0; i < mp[id].size(); ++i){
        if (!vis[mp[id][i]]){
            vis[mp[id][i]] = true;
            h = max(h, high(mp[id][i]));
        }
    }
    return h + 1;
}
int main()
{
    int n, a, b;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i){
        un[i] = i;
    }
    for (int i = 1; i < n; ++i){
        scanf("%d%d", &a, &b);
        mp[a].push_back(b);
        mp[b].push_back(a);
        unin(a, b);
    }

    set<int> st;
    for (int i = 1; i <= n; ++i){
        st.insert(getfa(i));
    }
    if (st.size() == 1){
        vector<int> v;
        int mn = -1;
        for (int i = 1; i <= n; ++i){
            vis.assign(n+1, false);
            int h = high(i);
            if (h > mn){
                v.clear();
                mn = h;
                v.push_back(i);
            }else if (h == mn){
                v.push_back(i);
            }
        }
        for (int i = 0; i < v.size(); ++i){
            printf("%d
", v[i]);
        }
    }else{
        printf("Error: %d components
", st.size());
    }
    return 0;
}