并查集-上

基本介绍

相关方法介绍
（1）一开始每个元素都拥有自己的集合，在自己的集合里只有这个元素自己
（2）int find（i）：查找 i 所在集合的代表元素，代表元素来代表 i 所在的集合
（3）boolean isSameSet（a, b）：判断 a 和 b 在不在一个集合里
（4）void union（a, b）：a 所在集合所有元素与 b 所在集合所有元素合并成一个集合
（5）各种操作单次调用的均摊时间复杂度为 O（1）
并查集的两个优化，都发生在 find 方法里
（1）扁平化（一定要做），又叫路径压缩
（2）小挂大（可以不做，原论文中是秩的概念，可以理解为粗略高度或者大小）

⚠️ 注意

并查集的小扩展（下节课的题目重点展示）：可以定制信息：并查集目前有多少个集合，以及给每个集合打上标签信息

带权并查集、可持久化并查集、可撤销并查集，都是备战算法竞赛的同学必学的内容，这些内容会在【挺难】阶段的课程里安排讲述

复杂度分析

感性理解单次调用的均摊时间复杂度为 O（1）即可，其实为 α（n），反阿克曼函数
当 n = 10⁸⁰ 次方即可探明宇宙原子量，α(n) 为 0.69 的返回值也不超过 6，那么就可以认为时间复杂度为 O（1）
并查集的发明者 Bernard A. Galler 和 Michael J. Fischer，从 1964 年证明到 1989 年才证明完毕，建议记住即可，理解证明难度很大！

并查集模板代码

基础模板

定义 father 数组，下标表示每个节点的编号，father [ i ] 表示 i 号节点的向上挂接的节点是谁
定义 size 数组，下标表示每个节点的编号，size [ i ] 表示编号为 i 的节点所在集合的元素个数，并采用小挂大的合并方式
定义 stack 数组，做扁平化处理，收集沿途节点，使得每个节点的上级挂接节点直接指向父节点，只有代表节点的 size 信息有用

java

class Disjoint {

    public static int MAXN = 1000001;

    public static int[] father = new int[MAXN];

    // 记录每个集合中元素的个数
    public static int[] size = new int[MAXN];

    // 用于收集沿途节点，实现扁平化处理
    public static int[] stack = new int[MAXN];

    public static int n;

    public static void build() {
        // 初始时都指向自己，且集合中都只有自己一个元素
        for (int i = 0; i <= n; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    public static int find(int n) {
        // 沿途收集了几个节点
        int size = 0;
        // 上级节点不是本身，说明还没找到上级节点
        while (n != father[n]) {
            // 收集沿途节点
            stack[size++] = n;
            // n 往上朓，来到当前节点的上级节点位置
            n = father[n];
        }
        // 沿途节点都收集好了，做扁平化处理
        while (size > 0) {
            father[stack[--size]] = n;
        }
        return n;
    }

    public static boolean isSameSet(int x, int y) {
        return find(x) == find(y);
    }

    public static void union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        // 不在一个结合中才合并，且遵循小挂大的原则
        if (fx != fy) {
            if (size[fx] >= size[fy]) {
                // 小挂大
                father[fy] = fx;
                // 大的集合吸纳新的元素
                size[fx] += size[fy];
            } else {
                father[fx] = fy;
                size[fy] += size[fx];
            }
        }
    }
}

优化模板

java

class Disjoint {

    public static int MAXN = 200001;

    public static int[] father = new int[MAXN];

    public static int n;

    public static void build() {
        for (int i = 0; i <= n; i++) {
            father[i] = i;
        }
    }

    public static int find(int n) {
        // 自身就是根节点，直接返回
        if (n == father[n]) {
            return n;
        }
        // 扁平化处理，将当前节点的上级节点变为父节点
        return father[n] = find(father[n]);
    }

    public static boolean isSameSet(int x, int y) {
        return find(x) == find(y);
    }

    public static void union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx == fy) {
            return;
        }
        // x 的根节点挂接到 y 的根节点上
        father[fx] = fy;
    }
}

⚠️ 注意事项

Tip

union 方法一定要用单独的变量接收两个元素的父节点，用变量来判断，这是比较安全的写法，不要直接用方法去判断，在某些题目中可能会出错

模板题

题目链接

洛谷：https://www.luogu.com.cn/problem/P3367
牛客：https://www.nowcoder.com/practice/e7ed657974934a30b2010046536a5372

洛谷代码实现

java

import java.io.*;

public class Main {

    public static int MAXN = 200001;

    public static int[] father = new int[MAXN];

    public static int n;

    public static void build() {
        for (int i = 0; i <= n; i++) {
            father[i] = i;
        }
    }

