PAT甲级——A1021 Deepest Root

概述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

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 (≤) which is the number of nodes,and hence the nodes are numbered from 1 to N. Then N−@H_419_31@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 componentswhere K is the number of connected components in the graph.

Sample input 1:

51 21 31 42 5

Sample Output 1:

345

Sample input 2:

51 31 42 53 4

Sample Output 2:

Error: 2 components

 1 #include <iostream> 2 #include <vector> 3 #include<set> 4 using namespace std; 5 vector<vector<int>>G; 6 int N,maxH = 0; 7 bool visit[10010]; 8 set<int>res; 9 vector<int>temp;10 11 voID DFS(int node,int H)12 {13     if (H > maxH)14     {15         temp.clear();16         temp.push_back(node);//更新新的根节点17         maxH = H;18     }19     else if (H == maxH)20         temp.push_back(node);//相同的最优解21     visit[node] = true;22     for (int i = 0; i < G[node].size(); ++i)23         if (visit[G[node][i]] == false)24             DFS(G[node][i],H + 1);25 }26 27 int main()28 {29     int a,b,s1 = 0,cnt = 0;30     cin >> N;31     G.resize(N+1);32     for (int i = 1; i < N; ++i)33     {34         cin >> a >> b;35         G[a].push_back(b);36         G[b].push_back(a);37     }38     for (int i = 1; i <= N; ++i)39     {40         if (visit[i] == false)//开始深度搜索遍历，如果是一个联通区域，则只会执行一次41         {42             DFS(i,1);43             if (i == 1)44             {45                 if (temp.size() != 0)46                     s1 = temp[0];47                 for (int j = 0; j < temp.size(); ++j)48                     res.insert(temp[j]);49             }50             cnt++;//计算集合数51         }        52     }53     if (cnt != 1)54         printf("Error: %d components\n",cnt);55     else56     {57         temp.clear();58         maxH = 0;59         fill(visit,visit + N + 1,false);60         DFS(s1,1);61         for (int j = 0; j < temp.size(); ++j)62             res.insert(temp[j]);63         for (auto r : res)64             cout << r << endl;65     }66     return 0;67 }

总结

以上是内存溢出为你收集整理的PAT甲级——A1021 Deepest Root全部内容，希望文章能够帮你解决PAT甲级——A1021 Deepest Root所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。