hdu 1232 / 1213 并查集（求子集个数）

并查集模板：

用到了两个优化，一个是按秩（rank）合并，一个是路径压缩。

 1 int rank[N];
 2 int parent[N];
 3 int n;
 4 void init()
 5 {
 6     int i;
 7     for( i=1;i<=n;i++)
 8     {
 9         parent[i]=i;
10         rank[i]=0;
11     }
12 }
13 int Find(int x)
14 {
15     if(x== parent[x]) return x;
16     return parent[x]=Find(parent[x]);
17 }
18 void Union(int x, int y)
19 {
20      int xf=Find(x);
21      int yf=Find(y);
22     if(rank[xf] > rank[yf])
23         parent[yf]=xf;
24     else
25     {
26         parent[xf] =yf;
27         if(rank[xf] == rank[yf])
28             rank[yf]++;
29     }
30 }

1：初始化init（），创建n-1 颗只有一个结点的树，并且是自己的父节点。（保证，根节点的父节点是其本身）。此时，每棵树的高度-秩（rank）为0。

2：Find(x) 函数，过程是一种两趟方法，当它递归时，第一趟沿着查找路径向上直到找到根，当递归回溯时，第二趟沿着搜索树向下更新每个结点，使其直接指向根。

3：Union（x，y） ,合并过程。合并操作有两种情况，取决于两棵树的根是否有相同的秩。如果根没有相同的秩，就让较大秩的根成为较小秩的根的父节点，但秩本身保持不变。另一种情况是两个根有相同的秩时，任意选择两个根中的一个作为父节点，并使它的秩加1。

hdu 1232

题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=1232

题目代码：

#include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>
#include<map>
#include<math.h>

#define N 1005
using namespace std;

int rank[N];
int parent[N];
int n;
void init()
{
    int i;
    for( i=1;i<=n;i++)
    {
        parent[i]=i;
        rank[i]=0;
    }
}
int Find(int x)
{
    if(x== parent[x]) return x;
    return parent[x]=Find(parent[x]);
}
void Union(int x, int y)
{
     int xf=Find(x);
     int yf=Find(y);
    if(rank[xf] > rank[yf])
        parent[yf]=xf;
    else
    {
        parent[xf] =yf;
        if(rank[xf] == rank[yf])
            rank[yf]++;
    }
}
int main()
{
    int m;
    while(scanf("%d",&n)&&n)
    {
        int u,v;
        int total=n-1;
        init();
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            cin>>u>>v;
            if(Find(u)!= Find(v))
            {
                Union(u,v);
                total--;
            }
        }
        cout<<total<<endl;
    }
    return 0 ;
}

hdu 1213

题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=1213

代码如下：

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string>
 4 #include<string.h>
 5 #include<map>
 6 #include<math.h>
 7 
 8 #define N 1005
 9 using namespace std;
10 
11 int rank[N];
12 int parent[N];
13 int n;
14 void init()
15 {
16     int i;
17     for( i=1;i<=n;i++)
18     {
19         parent[i]=i;
20         rank[i]=0;
21     }
22 }
23 int Find(int x)
24 {
25     if(x== parent[x]) return x;
26     return parent[x]=Find(parent[x]);
27 }
28 void Union(int x, int y)
29 {
30      int xf=Find(x);
31      int yf=Find(y);
32     if(rank[xf] > rank[yf])
33         parent[yf]=xf;
34     else
35     {
36         parent[xf] =yf;
37         if(rank[xf] == rank[yf])
38             rank[yf]++;
39     }
40 }
41 int main()
42 {
43     int t;
44     cin>>t;
45     while(t--)
46     {
47         int m,u,v;
48         cin>>n>>m;
49         int total=n;
50         init();
51         for(int i=0;i<m;i++)
52         {
53             cin>>u>>v;
54             if(Find(u)!= Find(v))
55             {
56                 Union(u,v);
57                 total--;
58             }
59         }
60         cout<<total<<endl;
61     }
62     return 0 ;
63 }