題干：

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

題目大意：

一個連通的非循環(huán)圖可以看作是一個樹。樹的高度取決于所選的根?，F(xiàn)在你應(yīng)該找到根，結(jié)果是最高的樹。這樣的根叫做最深的根。對于每個測試用例，在一行中打印每個最深的根。如果這樣的根不是惟一的，則按其數(shù)字的遞增順序打印它們。如果給定的圖形不是樹，則打印Error: K components，其中K是圖中連圖分量的數(shù)量。

解題報告：

? 因?yàn)闀r限是兩秒，直接枚舉每一個點(diǎn)當(dāng)根節(jié)點(diǎn)就可以。但是這題其實(shí)可以優(yōu)化，只枚舉葉子節(jié)點(diǎn)就可以。甚至可以用樹的直徑去亂搞一波，時間復(fù)雜度會更優(yōu)。但這題時限很寬，所以沒必要優(yōu)化。

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 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【PAT - 甲级1021】Deepest Root (25分)（并查集，暴力枚举）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。