并查集（Union-Find）算法

labuladong约 15706 字大约 52 分钟并查集图论算法数据结构

Info

数据结构精品课open in new window 和递归算法专题课open in new window 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》open in new window 出版，签名版限时半价！

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
130. Surrounded Regionsopen in new window	130. 被围绕的区域open in new window	🟠
323. Number of Connected Components in an Undirected Graphopen in new window🔒	323. 无向图中连通分量的数目open in new window🔒	🟠
990. Satisfiability of Equality Equationsopen in new window	990. 等式方程的可满足性open in new window	🟠

记得我之前在讲图论算法基础时说图论相关的算法不会经常考，但最近被打脸了，因为一些读者和我反馈近期求职面试涉及很多图论相关的算法，可能是因为环境不好所以算法这块更卷了吧。

常见的图论算法我都已经写过了，这里按难度顺序列举一下：

并查集（Union-Find）算法是一个专门针对「动态连通性」的算法，我之前写过两次，因为这个算法的考察频率高，而且它也是最小生成树算法的前置知识，所以我整合了本文，争取一篇文章把这个算法讲明白。

首先，从什么是图的动态连通性开始讲。

一、动态连通性

简单说，动态连通性其实可以抽象成给一幅图连线。比如下面这幅图，总共有 10 个节点，他们互不相连，分别用 0~9 标记：

现在我们的 Union-Find 算法主要需要实现这两个 API：

