acwing算法基础之数据结构--并查集算法

1 基础知识

并查集支持O(1)时间复杂度实现：

1. 将两个集合合并。
2. 询问两个元素是否在一个集合中。

基本原理：每个集合用一颗树来表示。树根的编号就是整个集合的编号。每个结点存储它的父结点，p[x]表示x的父结点。

问题1：如何判断树根：p[x] == x。
问题2：如何求x的集合编号：while (p[x] != x) x = p[x];。上述为朴素做法，可以通过路径压缩，进行优化。

int find(int x) {
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}
1
2
3
4

问题3：如何合并两个集合：px是x的集合编号，py是y的集合编号：p[px] = py。

2 模板

(1)朴素并查集：

    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);

(2)维护size的并查集：

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);

(3)维护到祖宗节点距离的并查集：

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

3 工程化

class UnionFind {
public:
	UnionFind(int n) {
		this->n = n;
		p.resize(n);
		cnt.resize(n);
		d.resize(n);
		for (int i = 0; i < n; ++i) {
			p[i] = i;
			cnt[i] = 1;
			d[i] = 0;
		}
	}

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

	void merge(int x, int y) {
		int px = find(x), py = find(y);
		if (px != py) {
			p[px] = py;
			cnt[py] += cnt[px];		
		}
		return;
	}
	
	int size(int x) {//返回x所在集合的大小
	    return cnt[find(x)];
	}
private:
	int n;
	vector<int> p; //存储父结点
	vector<int> cnt; //存储集合大小，根结点的cnt才有意义
	vector<int> d; //存储到根结点的距离
};
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