By yusijia

Updated:

Contents 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>

#define MAXN 1000
using namespace std;

int father[MAXN];//存储节点的父亲节点,如果父亲节点就是自己则说明是根节点
int rank[MAXN];/*rank数组用来存储大树的秩并且作为大树的标记*/

//并查集的初始化
void Init_set()
{
    int i;
    for(i = 0; i < MAXN; i++){
        father[i] = i;              //把所有的节点都初始化为根节点
        rank[i] = 0;                //秩初始化为0
    }
}

//递归查找
int Find(int x){
    if(x != father[x])              //不是根节点
        father[x] = Find(father[x]);//递归查找并压缩路径
    return father[x];
}

/*集合的合并*/
void Union(int x, int y){
    int root_x = Find(x);
    int root_y = Find(y);
    if(root_x != root_y){
        if(rank[root_x] > rank[root_y])
            father[root_y] = root_x;    //把小树合并到大树
        else if(rank[root_x] < rank[root_y])
            father[root_x] = root_y;    //把小树合并到大树
        else{
                father[root_x] = root_y;
                rank[root_y]++;         //相等的时候,将其中一个的秩加一
        }
    }
}
Contents