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 (≤104) 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

交了一发暴力,居然过了,关键就是这个求树的深度,这题的主要坑点在于,如果不是一颗树要输出那个信息,如果成环了但是只有一个连通块,要输出

Error: 1 components

所以注意判断逻辑

int dfs(int x)

{

    //de(x);

    vis[x]=1;

    int ma=0;

    for(int i=0;i<(int)G[x].size();i++){

        int v=G[x][i];

       if(vis[v])continue;

        ma=max(ma,dfs(G[x][i]));

    }

    return ma+1;

}

#include <iostream>

#include<bits/stdc++.h>

#define each(a,b,c) for(int a=b;a<=c;a++)

#define de(x) cout<<#x<<" "<<(x)<<endl

using namespace std;

const int maxn=1e4+5;

int father[maxn];   //  储存i的father父节点

void makeSet(int n) {

    for (int i = 1; i <=n; i++)

        father[i] = i;

}

int findRoot(int x) {   //  迭代找根节点

    int root = x; // 根节点

    while (root != father[root]) { // 寻找根节点

        root = father[root];

    }

    while (x != root) {

        int tmp = father[x];

        father[x] = root; // 根节点赋值

        x = tmp;

    }

    return root;

}

void Union(int x, int y) {  //  将x所在的集合和y所在的集合整合起来形成一个集合。

    int a, b;

    a = findRoot(x);

    b = findRoot(y);

    father[a] = b;  // y连在x的根节点上   或father[b] = a为x连在y的根节点上；

}

vector<int>G[maxn];

/*

5

1 2

1 3

1 4

2 5

*/

int maxx;

int depth[maxn];

int vis[maxn];

int dfs(int x)

{

    //de(x);

    vis[x]=1;

    int ma=0;

    for(int i=0;i<(int)G[x].size();i++){

        int v=G[x][i];

       if(vis[v])continue;

        ma=max(ma,dfs(G[x][i]));

    }

    return ma+1;

}

int main()

{

    int n;

    cin>>n;

    makeSet(n);

    int m=n-1;

    int a,b;

    int tree_flag=true;

    while(m--)

    {

        scanf("%d%d",&a,&b);

        if(findRoot(a)!=findRoot(b)){

            Union(a,b);

        G[a].push_back(b);

        G[b].push_back(a);

        }

        else tree_flag=false;

    }

    //int components=0;

    set<int>s;

    for(int i=1;i<=n;i++)

    {

        //de(i);

        //de(findRoot(i));

        s.insert(findRoot(i));

    }

    //de(s.size());

    if(tree_flag==false||s.size()!=1)

    {

        printf("Error: %d components\n",(int)s.size());

        return 0;

    }

    maxx=0;

    each(i,1,n)

    {

        memset(vis,0,sizeof(vis));

        //de(i);

        depth[i]=dfs(i);

    }

    each(i,1,n)

    {

        maxx=max(maxx,depth[i]);

    }

    each(i,1,n)

    {

        if(depth[i]==maxx)

        {

            cout<<i<<endl;

        }

    }

    return 0;

}