【PAT - 甲级1021】Deepest Root (25分)（并查集，暴力枚举）

科技前沿 • 2025-02-07 13:08 • 阅读 47

大家好，我是讯享网，很高兴认识大家。

题干：

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

讯享网

Sample Output 1:

讯享网3 4 5

Sample Input 2:

5 1 3 1 4 2 5 3 4

Sample Output 2:

讯享网Error: 2 components

题目大意：

讯享网

一个连通的非循环图可以看作是一个树。树的高度取决于所选的根。现在你应该找到根，结果是最高的树。这样的根叫做最深的根。对于每个测试用例，在一行中打印每个最深的根。如果这样的根不是惟一的，则按其数字的递增顺序打印它们。如果给定的图形不是树，则打印Error: K components，其中K是图中连图分量的数量。

解题报告：

因为时限是两秒，直接枚举每一个点当根节点就可以。但是这题其实可以优化，只枚举叶子节点就可以。甚至可以用树的直径去乱搞一波，时间复杂度会更优。但这题时限很宽，所以没必要优化。

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; int n,m,f[MAX],rt[MAX],dep[MAX]; vector<int> vv[MAX],ans; int getf(int v) { return f[v] == v ? v : f[v] = getf(f[v]); } void merge(int u,int v) { int t1 = getf(u),t2 = getf(v); f[t2] = t1; } int mx; void dfs(int u,int fa) { dep[u] = dep[fa] + 1; mx = max(mx,dep[u]); int up = vv[u].size(); for(int i = 0; i<up; i++) { int v = vv[u][i]; if(v == fa) continue; dfs(v,u); } } int main() { cin>>n; for(int i = 1; i<=n; i++) f[i] = i; for(int u,v,i = 1; i<=n-1; i++) cin>>u>>v,vv[u].pb(v),vv[v].pb(u),merge(u,v); int cnt = 0; for(int i = 1; i<=n; i++) { if(f[i] == i) cnt++; } if(cnt != 1) { printf("Error: %d components\n",cnt);return 0 ; } for(int root = 1; root<=n; root++) { mx = 0; dfs(root,0); rt[root] = mx; } mx = 0; for(int i = 1; i<=n; i++) { if(rt[i] > mx) { mx = rt[i]; ans.clear();ans.pb(i); } else if(rt[i] == mx) ans.pb(i); } sort(ans.begin(),ans.end()); for(auto x : ans) { printf("%d\n",x); } return 0 ; }