支持运算

  • MAKE_SET(S, n)：初始化并查集 S ，即 $S = {S_1, S_2,\cdots,S_n}$。每个动态集合 $S_i(1 <= i <= n)$ 仅仅包含一个编号为 i 的元素，该元素作为集合 $s_i$ 的“代表”。
  • FIND_SET(S, x)：返回并查集 S 中 x 元素所在集合的“代表”。
  • UNION(S, x, y) ：在并查集 S 中将 x 和 y 两个元素所在的动态集合合并为一个新的集合。并假设在此运算前这两个动态集合是分离的，通常以 $S_x$ 或者 $S_y$ 的“代表”作为新集合的“代表”。

树实现并查集

  • 用有根树标识集合，树种的每个结点包含集合的一个元素，每颗树表示一个集合。每一个分离集合又叫分离集合树。

  • 多个集合形成一个森林，以每颗树的树根作为集合的“代表”。整个并查集也就是一个分离集合森林。

  • 树中每个结点有一个指向双亲结点的指针，根节点的双亲结点指针指向其自身。

合并树时为了使树比较平衡有如下规定：

假设合并树A、B，有：$h_A > h_B$ ，则应将 B 树作为 A 树的子树；否则应将 A 树作为 B 树的子树。总之，总是将高度较小的分离集合树作为子树。得到了新的分离集合树 C 的高度为 $h_C$ ，如以 B 树作为 A 树的子树，$h_C = MAX{h_A, h_B+1}$。

这样得到的分离集合树的高度不会超过 $log_2n$，对应的查找与合并的时间复查度也就稳定在 $O(log_2n)$了。

为此给每一个结点增加一个秩（rank）域，它是近似子树高度的正常数，同时它也是该结点高度的一个上界

存储结构

1
2
3
4
5
typedef struct node{
	int data;		// 结点对应的编号 
	int rank;		// 结点对应的秩 
	int parent;		// 结点对应的双亲下标 
} UFSTree;			// 并查集树的结点类型

运算

初始化

建立一个存放并查集的数组 t ，每个结点对应的人，结点的 data 值设置为该人的编号，rank 值设置为0，parent 值设置为自己。

1
2
3
4
5
6
7
8
// 初始化
void MAKE_SET(UFSTree t[], int n) {
	for (int i = 1; i <= n; ++i) {
		t[i].data = i;			// 数据为该人的编号 
		t[i].rank = 0;			// 秩初始化为 0 
		t[i].parent = i;		// 双亲初始化指向自己 
	}
}

查找一个元素所属的集合

在分离集合森林中，每一颗分离集合树对应一个集合。如果要查找某一元素所属的集合，就是要找这个元素对应的结点所在的分离集合树。

用分离集合树的根节点的编号来标识这颗分离集合树，这样查找一个结点所在的分离集合树也就是查找该节点所在分离集合树的根节点。

寻找根节点的方法：任取树中的一个结点（一般是要查找的结点），沿双亲结点方向一直往树根上走；初始时，取一个结点，走到它的双亲结点，然后以双亲结点为基点，走到双亲结点的双亲结点，….， 直至走到一个没有双亲结点的结点（双亲结点就是自己）位置，这个结点就是树的根节点。

1
2
3
4
5
6
7
// 查找元素 x 所在集合的编号 
int FIND_SET(UFSTree t[], int x) {
	if (x != t[x].parent)
		return FIND_SET(t, t[x].parent);
	else
		return x;
}

对于 n 个人而言，构成的分离集合树的高度最高位 $log_2n$，所以本算法的时间复杂度位 $O(log_2n)$。

两个元素各自所属的集合的合并

在进行合并的时候，需要让秩较小的根指向具有较大秩的根。如果两根的秩相等，随便让一个指向另一个，同时秩增加1.

1
2
3
4
5
6
7
8
9
10
11
12
13
// 合并两个元素所属的集合
void UNION(UFSTree t[], int x, int y) {
	// 先找到两颗分离集合树的编号 
	x = FIND_SET(t, x);
	y = FIND_SET(t, y);
	if (t[x].rank > t[y].rank)
		t[y].parent = x;
	else {
		t[x].parent = y;
		if (t[x].rank == t[y].rank)
			t[y].rank++;
	}
}

对于 n 个人而言，本算法的时间复杂度位 $O(log_2 n)$。

应用

判断两个人是否是亲戚。

输入

先输入两个数：N , M。N代表人数，M表示关系个数。

再输入M行，每行两个数字为人的编号，表示这两个人是亲戚。

之后再输入一个数Q，表示想要询问的问题的个数

再输入Q行，表示问题。每行是两个数字，表示两个人的编号。

样例输入：

10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9

输出

输出两者是否是亲戚，是则输出 YES；否则输出NO。

样例输出：

YES

NO

YES

数组实现并查集

朴素并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int p[N];		// 存储每个结点的双亲结点

// 初始化
void init() {
    for (int i = 1; i <= n; ++i) p[i] = i;
}

// 查找元素
int find(int x) {
    if (p[x] != x) p[x] = find(p[x])
    return x;
}

// 合并 a 和 b所在的两个集合
void Union(int a, int b) {
    p[find(a)] = find(b);
}

维护size的并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int p[N], size[N];		// p 存储每个结点的双亲结点， size只有是根结点时才有意义，表示分离集合数种的点的数量

// 初始化
void init() {
    for (int i = 1; i <= n; ++i) {
        p[i] = i;
        size[i] = 1;
    }
}

int find(int x) {
    if (x != p[x]) return find(p[x]);
    return x;
} 

void Union(int a, int b) {
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);
}

维护到根节点距离的并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int p[N], d[N];			// p 存储每个点的双亲结点，d[x] 存储 x 到 p[x]的距离

void init() {
    for (int i = 1; i <= n; ++i) {
        p[i] = i;
        d[i] = 0;
    }
}

int find(int x) {
    if (p[x] != x) {
        int u = find(p[x]);
        d[x] += d[p[x]];
        p[x] = u;
    }
    return x;
}

void Union(int a, int b) {
    p[find(a)] = find(b);
    d[find(a)] = distance;		// 根据具体问题，初始化时 find(a) 的偏移量
}