class UF {
    /* 将 p 和 q 连接 */
    public void union(int p, int q);
    /* 判断 p 和 q 是否连通 */
    public boolean connected(int p, int q);
    /* 返回图中有多少个连通分量 */
    public int count();
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF {
public:
    /* 将 p 和 q 连接 */
    void union(int p, int q);
    /* 判断 p 和 q 是否连通 */
    bool connected(int p, int q);
    /* 返回图中有多少个连通分量 */
    int count();
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF:
    """将 p 和 q 连接"""
    def union(self, p: int, q: int):
        pass

    """判断 p 和 q 是否连通"""
    def connected(self, p: int, q: int) -> bool:
        pass

    """返回图中有多少个连通分量"""
    def count(self) -> int:
        pass

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

type UF struct {
    // 将 p 和 q 连接
    func union(p int, q int)
    // 判断 p 和 q 是否连通
    func connected(p int, q int) bool
    // 返回图中有多少个连通分量
    func count() int
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var UF = function() {
    /* 将 p 和 q 连接 */
    this.union = function(p, q) {};
    /* 判断 p 和 q 是否连通 */
    this.connected = function(p, q) {};
    /* 返回图中有多少个连通分量 */
    this.count = function() {};
};

这里所说的「连通」是一种等价关系，也就是说具有如下三个性质：

1、自反性：节点 p 和 p 是连通的。

2、对称性：如果节点 p 和 q 连通，那么 q 和 p 也连通。

3、传递性：如果节点 p 和 q 连通，q 和 r 连通，那么 p 和 r 也连通。

比如说之前那幅图，0～9 任意两个不同的点都不连通，调用 connected 都会返回 false，连通分量为 10 个。

如果现在调用 union(0, 1)，那么 0 和 1 被连通，连通分量降为 9 个。

再调用 union(1, 2)，这时 0,1,2 都被连通，调用 connected(0, 2) 也会返回 true，连通分量变为 8 个。

判断这种「等价关系」非常实用，比如说编译器判断同一个变量的不同引用，比如社交网络中的朋友圈计算等等。

这样，你应该大概明白什么是动态连通性了，Union-Find 算法的关键就在于 union 和 connected 函数的效率。那么用什么模型来表示这幅图的连通状态呢？用什么数据结构来实现代码呢？

二、基本思路

注意我刚才把「模型」和具体的「数据结构」分开说，这么做是有原因的。因为我们使用森林（若干棵树）来表示图的动态连通性，用数组来具体实现这个森林。

怎么用森林来表示连通性呢？我们设定树的每个节点有一个指针指向其父节点，如果是根节点的话，这个指针指向自己。比如说刚才那幅 10 个节点的图，一开始的时候没有相互连通，就是这样：

class UF {
    // 记录连通分量
    private int count;
    // 节点 x 的父节点是 parent[x]
    private int[] parent;

    /* 构造函数，n 为图的节点总数 */
    public UF(int n) {
        // 一开始互不连通
        this.count = n;
        // 父节点指针初始指向自己
        parent = new int[n];
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    /* 其他函数 */
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF {
    // 记录连通分量
    private:
        int count;
        // 节点 x 的父节点是 parent[x]
        int* parent;

    public:
        /* 构造函数，n 为图的节点总数 */
        UF(int n) {
            // 一开始互不连通
            this->count = n;
            // 父节点指针初始指向自己
            parent = new int[n];
            for (int i = 0; i < n; i++)
                parent[i] = i;
        }

        /* 其他函数 */
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF:
    # 记录连通分量
    def __init__(self, n: int):
        # 一开始互不连通
        self.count = n
        # 父节点指针初始指向自己
        self.parent = [i for i in range(n)]

    # 其他函数

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

type UF struct {
    // 记录连通分量
    count int
    // 节点 x 的父节点是 parent[x]
    parent []int
}

/* 构造函数，n 为图的节点总数 */
func NewUF(n int) *UF {
    // 一开始互不连通
    uf := &UF{count: n, parent: make([]int, n)}
    // 父节点指针初始指向自己
    for i := 0; i < n; i++ {
        uf.parent[i] = i
    }
    return uf
}

/* 其他函数 */

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var UF = function(n) {
    // 记录连通分量
    this.count = n;
    // 节点 x 的父节点是 parent[x]
    this.parent = [];
    // 构造函数，n 为图的节点总数
    for (var i = 0; i < n; i++) {
        // 一开始互不连通
        this.parent[i] = i;
    }
    /* 其他函数 */
}

如果某两个节点被连通，则让其中的（任意）一个节点的根节点接到另一个节点的根节点上：

class UF {
    // 为了节约篇幅，省略上文给出的代码部分...

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;
        // 将两棵树合并为一棵
        parent[rootP] = rootQ;
        // parent[rootQ] = rootP 也一样
        count--; // 两个分量合二为一
    }

    /* 返回某个节点 x 的根节点 */
    private int find(int x) {
        // 根节点的 parent[x] == x
        while (parent[x] != x)
            x = parent[x];
        return x;
    }

    /* 返回当前的连通分量个数 */
    public int count() { 
        return count;
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF {
    // 为了节约篇幅，省略上文给出的代码部分...

public:
    void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;
        // 将两棵树合并为一棵
        parent[rootP] = rootQ;
        // parent[rootQ] = rootP 也一样
        count--; // 两个分量合二为一
    }

    /* 返回某个节点 x 的根节点 */
    int find(int x) {
        // 根节点的 parent[x] == x
        while (parent[x] != x)
            x = parent[x];
        return x;
    }

    /* 返回当前的连通分量个数 */
    int count() {
        return count;
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF:
    # 为了节约篇幅，省略上文给出的代码部分...
  
    def union(self, p: int, q: int) -> None:
        rootP = self.find(p)
        rootQ = self.find(q)
        if rootP == rootQ:
            return
        # 将两棵树合并为一棵
        self.parent[rootP] = rootQ
        # parent[rootQ] = rootP 也一样
        self.count -= 1 # 两个分量合二为一

    """ 返回某个节点 x 的根节点 """
    def find(self, x: int) -> int:
        # 根节点的 parent[x] == x
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    """ 返回当前的连通分量个数 """
    def count(self) -> int:
        return self.count

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

type UF struct {
    // 为了节约篇幅，省略上文给出的代码部分...

	parent []int
    count  int
}

func (uf *UF) union(p int, q int) {
	rootP := uf.find(p)
	rootQ := uf.find(q)
	if rootP == rootQ {
		return
	}
	// 将两棵树合并为一棵
	uf.parent[rootP] = rootQ
	// parent[rootQ] = rootP 也一样
	uf.count-- // 两个分量合二为一
}

/* 返回某个节点 x 的根节点 */
func (uf *UF) find(x int) int {
	// 根节点的 parent[x] == x
	for uf.parent[x] != x {
		x = uf.parent[x]
	}
	return x
}

/* 返回当前的连通分量个数 */
func (uf *UF) count() int {
	return uf.count
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var UF = class {
    // 为了节约篇幅，省略上文给出的代码部分...

    union(p, q) {
        var rootP = this.find(p);
        var rootQ = this.find(q);
        if (rootP === rootQ)
            return;
        // 将两棵树合并为一棵
        this.parent[rootP] = rootQ;
        // parent[rootQ] = rootP 也一样
        this.count--; // 两个分量合二为一
    }

    /* 返回某个节点 x 的根节点 */
    find(x) {
        // 根节点的 parent[x] == x
        while (this.parent[x] !== x)
            x = this.parent[x];
        return x;
    }

    /* 返回当前的连通分量个数 */
    count() {
        return this.count;
    }
}

这样，如果节点 p 和 q 连通的话，它们一定拥有相同的根节点：

class UF {
    // 为了节约篇幅，省略上文给出的代码部分...

    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF {
private:
    // 省略上文给出的代码部分...
    
public:
    bool connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF:
    # 为了节约篇幅，省略上文给出的代码部分...

    def connected(self, p: int, q: int) -> bool:
        root_p = self.find(p)
        root_q = self.find(q)
        return root_p == root_q

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

type UF struct {
    // 为了节约篇幅，省略上文给出的代码部分...
}

func (uf *UF) connected(p int, q int) bool {
    rootP := uf.find(p)
    rootQ := uf.find(q)
    return rootP == rootQ
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var UF = class {
    // 为了节约篇幅，省略上文给出的代码部分...

    connected(p, q) {
        var rootP = find(p);
        var rootQ = find(q);
        return rootP == rootQ;
    }
}

至此，Union-Find 算法就基本完成了。是不是很神奇？竟然可以这样使用数组来模拟出一个森林，如此巧妙的解决这个比较复杂的问题！

那么这个算法的复杂度是多少呢？我们发现，主要 API connected 和 union 中的复杂度都是 find 函数造成的，所以说它们的复杂度和 find 一样。

find 主要功能就是从某个节点向上遍历到树根，其时间复杂度就是树的高度。我们可能习惯性地认为树的高度就是 logN，但这并不一定。logN 的高度只存在于平衡二叉树，对于一般的树可能出现极端不平衡的情况，使得「树」几乎退化成「链表」，树的高度最坏情况下可能变成 N。

所以说上面这种解法，find , union , connected 的时间复杂度都是 O(N)。这个复杂度很不理想的，你想图论解决的都是诸如社交网络这样数据规模巨大的问题，对于 union 和 connected 的调用非常频繁，每次调用需要线性时间完全不可忍受。

问题的关键在于，如何想办法避免树的不平衡呢？只需要略施小计即可。

三、平衡性优化

我们要知道哪种情况下可能出现不平衡现象，关键在于 union 过程：

class UF {
    // 为了节约篇幅，省略上文给出的代码部分...

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;
        // 将两棵树合并为一棵
        parent[rootP] = rootQ;
        // parent[rootQ] = rootP 也可以
        count--;
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF {
    // 为了节约篇幅，省略上文给出的代码部分...

public:
    void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;
        // 将两棵树合并为一棵
        parent[rootP] = rootQ;
        // parent[rootQ] = rootP 也可以
        count--;
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF:
    # 为了节约篇幅，省略上文给出的代码部分...
  
    def union(self, p: int, q: int) -> None:
        rootP = self.find(p)
        rootQ = self.find(q)
        if rootP == rootQ:
            return
        # 将两棵树合并为一棵
        self.parent[rootP] = rootQ
        # self.parent[rootQ] = rootP 也可以
        self.count -= 1

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

type UF struct {
    // 为了节约篇幅，省略上文给出的代码部分...
}

func (uf *UF) union(p int, q int) {
    rootP := uf.find(p)
    rootQ := uf.find(q)
    if rootP == rootQ {
        return
    }
    // 将两棵树合并为一棵
    uf.parent[rootP] = rootQ
    // parent[rootQ] = rootP 也可以
    uf.count--
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var UF = function() {
    // 为了节约篇幅，省略上文给出的代码部分...

    this.union = function(p, q) {
        var rootP = this.find(p);
        var rootQ = this.find(q);
        if (rootP == rootQ)
            return;
        // 将两棵树合并为一棵
        this.parent[rootP] = rootQ;
        // this.parent[rootQ] = rootP 也可以
        this.count--;
    }
}

我们一开始就是简单粗暴的把 p 所在的树接到 q 所在的树的根节点下面，那么这里就可能出现「头重脚轻」的不平衡状况，比如下面这种局面：

长此以往，树可能生长得很不平衡。我们其实是希望，小一些的树接到大一些的树下面，这样就能避免头重脚轻，更平衡一些。解决方法是额外使用一个 size 数组，记录每棵树包含的节点数，我们不妨称为「重量」：

class UF {
    private int count;
    private int[] parent;
    // 新增一个数组记录树的“重量”
    private int[] size;

    public UF(int n) {
        this.count = n;
        parent = new int[n];
        // 最初每棵树只有一个节点
        // 重量应该初始化 1
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    /* 其他函数 */
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF {
private:
    int count;
    int* parent;
    // 新增一个数组记录树的“重量”
    int* size;

public:
    UF(int n) {
        this->count = n;
        parent = new int[n];
        // 最初每棵树只有一个节点
        // 重量应该初始化 1
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    /* 其他函数 */
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF:
    def __init__(self, n: int):
        self.count = n
        self.parent = [i for i in range(n)]
        # 新增一个数组记录树的“重量”
        self.size = [1] * n

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

type UF struct {
    count  int     // 当前连通分量数目
    parent []int   // 存储每个节点的父节点
    size   []int   // 存储根节点对应的树的大小
}

// NewUF 构造函数，n 为图的节点总数
func NewUF(n int) *UF {
    uf := &UF{
        count:  n,
        parent: make([]int, n),
        // 最初每个节点的父节点为它本身，即自己与自己连通
        parent[i] = i
        size:   make([]int, n),
    }
    // 初始化时，每棵树的大小都为 1
    for i := 0; i < n; i++ {
        uf.size[i] = 1
    }
    return uf
}

// 其他方法

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var UF = function(n) {
    this.count = n;
    this.parent = new Array(n);
    this.size = new Array(n);
    for (var i = 0; i < n; i++) {
        this.parent[i] = i;
        this.size[i] = 1;
    }
}
/* 其他函数 */

比如说 size[3] = 5 表示，以节点 3 为根的那棵树，总共有 5 个节点。这样我们可以修改一下 union 方法：

class UF {
    // 为了节约篇幅，省略上文给出的代码部分...

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;
        
        // 小树接到大树下面，较平衡
        if (size[rootP] > size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        count--;
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF {
private:
    // 为了节约篇幅，省略上文给出的代码部分...
public:
    void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;
        
        // 小树接到大树下面，较平衡
        if (size[rootP] > size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        count--;
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF:
    # 为了节约篇幅，省略上文给出的代码部分...

    def union(self, p: int, q: int) -> None:
        rootP = self.find(p)
        rootQ = self.find(q)
        if rootP == rootQ:
            return

        # 小树接到大树下面，较平衡
        if self.size[rootP] > self.size[rootQ]:
            self.parent[rootQ] = rootP
            self.size[rootP] += self.size[rootQ]
        else:
            self.parent[rootP] = rootQ
            self.size[rootQ] += self.size[rootP]
        self.count -= 1

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

type UF struct {
    // 为了节约篇幅，省略上文给出的代码部分...
}

func (uf *UF) union(p int, q int) {
    rootP := uf.find(p)
    rootQ := uf.find(q)
    if rootP == rootQ {
        return
    }

    // 小树接到大树下面，较平衡
    if uf.size[rootP] > uf.size[rootQ] {
        uf.parent[rootQ] = rootP
        uf.size[rootP] += uf.size[rootQ]
    } else {
        uf.parent[rootP] = rootQ
        uf.size[rootQ] += uf.size[rootP]
    }
    uf.count--
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var UF = function(n) {
    // 为了节约篇幅，省略上文给出的代码部分...
}

UF.prototype.union = function(p, q) {
    var rootP = this.find(p);
    var rootQ = this.find(q);
    if (rootP == rootQ)
        return;
    
    // 小树接到大树下面，较平衡
    if (this.size[rootP] > this.size[rootQ]) {
        this.parent[rootQ] = rootP;
        this.size[rootP] += this.size[rootQ];
    } else {
        this.parent[rootP] = rootQ;
        this.size[rootQ] += this.size[rootP];
    }
    this.count--;
}

这样，通过比较树的重量，就可以保证树的生长相对平衡，树的高度大致在 logN 这个数量级，极大提升执行效率。

此时，find , union , connected 的时间复杂度都下降为 O(logN)，即便数据规模上亿，所需时间也非常少。

四、路径压缩

这步优化虽然代码很简单，但原理非常巧妙。

其实我们并不在乎每棵树的结构长什么样，只在乎根节点。

因为无论树长啥样，树上的每个节点的根节点都是相同的，所以能不能进一步压缩每棵树的高度，使树高始终保持为常数？

这样每个节点的父节点就是整棵树的根节点，find 就能以 O(1) 的时间找到某一节点的根节点，相应的，connected 和 union 复杂度都下降为 O(1)。

要做到这一点主要是修改 find 函数逻辑，非常简单，但你可能会看到两种不同的写法。

第一种是在 find 中加一行代码：

class UF {
    // 为了节约篇幅，省略上文给出的代码部分...

    private int find(int x) {
        while (parent[x] != x) {
            // 这行代码进行路径压缩
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF {
    // 为了节约篇幅，省略上文给出的代码部分...

private:
    int find(int x) {
        while (parent[x] != x) {
            // 这行代码进行路径压缩
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF:
    # 为了节约篇幅，省略上文给出的代码部分...

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            # 这行代码进行路径压缩
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

type UF struct {
    // 省略上文给出的代码部分...
}

func (this *UF) find(x int) int {
    for this.parent[x] != x {
        // 这行代码进行路径压缩
        this.parent[x] = this.parent[this.parent[x]]
        x = this.parent[x]
    }
    return x
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var UF = function() {
    // 为了节约篇幅，省略上文给出的代码部分...

    var find = function(x) {
        while (parent[x] !== x) {
            // 这行代码进行路径压缩
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
}

这个操作有点匪夷所思，看个 GIF 就明白它的作用了（为清晰起见，这棵树比较极端）：

用语言描述就是，每次 while 循环都会让部分子节点向上移动，这样每次调用 find 函数向树根遍历的同时，顺手就将树高缩短了。

路径压缩的第二种写法是这样：

class UF {
    // 为了节约篇幅，省略上文给出的代码部分...
    
    // 第二种路径压缩的 find 方法
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF {
    // 为了节约篇幅，省略上文给出的代码部分...
    
    // 第二种路径压缩的 find 方法
    public:
        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF:
    # 省略上文的代码部分
    
    # 第二种路径压缩的 find 方法
    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

type UF struct {
    // 省略上文给出的代码部分...
}

// 第二种路径压缩的 find 方法
func (uf *UF) find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.find(uf.parent[x])
    }
    return uf.parent[x]
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var UF = function() {
    // 为了节约篇幅，省略上文给出的代码部分...
    
    // 第二种路径压缩的 find 方法
    this.find = function(x) {
        if (this.parent[x] != x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }
}

我一度认为这种递归写法和第一种迭代写法做的事情一样，但实际上是我大意了，有读者指出这种写法进行路径压缩的效率是高于上一种解法的。

这个递归过程有点不好理解，你可以自己手画一下递归过程。我把这个函数做的事情翻译成迭代形式，方便你理解它进行路径压缩的原理：

// 这段迭代代码方便你理解递归代码所做的事情
public int find(int x) {
    // 先找到根节点
    int root = x;
    while (parent[root] != root) {
        root = parent[root];
    }
    // 然后把 x 到根节点之间的所有节点直接接到根节点下面
    int old_parent = parent[x];
    while (x != root) {
        parent[x] = root;
        x = old_parent;
        old_parent = parent[old_parent];
    }
    return root;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 这段迭代代码方便你理解递归代码所做的事情
int find(int x) {
    // 先找到根节点
    int root = x;
    while (parent[root] != root) {
        root = parent[root];
    }
    // 然后把 x 到根节点之间的所有节点直接接到根节点下面
    int old_parent = parent[x];
    while (x != root) {
        parent[x] = root;
        x = old_parent;
        old_parent = parent[old_parent];
    }
    return root;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

# 这段迭代代码方便你理解递归代码所做的事情
def find(x: int) -> int:
    # 先找到根节点
    root = x
    while parent[root] != root:
        root = parent[root]
    
    # 然后把 x 到根节点之间的所有节点直接接到根节点下面
    old_parent = parent[x]
    while x != root:
        parent[x] = root
        x = old_parent
        old_parent = parent[old_parent]
    
    return root

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 这段迭代代码方便你理解递归代码所做的事情
func find(x int) int {
    // 先找到根节点
    root := x
    for parent[root] != root {
        root = parent[root]
    }
    // 然后把 x 到根节点之间的所有节点直接接到根节点下面
    old_parent := parent[x]
    for x != root {
        parent[x] = root
        x = old_parent
        old_parent = parent[old_parent]
    }
    return root
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 这段迭代代码方便你理解递归代码所做的事情
var find = function(x) {
    // 先找到根节点
    var root = x;
    while (parent[root] !== root) {
        root = parent[root];
    }
    // 然后把 x 到根节点之间的所有节点直接接到根节点下面
    var old_parent = parent[x];
    while (x !== root) {
        parent[x] = root;
        x = old_parent;
        old_parent = parent[old_parent];
    }
    return root;
};

这种路径压缩的效果如下：

比起第一种路径压缩，显然这种方法压缩得更彻底，直接把一整条树枝压平，一点意外都没有。就算一些极端情况下产生了一棵比较高的树，只要一次路径压缩就能大幅降低树高，从摊还分析的角度来看，所有操作的平均时间复杂度依然是 O(1)，所以从效率的角度来说，推荐你使用这种路径压缩算法。

另外，如果使用路径压缩技巧，那么 size 数组的平衡优化就不是特别必要了。所以你一般看到的 Union Find 算法应该是如下实现：

class UF {
    // 连通分量个数
    private int count;
    // 存储每个节点的父节点
    private int[] parent;

    // n 为图中节点的个数
    public UF(int n) {
        this.count = n;
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    // 将节点 p 和节点 q 连通
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        
        if (rootP == rootQ)
            return;
        
        parent[rootQ] = rootP;
        // 两个连通分量合并成一个连通分量
        count--;
    }

    // 判断节点 p 和节点 q 是否连通
    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // 返回图中的连通分量个数
    public int count() {
        return count;
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF {
private:
    // 连通分量个数
    int count;
    // 存储每个节点的父节点
    int *parent;

public:
    // n 为图中节点的个数
    UF(int n) {
        this->count = n;
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    // 将节点 p 和节点 q 连通
    void union_(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        
        if (rootP == rootQ)
            return;
        
        parent[rootQ] = rootP;
        // 两个连通分量合并成一个连通分量
        count--;
    }

    // 判断节点 p 和节点 q 是否连通
    bool connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // 返回图中的连通分量个数
    int count_() {
        return count;
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class UF:
    # 连通分量个数
    count: int
    # 存储每个节点的父节点
    parent: List[int]

    # n 为图中节点的个数
    def __init__(self, n: int):
        self.count = n
        self.parent = [i for i in range(n)]

    # 将节点 p 和节点 q 连通
    def union(self, p: int, q: int):
        rootP = self.find(p)
        rootQ = self.find(q)

        if rootP == rootQ:
            return

        self.parent[rootQ] = rootP
        # 两个连通分量合并成一个连通分量
        self.count -= 1

    # 判断节点 p 和节点 q 是否连通
    def connected(self, p: int, q: int) -> bool:
        rootP = self.find(p)
        rootQ = self.find(q)
        return rootP == rootQ

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    # 返回图中的连通分量个数
    def count(self) -> int:
        return self.count

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

type UF struct {
    // 连通分量个数
    count int
    // 存储每个节点的父节点
    parent []int
}

// n 为图中节点的个数
func NewUF(n int) *UF {
    parent := make([]int, n)
    for i := 0; i < n; i++ {
        parent[i] = i
    }
    return &UF{
        count:  n,
        parent: parent,
    }
}

// 将节点 p 和节点 q 连通
func (u *UF) Union(p, q int) {
    rootP := u.Find(p)
    rootQ := u.Find(q)

    if rootP == rootQ {
        return
    }

    u.parent[rootQ] = rootP
    // 两个连通分量合并成一个连通分量
    u.count--
}

// 判断节点 p 和节点 q 是否连通
func (u *UF) Connected(p, q int) bool {
    rootP := u.Find(p)
    rootQ := u.Find(q)
    return rootP == rootQ
}

func (u *UF) Find(x int) int {
    if u.parent[x] != x {
        u.parent[x] = u.Find(u.parent[x])
    }
    return u.parent[x]
}

// 返回图中的连通分量个数
func (u *UF) Count() int {
    return u.count
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 定义 UF 类
var UF = function(n) {
    // 连通分量个数
    this.count = n;
    // 存储每个节点的父节点
    this.parent = [];
    
    // n 为图中节点的个数
    for (var i = 0; i < n; i++) {
        this.parent[i] = i;
    }
}

// 将节点 p 和节点 q 连通
UF.prototype.union = function(p, q) {
    var rootP = this.find(p);
    var rootQ = this.find(q);
    
    if (rootP == rootQ)
        return;
    
    this.parent[rootQ] = rootP;
    // 两个连通分量合并成一个连通分量
    this.count--;
}

// 判断节点 p 和节点 q 是否连通
UF.prototype.connected = function(p, q) {
    var rootP = this.find(p);
    var rootQ = this.find(q);
    return rootP == rootQ;
}

// 找到节点 x 所在的连通分量
UF.prototype.find = function(x) {
    if (this.parent[x] != x) {
        this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
}

// 返回图中的连通分量个数
UF.prototype.count = function() {
    return this.count;
}

Union-Find 算法的复杂度可以这样分析：构造函数初始化数据结构需要 O(N) 的时间和空间复杂度；连通两个节点 union、判断两个节点的连通性 connected、计算连通分量 count 所需的时间复杂度均为 O(1)。

到这里，相信你已经掌握了 Union-Find 算法的核心逻辑，总结一下我们优化算法的过程：

1、用 parent 数组记录每个节点的父节点，相当于指向父节点的指针，所以 parent 数组内实际存储着一个森林（若干棵多叉树）。

2、用 size 数组记录着每棵树的重量，目的是让 union 后树依然拥有平衡性，保证各个 API 时间复杂度为 O(logN)，而不会退化成链表影响操作效率。

3、在 find 函数中进行路径压缩，保证任意树的高度保持在常数，使得各个 API 时间复杂度为 O(1)。使用了路径压缩之后，可以不使用 size 数组的平衡优化。

下面我们看一些具体的并查集题目。

题目实践

力扣第 323 题「无向图中连通分量的数目open in new window」就是最基本的连通分量题目：

给你输入一个包含 n 个节点的图，用一个整数 n 和一个数组 edges 表示，其中 edges[i] = [ai, bi] 表示图中节点 ai 和 bi 之间有一条边。请你计算这幅图的连通分量个数。

函数签名如下：

int countComponents(int n, int[][] edges)

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

int countComponents(int n, vector<vector<int>>& edges)

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def countComponents(n: int, edges: List[List[int]]) -> int:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func countComponents(n int, edges [][]int) int {}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var countComponents = function(n, edges) {

};

这道题我们可以直接套用 UF 类来解决：

public int countComponents(int n, int[][] edges) {
    UF uf = new UF(n);
    // 将每个节点进行连通
    for (int[] e : edges) {
        uf.union(e[0], e[1]);
    }
    // 返回连通分量的个数
    return uf.count();
}

class UF {
    // 见上文
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

int countComponents(int n, vector<vector<int>>& edges) {
    UF uf(n);
    // 将每个节点进行连通
    for (const auto& e : edges) {
        uf.Union(e[0], e[1]);
    }
    // 返回连通分量的个数
    return uf.Count();
}

class UF {
    // 见上文
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def countComponents(n: int, edges: List[List[int]]) -> int:
    class UF:
        def __init__(self, n):
            self.count = n
            self.parent = [i for i in range(n)]
            self.rank = [0] * n

        def find(self, p: int) -> int:
            # 路径压缩
            while p != self.parent[p]:
                self.parent[p] = self.parent[self.parent[p]]
                p = self.parent[p]
            return p

        def union(self, p: int, q: int) -> None:
            # 按秩合并
            rootP, rootQ = self.find(p), self.find(q)
            if rootP == rootQ:
                return
            if self.rank[rootP] < self.rank[rootQ]:
                self.parent[rootP] = rootQ
            elif self.rank[rootP] > self.rank[rootQ]:
                self.parent[rootQ] = rootP
            else:
                self.parent[rootQ] = rootP
                self.rank[rootP] += 1
            self.count -= 1

    # 建立 n 个多个点组成的连通分量
    uf = UF(n)
    for e in edges:
        # 将每对节点进行连通
        uf.union(e[0], e[1])
    # 返回连通分量的个数
    return uf.count

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func countComponents(n int, edges [][]int) int {
    uf := NewUF(n)
  // 将每个节点进行连通
    for _, e := range edges {
        uf.Union(e[0], e[1])
    }
  // 返回连通分量的个数
    return uf.count()
}

type UF struct {
	// 见上文
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var countComponents = function(n, edges) {
    /**
     * @param {number} n
     * @return {void}
     */
    class UF {
        constructor(n) {
            // 初始化，parent 数组指向自身
            this.parent = new Array(n).fill(0).map((_, i) => i);
            // rank 数组初始化为 0
            this.rank = new Array(n).fill(0);
            // 集合数量
            this.count = n;
        }

        /**
         * 查找根节点
         * @param {number} p
         * @return {number}
         */
        find(p) {
            let root = p;
            // 循环查找根节点
            while (root !== this.parent[root]) {
                root = this.parent[root];
            }

            // 压缩路径，把当前节点指向根节点，优化树高
            while (p !== root) {
                let next = this.parent[p];
                this.parent[p] = root;
                p = next;
            }

            return root;
        }

        /**
         * 合并两个集合
         * @param {number} p
         * @param {number} q
         * @return {void}
         */
        union(p, q) {
            let rootP = this.find(p);
            let rootQ = this.find(q);
            // 如果两个节点已经在同一个连通分量内，不用合并
            if (rootP === rootQ) {
                return;
            }

            // 根据树高，优化合并性能，避免树变的很高
            if (this.rank[rootP] > this.rank[rootQ]) {
                this.parent[rootQ] = rootP;
            } else if (this.rank[rootP] < this.rank[rootQ]) {
                this.parent[rootP] = rootQ;
            } else {
                this.parent[rootQ] = rootP;
                this.rank[rootP]++;
            }

            this.count--;
        }

        /**
         * 获取集合个数
         * @return {number}
         */
        getCount() {
            return this.count;
        }

    }

    let uf = new UF(n);
    // 构建连通分量
    for (let e of edges) {
        uf.union(e[0], e[1])
    }

    // 返回集合数量
    return uf.getCount();
};

另外，一些使用 DFS 深度优先算法解决的问题，也可以用 Union-Find 算法解决。

比如力扣第 130 题「被围绕的区域open in new window」：

给你一个 M×N 的二维矩阵，其中包含字符 X 和 O，让你找到矩阵中四面被 X 围住的 O，并且把它们替换成 X。

void solve(char[][] board);

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

void solve(vector<vector<char>>& board);

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def solve(board: List[List[str]]) -> None:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func solve(board [][]byte) {}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

function solve(board) {
  // function body here
}

注意哦，必须是四面被围的 O 才能被换成 X，也就是说边角上的 O 一定不会被围，进一步，与边角上的 O 相连的 O 也不会被 X 围四面，也不会被替换。

Note

这让我想起小时候玩的棋类游戏「黑白棋」，只要你用两个棋子把对方的棋子夹在中间，对方的子就被替换成你的子。可见，占据四角的棋子是无敌的，与其相连的边棋子也是无敌的（无法被夹掉）。

其实这个问题应该归为岛屿系列问题使用 DFS 算法解决：

先用 for 循环遍历棋盘的四边，用 DFS 算法把那些与边界相连的 O 换成一个特殊字符，比如 #；然后再遍历整个棋盘，把剩下的 O 换成 X，把 # 恢复成 O。这样就能完成题目的要求，时间复杂度 O(MN)。

但这个问题也可以用 Union-Find 算法解决，虽然实现复杂一些，甚至效率也略低，但这是使用 Union-Find 算法的通用思想，值得一学。

你可以把那些不需要被替换的 O 看成一个拥有独门绝技的门派，它们有一个共同「祖师爷」叫 dummy，这些 O 和 dummy 互相连通，而那些需要被替换的 O 与 dummy 不连通。

这就是 Union-Find 的核心思路，明白这个图，就很容易看懂代码了。

首先要解决的是，根据我们的实现，Union-Find 底层用的是一维数组，构造函数需要传入这个数组的大小，而题目给的是一个二维棋盘。

这个很简单，二维坐标 (x,y) 可以转换成 x * n + y 这个数（m 是棋盘的行数，n 是棋盘的列数），敲黑板，这是将二维坐标映射到一维的常用技巧。

其次，我们之前描述的「祖师爷」是虚构的，需要给他老人家留个位置。索引 [0.. m*n-1] 都是棋盘内坐标的一维映射，那就让这个虚拟的 dummy 节点占据索引 m * n 好了。

看解法代码：

void solve(char[][] board) {
    if (board.length == 0) return;

    int m = board.length;
    int n = board[0].length;
    // 给 dummy 留一个额外位置
    UF uf = new UF(m * n + 1);
    int dummy = m * n;
    // 将首列和末列的 O 与 dummy 连通
    for (int i = 0; i < m; i++) {
        if (board[i][0] == 'O')
            uf.union(i * n, dummy);
        if (board[i][n - 1] == 'O')
            uf.union(i * n + n - 1, dummy);
    }
    // 将首行和末行的 O 与 dummy 连通
    for (int j = 0; j < n; j++) {/**<extend up -150><div class="img-content"><img src="/algo/images/unionfind应用/3.jpg" class="myimage"/></div> */
        if (board[0][j] == 'O')
            uf.union(j, dummy);
        if (board[m - 1][j] == 'O')
            uf.union(n * (m - 1) + j, dummy);
    }
    // 方向数组 d 是上下左右搜索的常用手法
    int[][] d = new int[][]{{1,0}, {0,1}, {0,-1}, {-1,0}};
    for (int i = 1; i < m - 1; i++) 
        for (int j = 1; j < n - 1; j++) 
            if (board[i][j] == 'O')
                // 将此 O 与上下左右的 O 连通
                for (int k = 0; k < 4; k++) {
                    int x = i + d[k][0];
                    int y = j + d[k][1];
                    if (board[x][y] == 'O')
                        uf.union(x * n + y, i * n + j);
                }
    // 所有不和 dummy 连通的 O，都要被替换
    for (int i = 1; i < m - 1; i++) 
        for (int j = 1; j < n - 1; j++) 
            if (!uf.connected(dummy, i * n + j))
                board[i][j] = 'X';
}

class UF {
    // 见上文
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

void solve(vector<vector<char>>& board) {
    if(board.empty()) return;

    int m = board.size();
    int n = board[0].size();

    //给dummy留一个额外位置
    UF uf(m*n+1);//引用UF类
    int dummy = m*n;
    //将首列和末列的O与dummy相连
    for (int i = 0; i < m; i++) {
        if (board[i][0] == 'O') {
            uf._union(i * n, dummy);
        }
        if (board[i][n - 1] == 'O') {
            uf._union(i * n + n - 1, dummy);
        }
    }

    //将首行和末行的O与dummy相连
    for (int j = 0; j < n; j++) {
        if (board[0][j] == 'O') {
            uf._union(j, dummy);
        }
        if (board[m - 1][j] == 'O') {
            uf._union(n * (m - 1) + j, dummy);
        }
    }

    //方向数组 d 是上下左右搜索的常用手法
    int d[4][2] = {{1,0}, {0,1}, {0,-1}, {-1,0}};
    for (int i = 1; i < m - 1; i++) {
        for (int j = 1; j < n - 1; j++) {
            if (board[i][j] == 'O') {
                //将此 O 与上下左右的 O 相连
                for (int k = 0; k < 4; k++) {
                    int x = i + d[k][0];
                    int y = j + d[k][1];

                    if (board[x][y] == 'O') {
                        uf._union(x * n + y, i * n + j);
                    }
                }
            }
        }
    }

    //所有不和dummy相连的O，都要被替换
    for (int i = 1; i < m - 1; i++) {
        for (int j = 1; j < n - 1; j++) {
            if(!uf.isConnected(dummy, i*n+j)) {
                board[i][j] = 'X';
            }
        }
    }
}

class UF {
    vector<int> parent;
public:
    UF(int n) {
        for (int i = 0; i < n; i++) {
            parent.push_back(i);
        }
    }

    int find(int x) {
        if(x!=parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void _union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if(rootX!=rootY) {
            parent[rootX] = rootY;
        }
    }

    bool isConnected(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        return rootX==rootY;
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def solve(board: List[List[str]]) -> None:
    if not board:
        return

    m = len(board)
    n = len(board[0])
    # 给 dummy 留一个额外位置
    uf = UF(m * n + 1)
    dummy = m * n
    # 将首列和末列的 O 与 dummy 连通
    for i in range(m):
        if board[i][0] == 'O':
            uf.union(i * n, dummy)
        if board[i][n - 1] == 'O':
            uf.union(i * n + n - 1, dummy)
    # 将首行和末行的 O 与 dummy 连通
    for j in range(n):
        if board[0][j] == 'O':
            uf.union(j, dummy)
        if board[m - 1][j] == 'O':
            uf.union(n * (m - 1) + j, dummy)
    # 方向数组 d 是上下左右搜索的常用手法
    d = [[1, 0], [0, 1], [0, -1], [-1, 0]]
    for i in range(1, m - 1):
        for j in range(1, n - 1):
            if board[i][j] == 'O':
                # 将此 O 与上下左右的 O 连通
                for k in range(4):
                    x = i + d[k][0]
                    y = j + d[k][1]
                    if board[x][y] == 'O':
                        uf.union(x * n + y, i * n + j)
    # 所有不和 dummy 连通的 O，都要被替换
    for i in range(1, m - 1):
        for j in range(1, n - 1):
            if not uf.connected(dummy, i * n + j):
                board[i][j] = 'X'


class UF:
    # 见上文
    pass

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func solve(board [][]byte) {
    if len(board) == 0 {
        return
    }

    m := len(board)
    n := len(board[0])
    // 给 dummy 留一个额外位置
    uf := NewUF(m*n + 1)
    dummy := m*n
    // 将首列和末列的 O 与 dummy 连通
    for i := 0; i < m; i++ {
        if board[i][0] == 'O' {
            uf.Union(i*n, dummy)
        }
        if board[i][n-1] == 'O' {
            uf.Union(i*n+n-1, dummy)
        }
    }
    // 将首行和末行的 O 与 dummy 连通
    for j := 0; j < n; j++ {
        if board[0][j] == 'O' {
            uf.Union(j, dummy)
        }
        if board[m-1][j] == 'O' {
            uf.Union(n*(m-1)+j, dummy)
        }
    }
    // 方向数组 d 是上下左右搜索的常用手法
    d := [][]int{{1, 0}, {0, 1}, {0, -1}, {-1, 0}}
    for i := 1; i < m-1; i++ {
        for j := 1; j < n-1; j++ {
            if board[i][j] == 'O' {
                // 将此 O 与上下左右的 O 连通
                for k := 0; k < 4; k++ {
                    x := i + d[k][0]
                    y := j + d[k][1]
                    if board[x][y] == 'O' {
                        uf.Union(x*n+y, i*n+j)
                    }
                }
            }
        }
    }
    // 所有不和 dummy 连通的 O，都要被替换
    for i := 1; i < m-1; i++ {
        for j := 1; j < n-1; j++ {
            if !uf.Connected(dummy, i*n+j) {
                board[i][j] = 'X'
            }
        }
    }
}

type UF struct {
    // 见上文
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var solve = function(board) {
    if (board.length === 0) return;
    var m = board.length;
    var n = board[0].length;
    var uf = new UF(m * n + 1);
    var dummy = m * n;
    for (var i = 0; i < m; i++) {
        if (board[i][0] === 'O')
            uf.union(i * n, dummy);
        if (board[i][n - 1] === 'O')
            uf.union(i * n + n - 1, dummy);
    }
    for (var j = 0; j < n; j++) {
        if (board[0][j] === 'O')
            uf.union(j, dummy);
        if (board[m - 1][j] === 'O')
            uf.union(n * (m - 1) + j, dummy);
    }
    var d = [[1,0], [0,1], [0,-1], [-1,0]];
    for (var i = 1; i < m - 1; i++) 
        for (var j = 1; j < n - 1; j++) 
            if (board[i][j] === 'O')
                for (var k = 0; k < 4; k++) {
                    var x = i + d[k][0];
                    var y = j + d[k][1];
                    if (board[x][y] === 'O')
                        uf.union(x * n + y, i * n + j);
                }
    for (var i = 1; i < m - 1; i++) 
        for (var j = 1; j < n - 1; j++) 
            if (!uf.connected(dummy, i * n + j))
                board[i][j] = 'X';
};

var UF = function() {
    // 见上文
};

这段代码很长，其实就是刚才的思路实现，只有和边界 O 相连的 O 才具有和 dummy 的连通性，他们不会被替换。

其实用 Union-Find 算法解决这个简单的问题有点杀鸡用牛刀，它可以解决更复杂，更具有技巧性的问题，主要思路是适时增加虚拟节点，想办法让元素「分门别类」，建立动态连通关系。

力扣第 990 题「等式方程的可满足性open in new window」用 Union-Find 算法就显得十分优美了，题目是这样：

给你一个数组 equations，装着若干字符串表示的算式。每个算式 equations[i] 长度都是 4，而且只有这两种情况：a==b 或者 a!=b，其中 a,b 可以是任意小写字母。你写一个算法，如果 equations 中所有算式都不会互相冲突，返回 true，否则返回 false。

比如说，输入 ["a==b","b!=c","c==a"]，算法返回 false，因为这三个算式不可能同时正确。

再比如，输入 ["c==c","b==d","x!=z"]，算法返回 true，因为这三个算式并不会造成逻辑冲突。

我们前文说过，动态连通性其实就是一种等价关系，具有「自反性」「传递性」和「对称性」，其实 == 关系也是一种等价关系，具有这些性质。所以这个问题用 Union-Find 算法就很自然。

核心思想是，将 equations 中的算式根据 == 和 != 分成两部分，先处理 == 算式，使得他们通过相等关系各自勾结成门派（连通分量）；然后处理 != 算式，检查不等关系是否破坏了相等关系的连通性。

boolean equationsPossible(String[] equations) {
    // 26 个英文字母
    UF uf = new UF(26);
    // 先让相等的字母形成连通分量
    for (String eq : equations) {
        if (eq.charAt(1) == '=') {
            char x = eq.charAt(0);
            char y = eq.charAt(3);
            uf.union(x - 'a', y - 'a');
        }
    }
    // 检查不等关系是否打破相等关系的连通性
    for (String eq : equations) {
        if (eq.charAt(1) == '!') {
            char x = eq.charAt(0);
            char y = eq.charAt(3);
            // 如果相等关系成立，就是逻辑冲突
            if (uf.connected(x - 'a', y - 'a'))
                return false;
        }
    }
    return true;
}

class UF {
    // 见上文
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

bool equationsPossible(vector<string>& equations) {
    UF uf(26);
    for (const string& eq : equations) {
        if (eq[1] == '=') {
            char x = eq[0];
            char y = eq[3];
            uf._union(x - 'a', y - 'a');
        }
    }
    for (const string& eq : equations) {
        if (eq[1] == '!') {
            char x = eq[0];
            char y = eq[3];
            if (uf.connected(x - 'a', y - 'a')) {
                return false;
            }
        }
    }
    return true;
}

class UF {
    // 见上文
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def equationsPossible(equations: List[str]) -> bool:
    class UF:
        def __init__(self, n: int):
            self.parent = list(range(n))
            self.size = [1] * n

        def find(self, x: int) -> int:
            if self.parent[x] != x:
                self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

        def union(self, x: int, y: int) -> None:
            root_x, root_y = self.find(x), self.find(y)
            if root_x == root_y:
                return
            if self.size[root_x] < self.size[root_y]:
                root_x, root_y = root_y, root_x
            self.parent[root_y] = root_x
            self.size[root_x] += self.size[root_y]

        def connected(self, x: int, y: int) -> bool:
            return self.find(x) == self.find(y)

    uf = UF(26)  # 26 个英文字母
    # 先让相等的字母形成连通分量
    for eq in equations:
        if eq[1] == '=':
            x, y = eq[0], eq[3]
            uf.union(ord(x) - ord('a'), ord(y) - ord('a'))
    # 检查不等关系是否打破相等关系的连通性
    for eq in equations:
        if eq[1] == '!':
            x, y = eq[0], eq[3]
            # 如果相等关系成立，就是逻辑冲突
            if uf.connected(ord(x) - ord('a'), ord(y) - ord('a')):
                return False
    return True

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func equationsPossible(equations []string) bool {
    // 26 个英文字母
    uf := Constructor(26)
    // 先让相等的字母形成连通分量
    for _, eq := range equations {
        if eq[1] == '=' {
            x := eq[0]
            y := eq[3]
            uf.Union(int(x-'a'), int(y-'a'))
        }
    }
    // 检查不等关系是否打破相等关系的连通性
    for _, eq := range equations {
        if eq[1] == '!' {
            x := eq[0]
            y := eq[3]
            // 如果相等关系成立，就是逻辑冲突
            if uf.Find(int(x-'a')) == uf.Find(int(y-'a')) {
                return false
            }
        }
    }
    return true
}

type UF struct {
    // 见上文
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var equationsPossible = function(equations) {
    class UF {
        // 见上文
    }

    // 26 个英文字母
    let uf = new UF(26);

    // 先让相等的字母形成连通分量
    for (let eq of equations) {
        if (eq.charAt(1) == '=') {
            let x = eq.charAt(0);
            let y = eq.charAt(3);
            uf.union(x - 'a', y - 'a');
        }
    }

    // 检查不等关系是否打破相等关系的连通性
    for (let eq of equations) {
        if (eq.charAt(1) == '!') {
            let x = eq.charAt(0);
            let y = eq.charAt(3);

            // 如果相等关系成立，就是逻辑冲突
            if (uf.connected(x - 'a', y - 'a')) {
                return false;
            }
        }
    }
    return true;
};

至此，这道判断算式合法性的问题就解决了，借助 Union-Find 算法，是不是很简单呢？

最后，Union-Find 算法也会在一些其他经典图论算法中用到，比如判断「图」和「树」，以及最小生成树的计算，详情见 Kruskal 最小生成树算法。

引用本文的文章

Dijkstra 算法模板及应用 Kruskal 最小生成树算法 Prim 最小生成树算法一文秒杀所有岛屿题目二分图判定算法我的刷题心得用算法打败算法

引用本文的题目

安装我的 Chrome 刷题插件open in new window 点开下列题目可直接查看解题思路：

LeetCode	力扣
1361. Validate Binary Tree Nodesopen in new window	1361. 验证二叉树open in new window
200. Number of Islandsopen in new window	200. 岛屿数量open in new window
261. Graph Valid Treeopen in new window🔒	261. 以图判树open in new window🔒
310. Minimum Height Treesopen in new window	310. 最小高度树open in new window
368. Largest Divisible Subsetopen in new window	368. 最大整除子集open in new window
582. Kill Processopen in new window🔒	582. 杀掉进程open in new window🔒
765. Couples Holding Handsopen in new window	765. 情侣牵手open in new window
947. Most Stones Removed with Same Row or Columnopen in new window	947. 移除最多的同行或同列石头open in new window

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释

# 一、动态连通性

# 二、基本思路

# 三、平衡性优化

# 四、路径压缩

# 题目实践

一、动态连通性

二、基本思路

三、平衡性优化

四、路径压缩

题目实践