    public static int find(int n) {
        // 自身就是根节点，直接返回
        if (n == father[n]) {
            return n;
        }
        // 扁平化处理，将当前节点的上级节点变为父节点
        return father[n] = find(father[n]);
    }

    public static boolean isSameSet(int x, int y) {
        return find(x) == find(y);
    }

    public static void union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx == fy) {
            return;
        }
        // x 的根节点挂接到 y 的根节点上
        father[fx] = fy;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) in.nval;
            build();
            in.nextToken();
            int m = (int) in.nval;
            for (int i = 0; i < m; i++) {
                in.nextToken();
                int z = (int) in.nval;
                in.nextToken();
                int x = (int) in.nval;
                in.nextToken();
                int y = (int) in.nval;
                if (z == 1) {
                    union(x, y);
                } else {
                    out.println(isSameSet(x, y) ? "Y" : "N");
                }
            }
        }
        out.flush();
        out.close();
        br.close();
    }
}

牛客代码实现

java

import java.io.*;

public class Main {

    public static int MAXN = 1000001;

    public static int[] father = new int[MAXN];

    // 记录每个集合中元素的个数
    public static int[] size = new int[MAXN];

    // 用于收集沿途节点，实现扁平化处理
    public static int[] stack = new int[MAXN];

    public static int n;

    public static void build() {
        // 初始时都指向自己，且集合中都只有自己一个元素
        for (int i = 0; i <= n; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    public static int find(int n) {
        // 沿途收集了几个节点
        int size = 0;
        // 上级节点不是本身，说明还没找到上级节点
        while (n != father[n]) {
            // 收集沿途节点
            stack[size++] = n;
            // n 往上朓，来到当前节点的上级节点位置
            n = father[n];
        }
        // 沿途节点都收集好了，做扁平化处理
        while (size > 0) {
            father[stack[--size]] = n;
        }
        return n;
    }

    public static boolean isSameSet(int x, int y) {
        return find(x) == find(y);
    }

    public static void union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        // 不在一个结合中才合并，且遵循小挂大的原则
        if (fx != fy) {
            if (size[fx] >= size[fy]) {
                // 小挂大
                father[fy] = fx;
                // 大的集合吸纳新的元素
                size[fx] += size[fy];
            } else {
                father[fx] = fy;
                size[fy] += size[fx];
            }
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) in.nval;
            build();
            in.nextToken();
            int m = (int) in.nval;
            for (int i = 0; i < m; i++) {
                in.nextToken();
                int op = (int) in.nval;
                in.nextToken();
                int x = (int) in.nval;
                in.nextToken();
                int y = (int) in.nval;
                if (op == 1) {
                    out.println(isSameSet(x, y) ? "Yes" : "No");
                } else {
                    union(x, y);
                }
            }
        }
        out.flush();
        out.close();
        br.close();
    }
}

情侣牵手

题目链接

https://leetcode.cn/problems/couples-holding-hands/

思路分析

根据题目可以得到以下结论：对于第 i 对情侣的编号 n，可以由第 i 对情侣的 a / 2 与 b / 2 得到
并查集中单个集合中存储两个元素，表示二者是情侣，如果发现两个元素所对应的情侣编号不相同，即二者不是情侣，将二者对应的情侣编号合并
⭐ 结论：集合中有 k 对情侣，则执行 k - 1 次调整后可以使得所有情侣配对
进一步简化，对于每个集合都要执行 k - 1 次操作，假设只有三个集合 a、b、c，在未执行合并方法之前，单个集合表示一对情侣，每个集合的元素个数为自己的编号，则 a 集合需要执行 a - 1 次调整，b 集合需要执行 b - 1 次，调整 c 集合需要执行 c - 1 次调整，累加得到总的调整次数，即为 a + b + c - 3，a + b + c 表示情侣的对数，3 表示集合的个数，可以得出如下推论
⭐ 调整次数 = 情侣的对数 - 集合的个数，假设有 n 个人，则情侣对数为 n / 2

代码实现

java

class Solution {

    int MAXN = 31;

    int[] father = new int[MAXN];

    int sets;

    public int minSwapsCouples(int[] row) {
        int n = row.length;
        build(n / 2);
        for (int i = 0; i < n; i += 2) {
            // i 位置的人 / 2 得到该请情侣对应的编号
            union(row[i] / 2, row[i + 1] / 2);
        }
        // 根据推论，调整的次数为情侣的对数 - 集合的个数
        return n / 2 - sets;
    }

    public void build(int n) {
        for (int i = 0; i <= n; i++) {
            father[i] = i;
        }
        // 初始为 n 对情侣，有 n 个集合
        sets = n;
    }

