---
date: 2021-02-07
---


- [是什么](#是什么)
- [初始化](#初始化)
- [查找](#查找)
  - [路径压缩](#路径压缩)
- [合并](#合并)
  - [启发式合并（按秩合并）](#启发式合并按秩合并)
- [时间复杂度及空间复杂度](#时间复杂度及空间复杂度)
  - [时间复杂度](#时间复杂度)
  - [空间复杂度](#空间复杂度)
- [LeetCode 题目](#leetcode-题目)
  - [题目描述](#题目描述)
  - [示例](#示例)
  - [提示](#提示)
  - [题解](#题解)
- [参考资料](#参考资料)


# 是什么

并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的 `合并` 及 `查询` 问题。 它支持两种操作：

查找（Find）：确定某个元素处于哪个子集；
合并（Union）：将两个子集合并成一个集合。

# 初始化

```java
void makeSet(int size) {
  for (int i = 0; i < size; i++) fa[i] = i;  // i就在它本身的集合里
  return;
}
```

# 查找

通俗地讲一个故事：几个家族进行宴会，但是家族普遍长寿，所以人数众多。由于长时间的分离以及年龄的增长，这些人逐渐忘掉了自己的亲人，只记得自己的爸爸是谁了，而最长者（称为「祖先」）的父亲已经去世，他只知道自己是祖先。为了确定自己是哪个家族，他们想出了一个办法，只要问自己的爸爸是不是祖先，一层一层的向上问，直到问到祖先。如果要判断两人是否在同一家族，只要看两人的祖先是不是同一人就可以了。

在这样的思想下，并查集的查找算法诞生了。

此处给出一种 C++ 的参考实现：

```java
int fa[MAXN];  // 记录某个人的爸爸是谁，特别规定，祖先的爸爸是他自己
int find(int x) {
  // 寻找x的祖先
  if (fa[x] == x)  // 如果x是祖先则返回
    return x;
  else
    return find(fa[x]);  // 如果不是则x的爸爸问x的爷爷
}
```

## 路径压缩

这样的确可以达成目的，但是显然效率实在太低。为什么呢？因为我们使用了太多没用的信息，我的祖先是谁与我父亲是谁没什么关系，这样一层一层找太浪费时间，不如我直接当祖先的儿子，问一次就可以出结果了。甚至祖先是谁都无所谓，只要这个人可以代表我们家族就能得到想要的效果。 把在路径上的每个节点都直接连接到根上 ，这就是路径压缩。

此处给出一种 C++ 的参考实现：

```java
int find(int x) {
  if (x != fa[x])  // x不是自身的父亲，即x不是该集合的代表
    fa[x] = find(fa[x]);  // 查找x的祖先直到找到代表,于是顺手路径压缩
  return fa[x];
}
```

![20210207174310](http://yano.oss-cn-beijing.aliyuncs.com/blog/20210207174310.png)

![20210207174318](http://yano.oss-cn-beijing.aliyuncs.com/blog/20210207174318.png)

# 合并

宴会上，一个家族的祖先突然对另一个家族说：我们两个家族交情这么好，不如合成一家好了。另一个家族也欣然接受了。
我们之前说过，并不在意祖先究竟是谁，所以只要其中一个祖先变成另一个祖先的儿子就可以了。

此处给出一种 C++ 的参考实现：

```java
void unionSet(int x, int y) {
  // x 与 y 所在家族合并
  x = find(x);
  y = find(y);
  fa[x] = y;  // 把 x 的祖先变成 y 的祖先的儿子
}
```

## 启发式合并（按秩合并）

一个祖先突然抖了个机灵：「你们家族人比较少，搬家到我们家族里比较方便，我们要是搬过去的话太费事了。」

由于需要我们支持的只有集合的合并、查询操作，当我们需要将两个集合合二为一时，无论将哪一个集合连接到另一个集合的下面，都能得到正确的结果。但不同的连接方法存在时间复杂度的差异。具体来说，如果我们将一棵点数与深度都较小的集合树连接到一棵更大的集合树下，显然相比于另一种连接方案，接下来执行查找操作的用时更小（也会带来更优的最坏时间复杂度）。

# 时间复杂度及空间复杂度

## 时间复杂度

同时使用路径压缩和启发式合并之后，并查集的每个操作平均时间仅为  ，其中  为阿克曼函数的反函数，其增长极其缓慢，也就是说其单次操作的平均运行时间可以认为是一个很小的常数。

Ackermann 函数 A(m,n) 的定义是这样的：

![20210207174552](http://yano.oss-cn-beijing.aliyuncs.com/blog/20210207174552.png)

[时间复杂度证明](https://oi-wiki.org/ds/dsu-complexity/)

## 空间复杂度

O(n)

# LeetCode 题目

[LeetCode 并查集](https://leetcode-cn.com/tag/union-find/)

题目：[547. 省份数量](https://leetcode-cn.com/problems/number-of-provinces/)

## 题目描述

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

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

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

返回矩阵中 省份 的数量。

## 示例

![20210207174912](http://yano.oss-cn-beijing.aliyuncs.com/blog/20210207174912.png)

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

## 提示

    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]

## 题解

```java
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int[] f = new int[isConnected.length];
        for (int i = 0; i < f.length; i++) {
            f[i] = i;
        }

        for (int i = 0; i < isConnected.length; i++) {
            for (int j = 0; j < isConnected.length; j++) {
                // 连通
                if (isConnected[i][j] == 1 && i != j) {
                    unionSet(i, j, f);
                }
            }
        }

        // 计算有多少个相等的
        int result = 0;
        for (int i = 0; i < f.length; i++) {
            if (f[i] == i) {
                result++;
            }
        }
        return result;
    }

    void unionSet(int x, int y, int[] f) {
        f[find(x, f)] = find(y, f);
    }

    int find(int x, int[] f) {
        if (f[x] == x) {
            return x;
        }
        return find(f[x], f);
    }
}
```

# 参考资料

- [OI Wiki 并查集](https://oi-wiki.org/ds/dsu/)