1021. Deepest Root (25)

女爷i 2022-05-31 09:55 151阅读 0赞

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

--------------------

题目大意：

一个连通的无环图可以看做一棵树。树的高度取决于所选的跟。现在你的任务是找到使树最高的根。这个根就叫做最深根。  
输入规格：  
每个输入文件包含一个测试用例。对于每一种情况，第一行包含一个正整数N(<=10000),即节点数，因此节点的编号是从0到N-1.然后接着是N-1行，然后每一行通过两个相邻节点的数字来描述一个边。  
输出规格：  
对于每个测试用例，在一行中打印出最深的根。如果最深的根不是唯一的，按递增的顺序打印出他们的编号。如果给定的图不是一颗树，则打印“Error:K conponents”其中K是组成图的各部分的数量。

代码：

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<vector>
    using namespace std;
    vector<int> Map[10001];
    int visited[10001],deep[10001];
    int maxdeep=0;
    int DFS(int node)
    {
       visited[node]=1;
       int maxdeep=0,curdeep,i;
       for(i=0;i<Map[node].size();i++)
       {
           if(visited[Map[node][i]]==0)
           {
               curdeep=DFS(Map[node][i]);
               if(maxdeep<curdeep)
               {
                   maxdeep=curdeep;
               }
           }
       }
       return maxdeep+1;
    }
    int main()
    {
        int i,j,n,m,k,t,x,y,flag=0;
        scanf("%d",&n);
        for(i=1;i<=n-1;i++)
        {
            scanf("%d %d",&x,&y);
            Map[x].push_back(y);
            Map[y].push_back(x);
        }
        for(i=1;i<=n;i++)
        {
            if(flag==0)
            {
                memset(visited,0,sizeof(visited));
            }
            else
            {
                break;
            }
            deep[i]=DFS(i);
            if(deep[i]>maxdeep)
            {
               maxdeep=deep[i];
            }
            for(j=1;j<=n;j++)
            {
                if(visited[j]==0)
                {
                    flag++;
                    DFS(j);
                }
            }
        }
        if(flag>0)
        {
            printf("Error: %d components\n",flag+1);
        }
        else
        {
            for(i=1;i<=n;i++)
            {
                if(deep[i]==maxdeep)
                {
                    printf("%d\n",i);
                }
            }
        }
        return 0;
    }