hdu 1829+hdu 1856(并查集）-白红宇

hdu 1829+hdu 1856(并查集）

阅读量：6881 次

发布时间：2019-06-27

本文共 1884 字，大约阅读时间需要 6 分钟。

题目链接：

思路：就是同性别的合并在一个集合中，然后每次输入看u，v是否在同一个集合中。。。然后不知道为什么用路径压缩不可以写。。。一些就TLE了。。。无语了。。。orz。。。

View Code

1 #define _CRT_SECURE_NO_WARNINGS 2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 const int MAXN=2000+20; 7 int parent[MAXN]; 8 int mark[MAXN]; 9 int n,m;10 11 void Initiate(){12     memset(mark,0,sizeof(mark));13     for(int i=1;i<=n;i++){14         parent[i]=i;15     }16 }17 18 int Find(int x){19     int s=x;20     while(s!=parent[s]){21         s=parent[s];22     }23     return s;24     /*25     int s;26     for(s=x;parent[s]>=0;s=parent[s]);27     while(s!=x){28         int tmp=parent[x];29         parent[x]=s;30         x=tmp;31     }32     return s;33     */34 }35 36 void Union(int R1,int R2){37     int r1=Find(R1);38     int r2=Find(R2);39     if(r1

题目链接：

思路：就是合并集合。。。赤裸裸的并查集啊！！！！可我为什么wa了无数次啊！！！！orz....

View Code

1 #define _CRT_SECURE_NO_WARNINGS 2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 const int MAXN=10000000+100; 7 int parent[MAXN]; 8 int _count[MAXN]; 9 int n;10 int MAX;11 12 void Initiate(){13     for(int i=1;i
         
          =0;s=parent[s]);22     while(s!=x){23         int tmp=parent[x];24         parent[x]=s;25         x=tmp;26     }27     return s;28 }29 30 31 void Union(int R1,int R2){32     int r1=Find(R1);33     int r2=Find(R2);34     if(r1!=r2){35         parent[r2]=r1;36         _count[r1]+=_count[r2];37     }38 }39 40 int main(){41     while(~scanf("%d",&n)){42         Initiate();43         MAX=0;44         for(int i=1;i<=n;i++){45             int u,v;46             scanf("%d%d",&u,&v);47             Union(u,v);48         }49         for(int i=1;i
          
           MAX){51                 MAX=_count[i];52             }53         }54         printf("%d\n",MAX);55     }56     return 0;57 }