1021. Deepest Root (25)

女爷i 2022-05-31 09:55 256阅读 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:

  1. 5
  2. 1 2
  3. 1 3
  4. 1 4
  5. 2 5

Sample Output 1:

  1. 3
  2. 4
  3. 5

Sample Input 2:

  1. 5
  2. 1 3
  3. 1 4
  4. 2 5
  5. 3 4

Sample Output 2:

  1. Error: 2 components

题目大意:

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

代码:

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<algorithm>
  4. #include<vector>
  5. using namespace std;
  6. vector<int> Map[10001];
  7. int visited[10001],deep[10001];
  8. int maxdeep=0;
  9. int DFS(int node)
  10. {
  11. visited[node]=1;
  12. int maxdeep=0,curdeep,i;
  13. for(i=0;i<Map[node].size();i++)
  14. {
  15. if(visited[Map[node][i]]==0)
  16. {
  17. curdeep=DFS(Map[node][i]);
  18. if(maxdeep<curdeep)
  19. {
  20. maxdeep=curdeep;
  21. }
  22. }
  23. }
  24. return maxdeep+1;
  25. }
  26. int main()
  27. {
  28. int i,j,n,m,k,t,x,y,flag=0;
  29. scanf("%d",&n);
  30. for(i=1;i<=n-1;i++)
  31. {
  32. scanf("%d %d",&x,&y);
  33. Map[x].push_back(y);
  34. Map[y].push_back(x);
  35. }
  36. for(i=1;i<=n;i++)
  37. {
  38. if(flag==0)
  39. {
  40. memset(visited,0,sizeof(visited));
  41. }
  42. else
  43. {
  44. break;
  45. }
  46. deep[i]=DFS(i);
  47. if(deep[i]>maxdeep)
  48. {
  49. maxdeep=deep[i];
  50. }
  51. for(j=1;j<=n;j++)
  52. {
  53. if(visited[j]==0)
  54. {
  55. flag++;
  56. DFS(j);
  57. }
  58. }
  59. }
  60. if(flag>0)
  61. {
  62. printf("Error: %d components\n",flag+1);
  63. }
  64. else
  65. {
  66. for(i=1;i<=n;i++)
  67. {
  68. if(deep[i]==maxdeep)
  69. {
  70. printf("%d\n",i);
  71. }
  72. }
  73. }
  74. return 0;
  75. }

发表评论

表情:
评论列表 (有 0 条评论,256人围观)

还没有评论,来说两句吧...

相关阅读