1021. Deepest Root

1021. Deepest Root (25)

时间限制

1500 ms

内存限制

32000 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

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

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <list>
#include <stdlib.h>
#include <string.h>
#define REP(i,j,k) for(int i = j ; i < k ; ++i)
#define MAXV 10010

using namespace std;


vector<int> adj_list[MAXV];
int Set[MAXV];
int Dist[MAXV];

int Find( int i )
{
    int n = i;

    while( Set[n] >= 0 )
    {
        n = Set[n];
    }

    while(i!=n)
    {
        int temp = Set[i];
        Set[i] = n;
        i = temp;
    }
    return n;

}


void Union( int i , int j )
{
    int a = Find(i);
    int b = Find(j);

    if( a != b )
    {
        if( Set[a] < Set[b] )
        {
            Set[a] = Set[a] + Set[b];
            Set[b] = a;
        }
        else
        {
            Set[b] = Set[a] + Set[b];
            Set[a] = b;
        }
    }
} 



int bfs( int start , int V )
{
    REP(i,1,V+1)
    {
        Dist[i] = -1;
    }
    Dist[start] = 0;
    queue<int> Q;
    Q.push(start);

    int max = 0;
    while(!Q.empty())
    {
        int now = Q.front();
        Q.pop();
        int dist = Dist[now];

        REP(i,0,adj_list[now].size())
        {
            if( Dist[adj_list[now][i]] == -1 )
            {
                Dist[adj_list[now][i]] = dist+1;
                Q.push(adj_list[now][i]);
            }
        }

        if( dist > max )
        {
            max = dist;
        }
    }

    return max;
}

int main()
{

    //freopen("test.txt","r" , stdin);
    int V;

    cin >> V;
    REP(i,1,V+1)
    {
        adj_list[i].clear();
        Set[i] = -1;
        Dist[i] = -1;
    }

    REP(i,0, V-1)
    {
        int s,t;

        scanf("%d %d" , &s ,&t );

        if( s != t )
        {
            adj_list[s].push_back(t);
            adj_list[t].push_back(s);
        }

        Union(s,t);
    }

    int n_comp = 0;

    REP(i,1,V+1)
    {
        if( Set[i] < 0 )
        {
            ++n_comp;
        }
    }

    if( n_comp > 1 )
    {
        printf("Error: %d components\n" , n_comp);
    }
    else
    {
        set<int> first;
        set<int> total;

        int max = bfs(1,V);


        REP(i,1,V+1)
        {
            if(Dist[i] == max)
            {
                first.insert(i);
                total.insert(i);
            }
        }


        max = bfs(*first.begin(), V);
        REP(i,1,V+1)
        {
            if(Dist[i] == max)
            {
                total.insert(i);
            }
        }


        for( set<int>::iterator it = total.begin() ; it != total.end() ; ++it )
        {
            cout << *it << endl;
        }

    }


    return 0;
}