数据结构——并查集

区间合并

指路一篇讲的很好的文章：算法学习笔记(1) : 并查集 - 知乎 (zhihu.com)

1.数据结构

并查集主要用途：

1. 快速将两个集合合并（时间复杂度接近O(1)）
2. 快速查询两个元素是否在一个集合当中（时间复杂度接近O(1)）

基本原理：每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点储存它的父节点，p[x]表示x的父节点。问题1：如何判断树根：== x)问题2：如何求x的集合编号：!= x) x = p[x];(常用优化方法：路径压缩)
问题3：如何合并两个集合：px是x的集合编号，py是y的集合编号。= y;

数据结构要点：

• 不是真正用树状存储，而是用数组模拟树状存储。

• 每个节点存储的是其父节点。所以除了根节点，不可能有节点指向自身即(p[x]==x)

• 将两个集合合并：使一个集合的根节点指向另一个集合的根

2.基础代码实现

存在问题：效率低下。随着不断合并，会形成一段长长的链，底部找到根节点会变得越来越难

初始化

for (int i = 1; i <= n; ++i)
	fa[i] = i;

初始化先将所有的节点指向自身（每个节点都是一个孤立的集合）。

查询

int find(int x) {
    if(fa[x] == x)	return x;
    else	return find(fa[x]);
}

合并

inline void merge(int i, int j) {
    fa[find(i)] = find(j);//使 i 点所在集合的根节点指向 j 点所在的根节点
}

3.代码优化

3.1路径压缩（最常用，但是比较极端）

int find(int x) {
    return x == fa[x] ? x : (fa[x] = find(fa[x]));//每个节点均指向其对应的根节点
}

图解：

3.2路径分裂（基本不用）

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

3.3路径减半（基本不用）

int find(int x) {
    while (x != p[x]) {//x与x的父节点均指向其祖父节点的父节点
        p[x] = p[p[x]];
        x = p[x];
    }
    return x;
}

3.4按秩合并（路径压缩的优化）

原理：小树向大数合并。用一个数组rank[]记录每个根节点对应的树的深度（如果不是根节点，其rank相当于以它作为根节点的子树的深度）。一开始，把所有元素的rank（秩）设为1。合并时比较两个根节点，把rank较小者往较大者上合并。

初始化（按秩合并）

inline void init(int n) {
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
        rank[i] = 1;
    }
}

合并（按秩合并）

inline void merge(int i, int j) {
    int x = find(i), y = find(j);    //先找到两个根节点
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (rank[x] == rank[y] && x != y)
        rank[y]++;                   //如果深度相同且根节点不同，则新的根节点的深度+1
}

4.AcWing代码模板

(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)的偏移量

5.例题解析

原题链接：240. 食物链 - AcWing题库

题解：AcWing 240. 食物链 - AcWing