1021 Deepest Root
分数 25
全屏浏览
切换布局
作者 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 (≤10 4) 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
1.分析
1.要考虑结点数为1的情况，输出1。
2.可以用dfs遍历每个点，找到高度最高的点。
3.用并查集来找联通块的个数。
2.代码
#include<iostream>
#include<vector>
#include<cstring>
#include<set>
using namespace std;
const int MAX = 1e5 + 10;
vector<int> v[MAX];
set<int> s, t;
int fa[MAX], n,vis[MAX],ma,l;
int find(int x) { //并查集查找函数if (fa[x] != x) fa[x] = find(fa[x]);return fa[x];
}
void getroot(int x,int d){ //找深度vis[x]=1;int num=0;for (int i = 0; i < v[x].size(); i++) {int t=v[x][i];if(!vis[t]){getroot(t,d+1);num++;}}if(num==0){l=max(l,d);}
}
int main() {cin >> n;for (int i = 1; i <= n; i++) { //初始化fa[i] = i;}for (int i = 1; i < n; i++) { //输入int x, y;cin >> x >> y;v[x].push_back(y);v[y].push_back(x);fa[find(y)] = fa[find(x)]; //连接}for (int i = 1; i <= n; i++) { //找联通块个数t.insert(find(i));}if (t.size() == 1) {for(int i=1;i<=n;i++){memset(vis,0,sizeof vis);l=0;getroot(i,1);if(l>ma){ma=l;s.clear();s.insert(i);}else if(ma==l){s.insert(i);}}for (auto it : s) {cout << it << endl;}}else cout << "Error: " << t.size() << " components" << endl;return 0;
}