    public int find(int n) {
        if (n == father[n]) {
            return n;
        }
        return father[n] = find(father[n]);
    }

    public void union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx == fy) {
            return;
        }
        // x 的根节点挂接到 y 的根节点上
        father[fx] = fy;
        // 合并之后集合的个数要减少
        sets--;
    }
}

相似字符串组

题目链接

https://leetcode.cn/problems/similar-string-groups/

思路分析

明确相似的含义（1）和本身相同是相似（2）本身中的两个字符交换是相似，即两个单词只要有两个对应位置的字符不相同就是相似的
需要求有多少组，即遍历每一个字符，以该字符为基准，遍历其他字符，如果是相似的就放到一组中，统计组数即可，使用并查集实现 union 操作
由于要求是相似的为一组，即给定数组中的每个单词的长度是相同的，要抓住这个特点
时间复杂度：O（m * n² ），m 是字符串的长度

代码实现

java

class Solution {

    int MAXN = 301;

    int[] father = new int[MAXN];

    int sets;

    public int numSimilarGroups(String[] strs) {
        int n = strs.length;
        int m = strs[0].length();
        build(n);
        // 遍历每个单词，以该单词为基准寻找同组的单词
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // 两个单词不在一个集合中，判断是否可以合并
                if (find(i) != find(j)) {
                    // 记录差异的位置个数
                    int diff = 0;
                    for (int k = 0; k < m && diff < 3; k++) {
                        if (strs[i].charAt(k) != strs[j].charAt(k)) {
                            diff++;
                        }
                    }
                    // 要么为本身，要么是相似，即 diff = 2
                    if (diff == 0 || diff == 2) {
                        union(i, j);
                    }
                }
            }
        }
        return sets;
    }

    // 一个单词对应一个下标，用下标来判断是否在同一个集合中
    public void build(int n) {
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
        sets = n;
    }

    public int find(int n) {
        if (n == father[n]) {
            return n;
        }
        return father[n] = find(father[n]);
    }

    public void union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx == fy) {
            return;
        }
        // x 的根节点挂接到 y 的根节点上
        father[fx] = fy;
        // 合并后集合的个数需要减少
        sets--;
    }
}

岛屿数量

题目链接

https://leetcode.cn/problems/number-of-islands/

思路分析

本题为二维问题，而在并查集中，处理的都是一维问题，每个元素都对应一个指标，本题中通过给（i，j）位置的元素一个编号，实现从二维问题向一维问题的转化，进而使用并查集实现
（0，0）位置的编号为 0，逐个向后编号，（i，j）位置的编号即为 i * m + j，m 表示总的列数
并查集实现思路：检查每个位置的四个方向，如果值相同就 union，最后返回集合的个数即可
优化点：实际上并不需要每次都检查该位置的上下左右四个方向，只需要检查左边和上边，每个位置的右边和下面这两个方向会由后面元素左边和上边检查，即无需重复检查
build 函数逻辑：只需要关注 1 的位置，0 的位置没用，对 1 的位置实现并查集操作

代码实现

java

class Solution {

    int MAXSIZE = 100001;

    int[] father = new int[MAXSIZE];

    // 总列数
    int cols;

    // 集合的个数
    int sets;

    public int numIslands(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        build(n, m, grid);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') {
                    // 只需要关注左边和上边两个方向
                    // 注意判断是否越界
                    if (j > 0 && grid[i][j - 1] == '1') {
                        union(i, j, i, j - 1);
                    }
                    if (i > 0 && grid[i - 1][j] == '1') {
                        union(i, j, i - 1, j);
                    }
                }
            }
        }
        return sets;
    }

    public void build(int n, int m, char[][] board) {
        cols = m;
        sets = 0;
        // 将 1 位置转为一维并查集，0 位置无需关注
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == '1') {
                    int index = index(i, j);
                    // 初始时指向自己
                    father[index] = index;
                    sets++;
                }
            }
        }
    }

    public int index(int x, int y) {
        return x * cols + y;
    }

    public int find(int n) {
        if (n == father[n]) {
            return n;
        }
        return father[n] = find(father[n]);
    }

    public void union(int a, int b, int c, int d) {
        int fa = find(index(a, b));
        int fb = find(index(c, d));
        if (fa == fb) {
            return;
        }
        // a 位置的根节点挂接到 b 位置的根节点上
        father[fa] = fb;
        // 合并之后，集合个数需要减少
        sets--;
    }
}

并查集-上

基本介绍 ​

相关方法介绍 ​

（1）一开始每个元素都拥有自己的集合，在自己的集合里只有这个元素自己 ​

