1021. Deepest Root (25)【并查集+深搜】——PAT (Advanced Level) Practise

Root (25)【并查集+深搜】——PAT (Advanced Level) Practise"/>

1021. Deepest Root (25)【并查集+深搜】——PAT (Advanced Level) Practise

题目信息

1021. Deepest Root (25)

时间限制1500 ms 内存限制65536 kB 代码长度限制16000 B

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

解题思路

并查集+深搜

AC代码

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int un[10005];
vector<bool> vis(10005);
vector<vector<int> > mp(10005);
int getfa(int a){return un[a] = (un[a] == a) ? a : getfa(un[a]);
}
void unin(int a, int b){un[getfa(a)] = un[getfa(b)];
}int high(int id){int h = 0;vis[id] = true;for (int i = 0; i < mp[id].size(); ++i){if (!vis[mp[id][i]]){vis[mp[id][i]] = true;h = max(h, high(mp[id][i]));}}return h + 1;
}
int main()
{int n, a, b;scanf("%d", &n);for (int i = 1; i <= n; ++i){un[i] = i;}for (int i = 1; i < n; ++i){scanf("%d%d", &a, &b);mp[a].push_back(b);mp[b].push_back(a);unin(a, b);}set<int> st;for (int i = 1; i <= n; ++i){st.insert(getfa(i));}if (st.size() == 1){vector<int> v;int mn = -1;for (int i = 1; i <= n; ++i){vis.assign(n+1, false);int h = high(i);if (h > mn){v.clear();mn = h;v.push_back(i);}else if (h == mn){v.push_back(i);}}for (int i = 0; i < v.size(); ++i){printf("%d\n", v[i]);}}else{printf("Error: %d components\n", st.size());}return 0;
}