Time Limit: 5000/1000 MS
(Java/Others) Memory Limit: 327680/102400 K
(Java/Others)
Total Submission(s): 11865 Accepted
Submission(s): 4395
#include <iostream> #include <cstdio> using namespace std; const int maxn=10000005; int f[maxn],v[maxn]; int findset(int x) { return f[x]!=x?f[x]=findset(f[x]):f[x];}//带路径压缩 void merge(int a,int b) { int fa=findset(a); int fb=findset(b); if(fa!=fb) f[fa]=fb; } int main() { int n,a,b,i,ans; while(~scanf("%d",&n)) { ans=0; for(i=1;i<=10000000;i++) f[i]=i,v[i]=0; while(n--) { scanf("%d %d",&a,&b); merge(a,b); } for(i=1;i<=10000000;i++) v[findset(f[i])]++; for(i=1;i<=10000000;i++) ans=ans>v[i]?ans:v[i]; printf("%d\n",ans); } return 0; }
原文:http://www.cnblogs.com/xiong-/p/3583168.html