Union Find

讲得浅显易懂。

uva,10608

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 const int maxn=30005;
 7 
 8 int id[maxn];
 9 int sz[maxn];
10 int n,m;
11 int count;
12 int find(int p)
13 {
14     return id[p];
15 }
16 
17 void Union(int p,int q)
18 {
19     int pId=find(p);
20     int qId=find(q);
21     
22     if(pId==qId) return;
23     for(int i=0;i<n;i++)
24         if(id[i]==pId)
25         {
26             id[i]=qId;
27             sz[qId]++;
28         }
29 }
30 
31 int main()
32 {
33     int t;
34     int a,b;
35     scanf("%d",&t);
36     while(t--)
37     {
38         scanf("%d%d",&n,&m);
39         for(int i=0;i<n;i++)
40         {
41             id[i]=i;
42             sz[i]=1;
43         }
44         
45         for(int i=0;i<m;i++)
46         {
47             scanf("%d%d",&a,&b);
48             Union(a-1,b-1);
49         }
50         int max=0;
51         
52         for(int i=0;i<n;i++)
53             if(sz[i]>max)
54                 max=sz[i];
55         printf("%d
",max);
56     }
57     return 0;
58 }

用最原始的方法做

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 const int maxn=30005;
 7 
 8 int id[maxn];
 9 int sz[maxn];
10 int n,m;
11 int count;
12 int find(int p)
13 {
14     while(p!=id[p]) p=id[p];
15     return p;
16 }
17 
18 void Union(int p,int q)
19 {
20     int pId=find(p);
21     int qId=find(q);
22     
23     if(pId==qId) return;
24     id[pId]=qId;
25     sz[qId]+=sz[pId];
26 }
27 
28 int main()
29 {
30     int t;
31     int a,b;
32     scanf("%d",&t);
33     while(t--)
34     {
35         scanf("%d%d",&n,&m);
36         for(int i=0;i<n;i++)
37         {
38             id[i]=i;
39             sz[i]=1;
40         }
41         
42         for(int i=0;i<m;i++)
43         {
44             scanf("%d%d",&a,&b);
45             Union(a-1,b-1);
46         }
47         int max=0;
48         
49         for(int i=0;i<n;i++)
50             if(max<sz[i])
51                 max=sz[i];
52         printf("%d
",max);
53 }
54         return 0;
55 }

建树的方法实现，且避免了头重脚轻

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 const int maxn=30005;
 7 
 8 int id[maxn];
 9 int sz[maxn];
10 int n,m;
11 int count;
12 int find(int p)
13 {
14     while(p!=id[p])
15     {
16         id[p]=id[id[p]];
17         p=id[p];
18     }
19     return p;
20 }
21 
22 void Union(int p,int q)
23 {
24     int pId=find(p);
25     int qId=find(q);
26     
27     if(pId==qId) return;
28     if(sz[pId]<sz[qId]){id[pId]=qId;sz[qId]+=sz[pId];}
29     else{id[qId]=pId;sz[pId]+=sz[qId];}
30 }
31 
32 int main()
33 {
34     int t;
35     int a,b;
36     scanf("%d",&t);
37     while(t--)
38     {
39         scanf("%d%d",&n,&m);
40         for(int i=0;i<n;i++)
41         {
42             id[i]=i;
43             sz[i]=1;
44         }
45         
46         for(int i=0;i<m;i++)
47         {
48             scanf("%d%d",&a,&b);
49             Union(a-1,b-1);
50         }
51         int max=0;
52         
53         for(int i=0;i<n;i++)
54             if(max<sz[i])
55                 max=sz[i];
56         printf("%d
",max);
57 }
58         return 0;
59 }

最高效的算法

uva,459

经验：需要的再转换拿来用，不要一次性处理。

有的时候需要得频繁就一次性处理。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cstdlib>
 6 #include <cmath>
 7 
 8 using namespace std;
 9 
10 int id[27];
11 int sz[27];
12 
13 void Make_Set(int x)  //不要一次性赋值完，可能不一定用那么多
14 {
15     id[x]=x;
16     sz[x]=1;
17 }
18 
19 int find(int p)
20 {
21     while(p!=id[p])
22     {
23         id[p]=id[id[p]];
24         p=id[p];
25     }
26     return p;
27 }
28 
29 void Union(int p,int q)
30 {
31     int i=find(p);
32     int j=find(q);
33     
34     if(i==j) return;
35     if(sz[i]<sz[j]) {id[i]=j;sz[j]+=sz[i];}
36     else {id[j]=i;sz[i]+=sz[j];}
37 }
38 
39 int main()
40 {
41     int t;
42     char ch;
43     char s[5];
44     char u,v;
45     int x,y;
46     scanf("%d

",&t);
47     while(t--)
48     {
49         gets(s);
50         sscanf(s,"%c",&ch);
51         int count=ch-'A'+1;
52         
53         for(int i=0;i<count;i++)
54             Make_Set(i);
55         while(gets(s) && strcmp(s,"")!=0)
56         {
57             sscanf(s,"%c%c",&u,&v);
58             x=u-'A';y=v-'A';
59             if(find(x)!=find(y))
60             {
61                 Union(x,y);
62                 count--;   //不做全局变量可以直接赋值
63             }
64         }
65         printf("%d
",count);
66         if(t)
67             printf("
");
68     }
69     return 0;
70 }

View Code

uva,793

当一行输入数字下面要输入字符的时候加' ';

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 const int maxn=10005;
 8 
 9 int id[maxn];
10 int sz[maxn];
11 
12 int find(int p)
13 {
14     while(p!=id[p])
15     {
16         id[p]=id[id[p]];
17         p=id[p];
18     }
19     return p;
20 }
21 
22 void Union(int p,int q)
23 {
24     int i=find(p);
25     int j=find(q);
26     
27     if(i==j) return;
28     if(sz[i]<sz[j]) {id[i]=j;sz[j]+=sz[i];}
29     else {id[j]=i;sz[i]+=sz[j];}
30 }
31 
32 int main()
33 {
34     int t;
35     scanf("%d
",&t);  //注意输入输出格式
36     int n;
37     char s[10];
38     int suc,unsuc;
39     while(t--)
40     {
41         suc=unsuc=0;
42         char d;
43         int a,b;
44         scanf("%d
",&n);  //输入输出
45         for(int i=0;i<n;i++)
46         {
47             id[i]=i;
48             sz[i]=1;
49         }
50         while(gets(s)&& strcmp(s,"")!=0)
51         {
52             sscanf(s,"%c%d%d",&d,&a,&b);
53             if(d=='c')
54             {
55                 Union(a-1,b-1);
56             }
57             else if(d=='q')
58             {
59                 if(find(a-1)==find(b-1))
60                     suc++;
61                 else
62                     unsuc++;
63             }
64         }
65         printf("%d,%d
",suc,unsuc);
66         if(t)
67             printf("
");
68     }
69     return 0;
70 }

View Code

活在现实，做在梦里。