PAT (Advanced Level) Practise 1021 Deepest Root (25)

1021. Deepest Root (25)

时间限制

1500 ms

内存限制

65536 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

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

对于不能成树的用并查集来判断，对于能成树的，随便选择一个点，找到最远点，所有最远点都可以是答案，然后随便找一个最远点，以这个点为根再找到全部最远点

那些点也是答案，然后排个序输出即可。至于为什么可以这么做，可以参考树的直径的证明。

#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long LL;
const int INF = 0x7FFFFFFF;
const int maxn = 2e4 + 10;
vector<int> t[maxn];
int n, fa[maxn], x, y, cnt, ans[maxn], dis[maxn], maxd;

int get(int x)
{
  return x == fa[x] ? x : fa[x] = get(fa[x]);
}

void dfs(int x, int y, int dep)
{
  dis[x] = dep; maxd = max(maxd, dep);
  for (int i = 0; i < t[x].size(); i++)
  {
    if (t[x][i] == y) continue;
    dfs(t[x][i], x, dep + 1);
  }
}

int main()
{
  scanf("%d", &n);  cnt = n;
  for (int i = 1; i <= n; i++) fa[i] = i;
  for (int i = 1; i < n; i++)
  {
    scanf("%d%d", &x, &y);
    int fx = get(x), fy = get(y);
    if (fx != fy) { fa[fx] = fy; cnt--; }
    t[x].push_back(y);  t[y].push_back(x);
  }
  if (cnt > 1) printf("Error: %d components\n", cnt);
  else
  {
    cnt = 0;

    dfs(1, 1, 0); 
    for (int i = 1; i <= n; i++) if (dis[i] == maxd) ans[cnt++] = i;

    for (int i = 1; i <= n; i++) dis[i] = 0;
    
    dfs(ans[0], ans[0], 0);
    for (int i = 1; i <= n; i++) if (dis[i] == maxd) ans[cnt++] = i;

    sort(ans, ans + cnt);
    cnt = unique(ans, ans + cnt) - ans;
    for (int i = 0; i < cnt; i++) printf("%d\n", ans[i]);
  }
  return 0;
}