（2）int find（i）：查找 i 所在集合的代表元素，代表元素来代表 i 所在的集合 ​

（3）boolean isSameSet（a, b）：判断 a 和 b 在不在一个集合里 ​

（4）void union（a, b）：a 所在集合所有元素 与 b 所在集合所有元素合并成一个集合 ​

（5）各种操作单次调用的均摊时间复杂度为 O（1） ​

并查集的两个优化，都发生在 find 方法里 ​

（1）扁平化（一定要做），又叫路径压缩 ​

（2）小挂大（可以不做，原论文中是秩的概念，可以理解为粗略高度或者大小） ​

并查集的小扩展（下节课的题目重点展示）：可以定制信息：并查集目前有多少个集合，以及给每个集合打上标签信息 ​

带权并查集、可持久化并查集、可撤销并查集，都是备战算法竞赛的同学必学的内容，这些内容会在【挺难】阶段的课程里安排讲述 ​

复杂度分析 ​

感性理解单次调用的均摊时间复杂度为 O（1）即可，其实为 α（n），反阿克曼函数 ​

当 n = 1080 次方即可探明宇宙原子量，α(n) 为 0.69 的返回值也不超过 6，那么就可以认为时间复杂度为 O（1） ​

并查集的发明者 Bernard A. Galler 和 Michael J. Fischer，从 1964 年证明到 1989 年才证明完毕，建议记住即可，理解证明难度很大！ ​

并查集模板代码 ​

基础模板 ​

定义 father 数组，下标表示每个节点的编号，father [ i ] 表示 i 号节点的向上挂接的节点是谁 ​

定义 size 数组，下标表示每个节点的编号，size [ i ] 表示编号为 i 的节点所在集合的元素个数，并采用小挂大的合并方式 ​

定义 stack 数组，做扁平化处理，收集沿途节点，使得每个节点的上级挂接节点直接指向父节点，只有代表节点的 size 信息有用 ​

优化模板 ​

⚠️ 注意事项 ​

union 方法一定要用单独的变量接收两个元素的父节点，用变量来判断，这是比较安全的写法，不要直接用方法去判断，在某些题目中可能会出错 ​

模板题 ​

题目链接 ​

洛谷：https://www.luogu.com.cn/problem/P3367 ​

牛客：https://www.nowcoder.com/practice/e7ed657974934a30b2010046536a5372 ​

洛谷代码实现 ​

牛客代码实现 ​

情侣牵手 ​

题目链接 ​

https://leetcode.cn/problems/couples-holding-hands/ ​

思路分析 ​

根据题目可以得到以下结论：对于第 i 对情侣的编号 n，可以由第 i 对情侣的 a / 2 与 b / 2 得到 ​

并查集中单个集合中存储两个元素，表示二者是情侣，如果发现两个元素所对应的情侣编号不相同，即二者不是情侣，将二者对应的情侣编号合并 ​

⭐ 结论：集合中有 k 对情侣，则执行 k - 1 次调整后可以使得所有情侣配对 ​

⭐ 调整次数 = 情侣的对数 - 集合的个数，假设有 n 个人，则情侣对数为 n / 2 ​

代码实现 ​

相似字符串组 ​

题目链接 ​

https://leetcode.cn/problems/similar-string-groups/ ​

思路分析 ​

明确相似的含义（1）和本身相同是相似（2）本身中的两个字符交换是相似，即两个单词只要有两个对应位置的字符不相同就是相似的 ​

需要求有多少组，即遍历每一个字符，以该字符为基准，遍历其他字符，如果是相似的就放到一组中，统计组数即可，使用并查集实现 union 操作 ​

由于要求是相似的为一组，即给定数组中的每个单词的长度是相同的，要抓住这个特点 ​

时间复杂度：O（m * n2 ），m 是字符串的长度 ​

代码实现 ​

岛屿数量 ​

题目链接 ​

https://leetcode.cn/problems/number-of-islands/ ​

思路分析 ​

本题为二维问题，而在并查集中，处理的都是一维问题，每个元素都对应一个指标，本题中通过给（i，j）位置的元素一个编号，实现从二维问题向一维问题的转化，进而使用并查集实现 ​

（0，0）位置的编号为 0，逐个向后编号，（i，j）位置的编号即为 i * m + j，m 表示总的列数 ​

并查集实现思路：检查每个位置的四个方向，如果值相同就 union，最后返回集合的个数即可 ​

优化点：实际上并不需要每次都检查该位置的上下左右四个方向，只需要检查左边和上边，每个位置的右边和下面这两个方向会由后面元素左边和上边检查，即无需重复检查 ​

