简介

并查集（Union-Find）是一种树形的数据结构，用于处理一些不相交集合的合并及查询问题。从它的名字“并查”可以知道它包含了两个操作：合并和查找。

合并：将两个不相交集合合并成同一个集合。

查找：确定元素属于哪一个集合。一般来说，一个集合用一个元素作为代表（树的根），当前元素通过不断地向上查找，最终找到当前集合的代表（树的根），也就可以确定所在集合了。

用数据结构来实现并查操作

初始化

假设有 N 个元素，在初始情况下，每个元素都属于不同的集合。也就是说，每个元素都代表了各自的集合（都为根节点）。

同时定义一个长度为 N 的数值 parent，parent[i] 表示第 i 个元素的父节点，由于一开始每个元素都是各自集合的根节点，所以没有父节点，没有父节点的情况下置为 -1。

代码实现如下（本文代码编写所使用的语言皆为 Java）：

int[] parent = new int[N];
for (int i = 0; i < N; i++) {
    parent[i] = -1;
}

查找

找到元素所属的集合，这里使用一个元素来代表整个集合，返回该代表元素的索引。具体代码实现如下：

/**
 * 返回 parent[i] 元素所属的集合（代表元素的索引）
 */
private int find(int[] parent, int i) {
    while (parent[i] != -1) {
        i = parent[i];
    }
    return i;
}

合并

合并两个不相交的集合。在合并之前，先得到两个元素所属集合（借助上面的 find 操作），如果发现属于同一集合就不用合并了。否则就将其中一个代表的父节点置为另一个代表（即将一个集合并入另一个集合）。具体代码实现如下：

/**
 * 合并 parent[x] 和 parent[y] 所属集合
 */
private void union(int[] parent, int x, int y) {
    int xSet = find(parent, x);
    int ySet = find(parent, y);
    if (xSet != ySet) {
        parent[xSet] = ySet;
    }
}

优化

按秩合并

在合并的时候，总是将更小的树连接到各大的树上。这里的“秩”可以指代树的深度（两者不一定完全相等，在结合另一种优化“路径压缩”的时候，两者可能不同），影响运行时间的一个因素是树的深度，而将更小的树添加到更大的树时将不会增加它们的秩，除非它们的秩相同。

单个节点的秩定义为 0，两棵秩同为 r 的树，合并后秩为 r+1。可以使用一个 rank 数组来表示每个节点的秩。优化后新的 union 方法如下：

int[] rank = new int[N];

/**
 * 合并 parent[x] 和 parent[y] 所属集合
 */
private void union(int[] parent, int[] rank, int x, int y) {
    int xSet = find(parent, x);
    int ySet = find(parent, y);
    if (xSet == ySet) {
        return;
    }
    if (rank[xSet] > rank[ySet]) {
        parent[ySet] = xSet;
    } else if (rank[ySet] > rank[xSet]) {
        parent[xSet] = ySet;
    } else {
        parent[ySet] = xSet;
        rank[xSet]++;
    }
}

路径压缩

路径压缩是一种在“查找”时扁平化树结构的方法，对于当前节点向上直到根节点的这条路径的所有节点（根节点除外），在找到根节点后，都可以将它们的父节点置为根节点，这样的话，以后这些节点在查找时就可以加快速度。

优化后的 find 方法如下：

/**
 * 返回 parent[i] 元素所属的集合（代表元素的索引）
 */
private int find(int[] parent, int i) {
    // 保存当前节点
    int temp = i;
    while (parent[i] != -1) {
        i = parent[i];
    }
    // 将从当前节点到根节点路径的所有节点的父节点置为根节点
    while (parent[temp] != -1) {
        int next = parent[temp];
        parent[temp] = i;
        temp = next;
    }
    // 返回根节点的索引
    return i;
}

应用

LeetCode 第 547 题：朋友圈

题目描述

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果 M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例

示例 1：

输入: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
输出: 2 
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。

示例 2：

输入: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。

注意

N 在[1,200]的范围内。
对于所有学生，有M[i][i] = 1。
如果有M[i][j] = 1，则有M[j][i] = 1。

代码实现

public int findCircleNum(int[][] M) {
    int N = M.length;     // 人数
    // 开始时，假设每个同学各自为一个集合
    int[] parent = new int[N];
    int[] rank = new int[N];
    for (int i = 0; i < N; i++) {
        parent[i] = -1;
    }
    // 合并有朋友关系的集合
    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            if (M[i][j] == 1) {
                // 合并 i 和 j 所属集合
                union(parent, rank, i, j);
            }
        }
    }
    // 最后判断集合个数，即查找 parent[i] == -1 的元素个数
    int count = 0;
    for (int i = 0; i < N; i++) {
        if (parent[i] == -1) {
            count++;
        }
    }

    return count;
}

private int find(int[] parent, int i) {
    // 保存当前节点
    int temp = i;
    while (parent[i] != -1) {
        i = parent[i];
    }
    // 将从当前节点到根节点路径的所有节点的父节点置为根节点
    while (parent[temp] != -1) {
        int next = parent[temp];
        parent[temp] = i;
        temp = next;
    }
    // 返回根节点的索引
    return i;
}

private void union(int[] parent, int[] rank, int x, int y) {
    int xSet = find(parent, x);
    int ySet = find(parent, y);
    if (xSet == ySet) {
        return;
    }
    if (rank[xSet] > rank[ySet]) {
        parent[ySet] = xSet;
    } else if (rank[ySet] > rank[xSet]) {
        parent[xSet] = ySet;
    } else {
        parent[ySet] = xSet;
        rank[xSet]++;
    }
}

附上优化前和优化后（2 ms 的是优化后的）两次在 LeetCode 提交的时间对比：

虽然时间都不大，可能会出现一些误差，但不管怎样，还是很容易看得出来在进行两种优化后，运行时间快了很多。

简介