1021 Deepest Root (25 分)

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

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:

Sample Output 1:

3
4
5

Sample Input 2:

Sample Output 2:

Error: 2 components

题目分析：最开始我理解错题意了我认为给的连通图会有回路但实际上是没有的

有回路的应该是不连通的

还要注意用数组存会使空间过大用vector<vector<int> >比较好

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<iostream>
 3 #include<vector>
 4 #include<queue>
 5 #include<stack>
 6 #include<algorithm>
 7 using namespace std;
 8 int Highest = -1;
 9 vector<vector<int> >G;
10 int Dist[10001];
11 int Collected[10001];
12 int N;
13 int Components = 1;
14 vector<int> V;
15 void dfs(int v)
16 {
17     Collected[v] = 1;
18     for (int i = 0; i < G[v].size(); i++)
19     {
20         if (!Collected[G[v][i]])
21         {
22             Dist[G[v][i]] = Dist[v] + 1;
23             dfs(G[v][i]);
24         }
25     }
26 }
27 int main()
28 {
29     cin >> N;
30     G.resize(N + 1);
31     for (int i = 1; i < N; i++)
32     {
33         int v1, v2;
34         cin >> v1 >> v2;
35         G[v1].push_back(v2);
36         G[v2].push_back(v1);
37     }
38     int i = 1;
39     for (; i <= N; i++)
40     {
41         fill(Dist, Dist + N + 1, 0);
42         fill(Collected, Collected + N + 1, 0);
43         dfs(i);
44         for (int j = 1; j <= N; j++)
45         {
46             if (!Collected[j])
47             {
48                 dfs(j);
49                 Components++;
50             }
51         }
52         if (Components != 1)
53             break;
54         int Max = -65535;
55         for (int i = 1; i <= N; i++)
56             if (Max < Dist[i])
57                 Max = Dist[i];
58         if (Max > Highest)
59         {
60             Highest = Max;
61             V.clear();
62             V.push_back(i);
63         }
64         else if (Max == Highest)
65             V.push_back(i);
66     }
67     if (Components == 1)
68     {
69         for (int i = 0; i < V.size() - 1; i++)
70             printf("%d
", V[i]);
71         printf("%d", V[V.size() - 1]);
72     }
73     else
74         printf("Error: %d components", Components);
75     return 0;
76 }

View Code