要解决两大问题:
1. 数包含几个连通分量
2. 如何找到最深结点
注意:connected components的意思是连通分量
问题1我用并查集解决
问题2转化为如何得到每个结点的深度
值得注意之处是对于问题2来说,下图是测试用例1给出的树
可以看出从1出发得到5的深度是3
从3出发得到5的深度是4
……
以每个结点为根节点开始遍历,会得到每个结点的一个深度,而我们只需要维护每个结点的最大深度。(如果不是这样,而是记录每个深度再排序,二维整型列表会导致内存超限)
AC代码
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<set>using namespace std;const int maxn = 10010;vector<int> G[maxn];int F[maxn] = {0};int n;int ccnum = 0;//连通分量的个数 vector<int> cc[maxn]; int seekr(int x){int a = x;while(F[x]!=x){x = F[x];}while(F[a]!=a){int z = a;F[z] = x;a = F[a];}return x;
}void unite(int a,int b){int ra = seekr(a);int rb = seekr(b);if(ra!=rb)F[ra] = rb;return;
}int vis[maxn] = {0};int maxLen = 0;int L[maxn] = {0};//1:no 2:rootvoid DFS(int no,int len,int start){vis[no] = 1;if(len>L[no])L[no] = len;for(int i=0;i<G[no].size();i++){int next = G[no][i];if(vis[next]==0){DFS(next,len+1,start);}}return;
}int main(){ cin>>n;for(int i=0;i<n-1;i++){int v1,v2;cin>>v1>>v2;G[v1].push_back(v2);G[v2].push_back(v1);if(F[v1]==0)F[v1] = v1;if(F[v2]==0)F[v2] = v2;unite(v1,v2);}for(int i=1;i<=n;i++){int r = seekr(i);if(cc[r].size()==0){ccnum ++;cc[r].push_back(i);}}if(ccnum>1){printf("Error: %d components",ccnum);return 0;}for(int i=1;i<=n;i++){fill(vis,vis+n+1,0);DFS(i,1,i);}vector<int> roots;int maxLen = 0;for(int i=1;i<=n;i++){if(L[i]>maxLen){maxLen = L[i];roots.clear();roots.push_back(i);}else if(L[i]==maxLen){roots.push_back(i);}}sort(roots.begin(),roots.end());for(int i=0;i<roots.size();i++){printf("%d\n",roots[i]);}return 0;
}