1021 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 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 (≤104) 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 • 1 • 2 • 3 • 4 • 5
Sample Output 1:
3 4 5
Sample Input 2:
5 1 3 1 4 2 5 3 4 • 1 • 2 • 3 • 4 • 5
Sample Output 2:
Error: 2 components
题意
第一行包含整数 N ，表示节点数量。
节点编号为 1 ∼ N
接下来 N − 1 行，每行包含两个整数，表示两个节点之间存在一条边。
输出最深的根的节点编号。
如果最深的根不唯一，则按照从小到大的顺序，将它们依次输出，每个占一行。
如果给定的图不是树，输出 Error: K components ，其中 K KK 是图中连通分量的数量。
思路
在输入每条边的信息时，我们可以利用并查集来对该图进行判断，输入前令 k = n ，每输入一条边时就判断这条边两个端点是否已经在同一个连通块中，如果不在则将 k - 1 ，最终的 k 值就是该图连通块的数量。
如果 k > 1 则该图不是树，输出 Error: K components ，否则对每个结点都进行一次 dfs 操作，找到最深的结点。注意，我们这里的结点是从小到大进行 dfs ，所以最终得到的结果一定是单调递增的，不用再进行排序。
在 dfs 的过程中，注意不能回溯即当前结点再访问其父结点，需要额外进行判断。
代码
#include<bits/stdc++.h> using namespace std; const int N = 10010, M = 2 * N; int h[N], e[M], ne[M], idx; int p[N]; int n; //链式前向星保存每一条边 void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } //并查集查找操作 int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } //获取当前最大深度，其中u表示当前结点，father表示父结点 int dfs(int u, int father) { int depth = 0; //遍历其所有孩子结点 for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j == father) continue; //防止回溯 depth = max(depth, dfs(j, u) + 1); } return depth; } int main() { //初始化 cin >> n; memset(h, -1, sizeof h); for (int i = 1; i <= n; i++) p[i] = i; //输入所有边，且用并查集判断该图是否为树 int k = n; for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; add(a, b), add(b, a); if (find(a) != find(b)) { k--; p[find(a)] = find(b); } } if (k > 1) printf("Error: %d components\n", k); else { vector<int> nodes; int max_depth = 0; for (int i = 1; i <= n; i++) { int depth = dfs(i, 0); //获得当前深度 if (depth > max_depth) //如果当前深度大于当前最大深度 { nodes.clear(); max_depth = depth; nodes.push_back(i); } else if (depth == max_depth) //如果当前深度等于当前最大深度 nodes.push_back(i); } //输出结果 for (auto& x : nodes) cout << x << endl; } return 0; }
