More is better HDU

More is better

题意：给出n个关系，问最多有多少个人直接或者间接有关系．

并查集．

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn=10000010;
 5 int f[maxn],rk[maxn];
 6 
 7 int gf(int x){
 8     return x==f[x]?f[x]:f[x]=gf(f[x]);
 9 }
10 int n;
11 int main(){
12    // freopen("in.txt","r",stdin);
13     while(scanf("%d",&n)!=EOF){
14         int ans=0;
15         for(int i=0;i<maxn;i++) f[i]=i,rk[i]=1;
16         for(int i=0;i<n;i++){
17             int a,b;
18             scanf("%d %d",&a,&b);
19             int pa=gf(a),pb=gf(b);
20             if(pa!=pb){
21                 f[pa]=pb;
22                 rk[pb]+=rk[pa];
23               //  ans=max(ans,rk[pb]);
24             }
25         }
26         for(int i=1;i<maxn;i++) ans=max(ans,rk[i]);
27         printf("%d
",ans);
28     }
29     return 0;
30 }