build 函数逻辑：只需要关注 1 的位置，0 的位置没用，对 1 的位置实现并查集操作 ​

代码实现 ​

基本介绍

相关方法介绍

（1）一开始每个元素都拥有自己的集合，在自己的集合里只有这个元素自己

（2）int find（i）：查找 i 所在集合的代表元素，代表元素来代表 i 所在的集合

（3）boolean isSameSet（a, b）：判断 a 和 b 在不在一个集合里

（4）void union（a, b）：a 所在集合所有元素与 b 所在集合所有元素合并成一个集合

（5）各种操作单次调用的均摊时间复杂度为 O（1）

并查集的两个优化，都发生在 find 方法里

（1）扁平化（一定要做），又叫路径压缩

（2）小挂大（可以不做，原论文中是秩的概念，可以理解为粗略高度或者大小）

并查集的小扩展（下节课的题目重点展示）：可以定制信息：并查集目前有多少个集合，以及给每个集合打上标签信息

带权并查集、可持久化并查集、可撤销并查集，都是备战算法竞赛的同学必学的内容，这些内容会在【挺难】阶段的课程里安排讲述

复杂度分析

感性理解单次调用的均摊时间复杂度为 O（1）即可，其实为 α（n），反阿克曼函数

当 n = 10⁸⁰ 次方即可探明宇宙原子量，α(n) 为 0.69 的返回值也不超过 6，那么就可以认为时间复杂度为 O（1）

并查集的发明者 Bernard A. Galler 和 Michael J. Fischer，从 1964 年证明到 1989 年才证明完毕，建议记住即可，理解证明难度很大！

并查集模板代码

基础模板

定义 father 数组，下标表示每个节点的编号，father [ i ] 表示 i 号节点的向上挂接的节点是谁

定义 size 数组，下标表示每个节点的编号，size [ i ] 表示编号为 i 的节点所在集合的元素个数，并采用小挂大的合并方式

定义 stack 数组，做扁平化处理，收集沿途节点，使得每个节点的上级挂接节点直接指向父节点，只有代表节点的 size 信息有用

优化模板

⚠️ 注意事项

union 方法一定要用单独的变量接收两个元素的父节点，用变量来判断，这是比较安全的写法，不要直接用方法去判断，在某些题目中可能会出错

模板题

题目链接

洛谷：https://www.luogu.com.cn/problem/P3367

牛客：https://www.nowcoder.com/practice/e7ed657974934a30b2010046536a5372

洛谷代码实现

牛客代码实现

情侣牵手

题目链接

https://leetcode.cn/problems/couples-holding-hands/

思路分析

根据题目可以得到以下结论：对于第 i 对情侣的编号 n，可以由第 i 对情侣的 a / 2 与 b / 2 得到

并查集中单个集合中存储两个元素，表示二者是情侣，如果发现两个元素所对应的情侣编号不相同，即二者不是情侣，将二者对应的情侣编号合并

⭐ 结论：集合中有 k 对情侣，则执行 k - 1 次调整后可以使得所有情侣配对

⭐ 调整次数 = 情侣的对数 - 集合的个数，假设有 n 个人，则情侣对数为 n / 2

代码实现

相似字符串组

题目链接

https://leetcode.cn/problems/similar-string-groups/

思路分析

明确相似的含义（1）和本身相同是相似（2）本身中的两个字符交换是相似，即两个单词只要有两个对应位置的字符不相同就是相似的

需要求有多少组，即遍历每一个字符，以该字符为基准，遍历其他字符，如果是相似的就放到一组中，统计组数即可，使用并查集实现 union 操作

由于要求是相似的为一组，即给定数组中的每个单词的长度是相同的，要抓住这个特点

时间复杂度：O（m * n² ），m 是字符串的长度

代码实现

岛屿数量

题目链接

https://leetcode.cn/problems/number-of-islands/

思路分析

本题为二维问题，而在并查集中，处理的都是一维问题，每个元素都对应一个指标，本题中通过给（i，j）位置的元素一个编号，实现从二维问题向一维问题的转化，进而使用并查集实现

（0，0）位置的编号为 0，逐个向后编号，（i，j）位置的编号即为 i * m + j，m 表示总的列数

并查集实现思路：检查每个位置的四个方向，如果值相同就 union，最后返回集合的个数即可

优化点：实际上并不需要每次都检查该位置的上下左右四个方向，只需要检查左边和上边，每个位置的右边和下面这两个方向会由后面元素左边和上边检查，即无需重复检查

build 函数逻辑：只需要关注 1 的位置，0 的位置没用，对 1 的位置实现并查集操作

代码实现