dfs求最大层数
并查集求连通个数
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> #include <string> #include <vector> using namespace std; /* dfs求最大层数 并查集求连通个数 */ const int maxn=10000+5; int n; int anslayer=0; //最大层数 vector<int>deeproot; int maxlayer; //保存当前dfs的最大层数 int vis[maxn]; //并查集 struct UF{ int fa[maxn]; void init(){ for(int i=0;i<maxn;i++) fa[i]=i; } int find_root(int x){ if(fa[x]!=x) fa[x]=find_root(fa[x]); return fa[x]; } void Union(int x,int y){ int fx=find_root(x); int fy=find_root(y); if(fx!=fy){ fa[fy]=fx; } } }uf; //链式前向星建立边 int head[maxn]; int tot; struct Edge{ int to; int next; }edge[maxn*2]; int init(){ memset(head,-1,sizeof(head)); tot=0; } void add(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } void dfs(int u,int layer){ bool flag=true; vis[u]=1; for(int k=head[u];k!=-1;k=edge[k].next){ int v=edge[k].to; if(!vis[v]){ flag=false; //vis[v]=1; dfs(v,layer+1); } } //到叶子节点了 if(flag){ if(layer>maxlayer) maxlayer=layer; } } int main() { int u,v; scanf("%d",&n); init(); uf.init(); for(int i=0;i<n-1;i++){ scanf("%d %d",&u,&v); add(u,v); add(v,u); uf.Union(u,v); } memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++){ int f=uf.find_root(i); vis[f]=1; } int cnt=0; for(int i=1;i<=n;i++){ if(vis[i]==1) cnt++; } if(cnt>1){ printf("Error: %d components ",cnt); } else{ for(int i=1;i<=n;i++){ maxlayer=0; memset(vis,0,sizeof(vis)); //printf("dfs %d ",i); dfs(i,1); if(maxlayer>anslayer){ anslayer=maxlayer; deeproot.clear(); deeproot.push_back(i); } else if(maxlayer==anslayer){ deeproot.push_back(i); } } sort(deeproot.begin(),deeproot.end()); for(int i=0;i<deeproot.size();i++){ printf("%d ",deeproot[i]); } } return 0; }