并查集入门

先贴上参考资料

1、杭电的并查集课件...

http://wenku.baidu.com/link?url=IJ10qA1w6APfrbZuF-tq0Rl_-SAM4_LyXBLpkAn_GUwlBhaFRZfMZN_XdUlXkwIhRW1SCp3tJBkqtaU7kOzOq33ENgByKAgHA3jtkKzTQ97

2、相关博客...

http://hi.baidu.com/czyuan_acm/item/13cbd3258c29e20d72863edf

http://www.cppblog.com/yuan1028/archive/2011/02/13/139990.html

并查集，顾名思义，就是做 “并” 和 “查” 两件事的。我们用到并查集基本都是模拟树形结构的，线形的效率太低。

先贴上模版

 1 #include<cstdio>
 2 #define MAXN 50005
 3 int father[MAXN], rank[MAXN];
 4 void init(int n)
 5 {
 6   for (int i = 1; i <= n; ++i)
 7   {
 8     father[i] = i;
 9     rank[i] = 0;
10   }
11 }
12 int find(int x)
13 {
14   if (father[x] != x)
15   {
16     father[x] = find(father[x]);
17   }
18   return father[x];
19 }
20 void merge(int a, int b)
21 {
22   int fa = find(a);
23   int fb = find(b);
24   if (rank[fa] < rank[fb])
25   {
26     father[fa] = fb;
27   }
28   if (rank[a] > rank[fb])
29   {
30     father[fb] = fa;
31   }
32   if (rank[fa] == rank[fb])
33   {
34     father[fb] = fa;
35     rank[fa]++;
36   }
37 }

1、father[]用来记录此结点的父结点，rank[]用来记录此树的深度

2、find()函数中用了路径压缩，在寻找某个结点的祖先时，将这条路径上所有结点的父结点更新为祖先结点

3、merge()函数中，是按秩合并。秩就是树的高度。不过很多时候没有必要按秩合并，也就不用开rank[]，直接下面这样就ok

1 void merge(int a, int b)
2 {
3   int fa = find(a);
4   int fb = find(b);
5   father[fa] = fb;
6 }

练习题：

1、HDOJ 1213 How Many Tables(水题，直接套模版)

http://acm.hdu.edu.cn/showproblem.php?pid=1213

2、HDOJ 1232 畅通工程(同上、、)

http://acm.hdu.edu.cn/showproblem.php?pid=1232

3、POJ 1182 食物链(经典问题，里面的公式比较难想、、)

http://poj.org/problem?id=1182

下面是AC代码：

 1 #include<cstdio>
 2 #define MAXN 1005
 3 int father[MAXN];
 4 void init()
 5 {
 6   for (int i = 0; i < MAXN; ++i)
 7   {
 8     father[i] = i;
 9   }
10 }
11 int find(int n)
12 {
13   if (father[n] != n)
14   {
15     father[n] = find(father[n]);
16   }
17   return father[n];
18 }
19 void merge(int a, int b)
20 {
21   if (find(a) != find(b))
22   {
23     father[find(b)] = find(a);
24   }
25 }
26 int main()
27 {
28   int T;
29   scanf("%d", &T);
30   while(T--)
31   {
32     int n, m, a, b, count = 0;
33     init();
34     scanf("%d %d", &n, &m);
35     for (int i = 0; i < m; ++i)
36     {
37       scanf("%d %d", &a, &b);
38       merge(a, b);
39     }
40     for (int i = 1; i <= n; ++i)
41     {
42       if (father[i] == i)
43       {
44         count++;
45       }
46     }
47     printf("%d\n", count);
48   }
49   return 0;
50 }

View Code

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #define MAXN 1000
 4 int father[MAXN];
 5 void init()
 6 {
 7   for (int i = 0; i < MAXN; ++i)
 8   {
 9     father[i] = i;
10   }
11 }
12 int find(int n)
13 {
14   int r = n;
15   while(father[r] != r)
16   {
17     r = father[r];
18   }
19   return r;
20 }
21 void merge(int s, int e)
22 {
23   int a = find(s);
24   int b = find(e);
25   if (a < b)
26   {
27     father[b] = a;
28   }else
29   {
30     father[a] = b;
31   }
32 }
33 
34 int main()
35 {
36   int n, m, s, e;
37   while(scanf("%d", &n) != EOF)
38   {
39     int ans = 0;
40     if (n == 0)
41     {
42       exit(0);
43     }else
44     {
45       init();
46       scanf("%d", &m);
47       for (int i = 0; i < m; ++i)
48       {
49         scanf("%d %d", &s, &e);
50         merge(s, e);
51       }
52       for (int i = 1; i <= n; ++i)
53       {
54         if (find(i) == i)
55         {
56           ans += 1;
57         }
58       }
59       printf("%d\n", ans-1);
60     }
61   }
62   return 0;
63 }

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 #define MAX 50050
 5 int par[MAX],rel[MAX];
 6 
 7 void init(int n)
 8 {
 9     for(int i=1;i<=n;i++)
10     {
11         par[i]=i;
12         rel[i]=0;
13     }
14 }
15 
16 int find(int x)
17 {
18     if(par[x]==x)    return x;
19     int tmp=par[x];
20     par[x]=find(tmp);
21     rel[x]=(rel[tmp]+rel[x])%3;
22     return par[x];
23 }
24 
25 void union_set(int x,int y,int px,int py,int d)
26 {
27     par[px]=py;
28     rel[px]=(rel[y]-rel[x]+2+d)%3;
29 }
30 
31 int main()
32 {
33     int T,n,m,a,b,pa,pb,k,r;
34     scanf("%d%d",&n,&m);
35     {
36         init(n);
37         r=0;
38         for(int i=0;i<m;i++)
39         {
40             scanf("%d%d%d",&k,&a,&b);
41             if(a>n||b>n)    {    r++;    continue;}
42             if(k==2&&a==b)    {    r++;    continue;}
43             pa=find(a);
44             pb=find(b);
45             if(pa==pb)
46             {
47                 if((rel[b]+k+2)%3!=rel[a])    r++;
48             }
49             else    union_set(a,b,pa,pb,k);
50         }
51         printf("%d\n",r);
52     }
53 }

View Code