并查集（union-find）

介绍

概念

当涉及到处理元素之间的等价关系、集合的合并与查询等问题时，它是一种用于维护不相交集合的有效方法，常被用于解决诸如连通性、网络连接状态、等价关系等问题。

核心思想

并查集通过构建一个森林（或者称为集合），其中每个元素都属于一个集合，每个集合以一个代表元素来标识。这样的数据结构可以高效地进行两个关键操作：查找和合并。

操作

  • 查找（Find）： 查找一个元素所属的集合，通常以代表元素作为标识。这个操作通常用于判断两个元素是否属于同一个集合，即判断它们的代表元素是否相同。
1
2
3
int find(int x) {
    return pa[x] == x ? x : (pa[x] = find(pa[x]));
}
  • 合并（Union）： 将两个不相交的集合合并为一个集合，即将两个集合的代表元素连接在一起。
1
2
3
4
5
6
7
void union(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return;
    if (rank[fx] <= rank[fy]) pa[fx] = pa[fy];  // 相等时，把x的代表元素替换成y的代表元素
    else pa[fy] = pa[fx];
    if (rank[fx] == rank[fy]) rank[y]++;  // 所以这里y树的高度(秩)增加
}

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    int[] pa, rank;
    int count = 0;
    int find(int x) {
        return pa[x] == x ? x : (pa[x] = find(pa[x]));
    }
    void union(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return;
        if (rank[fx] <= rank[fy]) pa[fx] = pa[fy];
        else pa[fy] = pa[fx];
        if (rank[fx] == rank[fy]) rank[y]++;
        count++;
    }
}

计算连通性

省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

示例 1：

1
2
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

示例 2：

1
2
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

提示：

  • 1 <= n <= 200
  • n == isConnected.length
  • n == isConnected[i].length
  • isConnected[i][j] 为 1 或 0
  • isConnected[i][i] == 1
  • isConnected[i][j] == isConnected[j][i]

并查集

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
class Solution {
    int[] pa, rank;
    int count = 0;
    int find(int x) {
        return pa[x] == x ? x : (pa[x] = find(pa[x]));
    }
    void union(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return;
        if (rank[fx] <= rank[fy]) pa[fx] = pa[fy];
        else pa[fy] = pa[fx];
        if (rank[fx] == rank[fy]) rank[y]++;
        count++;
    }
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        pa = new int[n]; rank = new int[n];
        for (int i = 0; i < n; i++) pa[i] = i;
        Arrays.fill(rank, 1);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    union(i, j);
                }
            }
        }
        return n - count;
    }
}

计算环的数量

情侣牵手

n 对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手。

人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n-2, 2n-1)。

返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起。 每次交换可选择任意两人，让他们站起来交换座位。

示例 1:

1
2
3
输入: row = [0,2,1,3]
输出: 1
解释: 只需要交换row[1]和row[2]的位置即可。

示例 2:

1
2
3
输入: row = [3,2,0,1]
输出: 0
解释: 无需交换座位，所有的情侣都已经可以手牵手了。

提示:

  • 2n == row.length
  • 2 <= n <= 30
  • n 是偶数
  • 0 <= row[i] < 2n
  • row 中所有元素均无重复

用并查集计算环的数量

环的数量 = n-count

res = 交换数量 = count

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
/**
两对情侣相互坐错了位置，ta们两对之间形成了一个环
 */
class Solution {
    int[] pa, rank;
    int count = 0;
    int find(int x) {
        return pa[x] == x ? x : (pa[x] = find(pa[x]));
    }
    void union(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) return;
        if (rank[fx] <= rank[fy]) pa[fx] = pa[fy];
        else pa[fy] = pa[fx];
        if (rank[fx] == rank[fy]) rank[y]++;
        count++;
    }
    public int minSwapsCouples(int[] row) {
        int n = row.length;
        pa = new int[n];
        rank = new int[n];
        Arrays.setAll(pa, i -> i);
        for (int i = 0; i < n; i+=2) {
            union(row[i]/2, row[i+1]/2);
        }
        return count;
    }
}

在限定条件下，计算连通性

逐步扩张这个条件，获得题目需要的极值

  • [1631. 最小体力消耗路径(1948)]