并查集从入门到出门

于是我们可以这样概括性地描述并查集：

这基本上就是对并查集的完整描述了，十分简单。以问题呈现时，问题涉及的元素初始时总是自己构成一个单元素集合，求解问题需要通过合并操作将等价元素归入一个集合中。为了能够合并等价元素，我们必须查询希望合并的对象元素属于哪个集合，以决定是否要执行合并。因此 主要操作就是「查询」与「合并」 。「不相交」描述的是问题元素构成集合之后各个集合不相交的状态，「并查」描述的是处理问题时的操作。后文中两种称呼都会出现。

本文余下内容，你将会以547: 省份数量问题为研究对象，以解决该问题为目标，在解决这个问题的过程中独立发明并查集。

LeetCode 547. 省份数量
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
示例1:
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
示例2
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

这是一个典型的并查集问题。如果我们能够通过矩阵信息将同一省份的城市都加入到同一个集合，最终这些不相交集合的数量就是省份数量。

从现在开始，行文视角换成正在读本文的你。对于上述问题，你在草稿纸上稍作勾画，写下了如下处理过程 (draft版)：

初始时，每个城市是否与其他城市同属一省是未知的，此时每个城市构成单元素集合。
为了知道哪些城市同属一省，需要遍历矩阵，若(i, j)为1，说明i, j两个城市同属一省，可以合并在一起，得到一个2元素集合。在集合扩大的过程中，需要找到一个代表，以便于多元素集合之间的合并。即当询问 i 与 j 是否应当合并时，需先确定 i 和 j 各自的代表，若相同，那么她们在之前就已经通过其他城市合并在一起了，若不同，则合并之，即向其中一个城市宣告它的代表，使她可以知道自己属于哪个省。现在，「查询」与「合并」变得更具体了。
对未确定归属的城市进行上述的查询合并操作，当结束矩阵遍历时，所有城市就都知道了自己的代表。此时再遍历一遍所有城市，「查询」她们的代表，有多少个不同的代表，就有多少个不同的省份，于是问题得到解决。
通过上述对处理过程的思考，你发现「代表」在这一过程中至关重要，一个迫切要解决的问题就是如何保存及表示「代表」。再回顾一遍查询操作，假设集合中的某个元素(省会城市) x 为该集合的代表，查询城市 y 是否属于x所在的省（x省）时，虽然不能直接得知这一信息，但 y 可能知道自己与其他城市是否在同一省，而这个其他城市又知道自己与 x 在同一省，或者经过「若干跳」来追溯到 x，那么你就能够知道 y 与 x 为同一省。这种向着一个方向串联的关系使你立刻想到以 (单向)链表 来实现(后面你会知道用树的概念更合适，不过现在的你还一无所知)，以尾节点(省会城市)作为代表，每个元素(城市)指向它的后继(通过矩阵中的1得知)，连续地向next查询，一定能查询到尾结点。查询两个节点元素的尾结点是否相同，即可知道他们是否属于同一集合。

总之，你勾勒出了并查集处理问题的主要过程为：初始化(单元素集合)、合并和查询。不待稍歇，你即刻拍马上路。

处理过程
初始化
你首先尝试完成初始化。自然是从最简单的(实际上也是最常用的)的数据形式入手，你采用了 0 到 n - 1的整数代表问题涉及的 n 个元素，并以 数组 储存之。自然地，下标即代表元素，值为与该元素有 「等价」 关系的元素，在亲戚关系中该等价关系为是否互为亲戚，在省份问题中等价关系为是否同属一省。对于省份问题，你创建了一个 capital[] 数组 (capital即省会，虽然一开始城市 capital[i] 还不等于省会，但你希望capital[i]在一番处理后为城市 i 的省会)，capital大小为矩阵的一维长度，即城市数量。初始时，每个元素只知道自己与自己「等价」，因此创建这个数组后，遍历并使得capital[i] = i。这样初始化就完成了，十分容易。实际编写代码解题时，初始化过程可以在主方法中完成，也可以在并查集类(UnionFind)的构造器中完成。

// 初始化
int[] capital = new int[isConnected.length];
for(int i = 0; i < isConnected.length; i++) {
    capital[i] = i;
}

你选择在构造器中完成初始化，并写下如下代码。

class Solution{
    // 在主方法(findCycleNum)中new UnionFind
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind uf = new UnionFind(isConnected); // 通过构造器完成初始化
  
        // 求解过程 ???
  
        return ???;
    }
}

// UnionFind类，只写我们当前知道的。
class UnionFind{
    private int[] capital;
    // 其他字段???
    
    public UnionFind(int[][] isConnected){ // 构造方法
        this.capital = new int[isConnected.length];
        for(int i = 0; i < isConnected.length; i++){ 
            capital[i] = i;
            // 其他字段的初始化???
        }
    }
}

你自己写了个输入矩阵，一共有6个城市{0, 1, 2, 3, 4, 5}，isConnected[i][j] = 1表示i与j为同一省。

// 输入矩阵M
{
{1, 0, 0, 0, 1, 0}, // 0-0, 0-4
{0, 1, 0, 0, 0, 1}, // 1-1, 1-5
{0, 0, 1, 1, 0, 1}, // 2-2, 2-3, 2-5
{0, 0, 1, 1, 0, 0}, // 3-2, 3-3
{1, 0, 0, 0, 1, 0}, // 4-0, 4-4
{0, 1, 1, 0, 0, 1}, // 5-1, 5-2, 5-5
}

初始化后得到如下5个单元素集合。

合并
你现在开始尝试实现 合并方法(union) 。在你设计的处理过程中已经写到，合并的依据是查询，你先假设自己已经实现了「查询」方法find(x)，该方法返回 x 的当前代表。合并 x 和 y 的前提是 find(x) != find(y)，因为若 find(x) == find(y)，说明二者已经在同一集合中了（同一省）。具体做法如下，对于 x，y 两个城市，若 find(x) != find(y)，就令 capital[find(y)] = find(x)，当然也可以是 capital[find(x)] = find(y)，选用其中一种即可。你一开始可能想要写成 capital[x] = y，但马上发现这么写只能表示 y 是 x 的代表，而你的目的是用 y 目前的代表 (find(y)的返回值) 来作为 x 的代表 (find(x)的返回值) 的代表，这样才能使得 x 目前的集合整个并入 y 所在的集合，这一点现在还不太直观，但在实现查询方法后你会有更深的体会。合并方法就这么实现好了，并不复杂，你的信心开始上涌。

// union方法
public void union(int x, int y) {
    if(find(x) != find(y)){
        capital[find(y)] = find(x);
    }
}

// 在main方法中遍历矩阵，调用union执行合并的过程的写法如下：
for(int i = 0; i < n; i++){
    for(int j = i + 1; j < n; j++){
        if(isConnected[i][j] == 1) uf.union(i, j);
    }
}

于是主方法扩充成为如下：

class Solution{
    // 在主方法(findCycleNum)中new UnionFind
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind uf = new UnionFind(isConnected); // 通过构造器完成初始化
        // 两个for，遍历矩阵完成合并
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(isConnected[i][j] == 1) uf.union(i, j);
            }
        }
        return ???; // 完成合并后我们已经完成求解，但现在还不知道该返回什么
    }
}

现在你想试试这个合并方法能不能有效处理输入矩阵，并看看会「合并」成何种状态。为方便，你把前面的输入矩阵isConnected再一次写在这里。 遍历前三行，你画出了遍历到 isConnected[2][3] 和 isConnected[2][5]的状态（建议真的动手画一下，加深理解）。可以看到，遍历前三行后，就已经得到了最终的两个不相交集，所以对于这个输入，一共有两个省。

// 输入矩阵M
{
{1, 0, 0, 0, 1, 0}, // 0-0, 0-4
{0, 1, 0, 0, 0, 1}, // 1-1, 1-5
{0, 0, 1, 1, 0, 1}, // 2-2, 2-3, 2-5
{0, 0, 1, 1, 0, 0}, // 3-2, 3-3
{1, 0, 0, 0, 1, 0}, // 4-0, 4-4
{0, 1, 1, 0, 0, 1}, // 5-1, 5-2, 5-5
}

当你画出union的过程后，自然地发现，数据的结构呈现出 「树」 的形态，原先的单向链表的「尾结点」为树的 「根」 ，但与通常的树不同，这里的链接关系是从孩子结点指向父结点。现在，你非常自然地将并查集结构从一开始的很直觉的「单向链表」转换成了「树」。（当然这并不是特别重要，只不过我们有必要从这里开始统一后续的描述语言，即用树的语言来描述并查集。）

查询
你现在开始尝试实现查询方法(find方法)。之前已经说过，集合以单向链表（暂时还用链表的语言描述）的形式组织，尾结点为集合代表(省会)。那么查询应该是一个递归的过程，熟悉链表写法的你立即写出如下尾递归代码。

※ 当然也可以用迭代来实现，这里采用递归方式实现，后续你会知道用递归而非迭代实现的好处。

// 如果用链表组织集合，find可实现如下
public Node find(Node x){
    if(x.next == null) return x;
    return find(x.next);
}

这相当理想，不过别忘了，虽然将集合想象成链表，但目前capital是一个数组，要怎样沿着 x 到找到它的代表元呢？想到这里，你意识到要先思考如何知道哪个元素是代表元。初始化单元素集合时，capital[i] = i，如果此时合并 i 和 j，令capital[find(j)] = find(i)，因为刚开始 find(j) = j, find(i) = i，所以这个合并其实就是 capital[j] = i，并且要令此后 find(j) = i。你发现，代表元的特点是 find(i) = i，非代表元 find(j) = i (i 是 j 的代表)。于是仿照前面链表的写法，你轻松写出如下find方法。当 capital[x] = x时，找到代表元，否则就找当前代表元的代表元，因为从 x 到它的代表元，一定是串联在一条链上的，而对于尾结点 t，一定满足 capital[t] = t，因此可以保证找到 x 的代表元 t。可以看到，无论是union还是find，无论从理解上还是从实现上，都异常简单。（这正是并查集的一大特色，短小精悍，以少量的代码完成高效的处理，你后续还会反复体会到这一点。）

// find方法
public int find(int x) {
    if(capital[x] == x) return x; // 只有根节点满足capital[x] = x
    return find(capital[x]);  
}

小结
至此你得到了基本的并查集实现，主要方法find和union都只有数行代码，十分简洁。你回顾了一下刚才的实现，写下如下概括性的总结。

初始化：初始化代表下标 i (城市 i) 的省会(capital[i])的capital数组，一开始令 capital[i] = i。
合并：以查询为基础，union(x, y)将y当前的代表元「指向」x当前的代表元。
查询：为尾递归方法，find(x)不断在链上沿着x到它的代表元的方向前进，直到找到代表元(尾结点)。
现在，你已经 “独立发明” 了基本并查集，写下如下代码，并验证了它确实能够解决省份问题，你感到一阵兴奋。

※ 最终的省份数量可以在合并完成后对所有元素执行一次find(x)，统计不同结果的个数得到。更聪明的做法是设置一个unionCount = 0，表示合并的次数，在union方法内添加一行代码，使得发生合并时unionCount++实现累计，最后元素总数减去合并次数即为不相交集数量，也即省份数量。

class Solution{
    // 在主方法(findCycleNum)中new UnionFind
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind uf = new UnionFind(isConnected); // 通过构造器完成初始化
        // 两个for，遍历矩阵完成合并
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(isConnected[i][j] == 1) uf.union(i, j);
            }
        }
        return n - uf.unionCount; // 完成合并后我们已经完成求解，但现在还不知道该返回什么
    }
}

// UnionFind类，只写我们当前知道的。
class UnionFind{
    private int[] capital;
    int unionCount = 0; // 合并次数
  
    public UnionFind(int[][] isConnected){ // 构造器
        this.capital = new int[isConnected.length];
        for(int i = 0; i < isConnected.length; i++){ 
            capital[i] = i;
        }
    }
    // union方法
    public void union(int x, int y) {
        if(find(x) != find(y)){
            capital[find(y)] = find(x);
            unionCount++; // 实时统计合并次数
        }
    }
    // find方法
    public int find(int x) {
        if(capital[x] == x) return x; // 只有根节点满足capital[x] = x
        return find(capital[x]);  
    }
}

治学十分严谨的你开始研究目前的实现，并思考这一基本实现是否存在什么问题，或者有什么可以优化的地方。你首先从数据规模上考虑，若元素较多时，你发现将得到一条很长的链，对头节点查询其代表元时，需要遍历整条链。例如上述{1, 2, 3, 5}这个集合，如果还有{6}, {7}, {8}这三个单结点元素，且令{1,2,3,5}连续地与它们合并，即执行union(6, 5), union(7, 5), union(8, 5)之后，得到如下。

你发现，简单直接的合并将导致较高的树，若再继续执行union(5, 9)，首先进行的find(5)将会依次向父节点方向查询1, 2, 6, 7, 8，查询效率低下。设想，如果能将树的高度降低，例如除根节点外的所有节点直接挂在根节点下（放射状，或者也有人说是菊花状），那么find(x)的复杂度将为常数级，union也会因此变为常数级操作。基于这个思考，你将在下一节继续“独立发明”更好的求并方法，使得两棵树合并后得到的新树拥有更低的树高。

补充说明：寻找等价关系

在省份数量问题中，矩阵已给出等价信息，使得我们可以直接遍历 isConnected[i][j]，根据其值是否为 1 来直接求并，但对于有的问题，开始时等价信息并不明显，需要先找到这样的等价关系，然后才能求并。例如128: 最长连续序列问题，可以用并查集求解，但需要在开始时对i和i+1执行一次合并操作，这个「等价」是不太明显的。具体过程（代码）可参考后续内容。

求并优化
以目前的实现求解省份数量问题，你已经发现，合并 x 和 y 所在树(集合)时，只是简单地将 y 所在树的根指向 x 所在树的根capital[find(y)] = find(x)，最坏的情况下将得到一棵链状的树，较高的树高将导致较高的查询(及合并)复杂度。你希望以某种策略使合并后得到树高较小的树。几乎不费思忖，你就得到了一个自然的想法：在合并时，不再默认将 y 所在树(的根结点)挂到 x 所在树(的根结点)上，而是先比较这两棵树的大小，让较小的树挂到较大的树上，因为较小的树的树高总是倾向于较低。

按大小求并
现在，你尝试实现这种 「按大小求并」 的做法。这很简单，只需要在合并前比较两棵树的大小即可，如下，「按大小求并」的union方法对你来说就是“分分钟”（此时你已经有点膨胀了，不过作为并查集“发明人”，倒也不为过）。（为了从更广泛的意义上描述，此后不再特别强调「省份数量」问题，且把 capital 数组改为更一般的 parent 数组，表示父结点。）

※ 用parent而不是father，就像说孩子结点而不是儿子结点，用child而不是son，都是名称上的性别正义，不过中文语境中很少说“亲结点”，因此还是描述为父结点。

// Union方法：按大小求并
public void union(int x, int y){
    int xRoot = find(x), yRoot = find(y);
    // 根节点不同才求并
    if(xRoot != yRoot) {
        if(size[yRoot] <= size[xRoot]){ // 当y所在树大小小于等于x所在树大小时
            parent[yRoot] = xRoot; // 将yRoot挂在xRoot上
            size[xRoot] += size[yRoot]; // 更新x所在树的大小
        } else {
            parent[xRoot] = yRoot;
            size[yRoot] += size[xRoot];
        }
    }
}

你新增了一个大小与parent大小相同的size数组，size[i] 表示 i 结点所在树的大小。UnionFind类中需要添加size数组字段和相应的初始化内容（单结点集合的大小为1）。如下代码在构造器中初始化树大小数组size[]。补充后如下，并且你稍微修改了构造器的入参，不是以矩阵为入参，而是以一维数组为入参，转而把parent数组的初始化写在主方法中。因为你觉得这样有利于使UnionFind类的写法统一且稳定，不必总是对不同问题进行调整。你对这一修改还算满意。

// 初始化
int[] parent = new int[isConnected.length];
for(int i = 0; i < isConnected.length; i++) {
    parent[i] = i;
}
UnionFind uf = new UnionFind(parent);

// UnionFind类(部分)
class UnionFind{
    private int[] parent;
    private int[] size; // 保存树的大小
    
    public UnionFind(int[] parent) {
        this.parent = parent;
        this.size = new int[parent.length];
        for (int i = 0; i < parent.length; i++) {
            this.size[i] = 1; // 初始时单节点树大小为1
        }
    }
}

按大小求并的方法就这样实现出来了。不过在欣赏这个实现之余，你难免会回想自己当初为何出发，起初你希望合并后的树拥有较低的树高，但是一棵大小较小的树完全有可能高于大小较大的树，比如链状树在结点较少时也很容易高于菊花树。那为何不直接按高度求并呢？而且按高度求并还有一个好处，新树的高度变化只发生在两棵树高度相等时，此时高度加1，而按大小求并时，每次合并都要修改新树的大小。沿着这个想法，下一节你将继续“发明”「按高度求并」。

按秩(高度)求并
不是「按高度求并」吗，怎么还有个 「秩(rank)」 ？必须在这里先说明，写上「秩」是为了严谨，但原因现在只能按下不表，要等到你继续“发明”一种优化的查找方法后才会了解原因（这一点你现在还一无所知），现在先将「秩(rank)」看作「高度(height)」。类似「按大小求并」的做法，你立即写出「按秩(高度)求并」的如下方法（写法有点不规范，括号内单行语句的情况你都省略了括号，不过你并不是很在意，心想这有啥的？）。

// union方法：按秩(高度)求并，先判断是否在同一集合
public void union(int x, int y){
    int xRoot = find(x), yRoot = find(y);
    if( xRoot != yRoot){
        if(rank[yRoot] <= rank[xRoot]) parent[yRoot] = xRoot;
        else parent[xRoot] = yRoot;
        if(rank[xRoot] == rank[yRoot]) rank[xRoot]++; 
    }
}

你敏锐地发现还可以有一种去掉 if(xRoot != yRoot) 判断的写法。因为你发现即便 xRoot == yRoot，根据rank[xRoot] == rank[yRoot]，将执行 parent[yRoot] = xRoot，仍是根结点指向自己，并未改变什么。在不同集合元素求并操作较多时，这样做可以节省一点 xRoot != yRoot 判断的时间。当然，这并不重要，你只是想多展现一些不同的写法。你还注意到，采用这种写法后，在决定是否要增加秩(树高)时，要判断是否有 xRoot != yRoot。即当两棵树秩(高度)相等且为不同集合时，新树的秩(高度)加1。

// union方法：按秩(高度)求并，不判断是否在同一集合
public void union(int x, int y){
    int xRoot = find(x), yRoot = find(y);
    if(rank[yRoot] <= rank[xRoot]) parent[yRoot] = xRoot;
    else parent[xRoot] = yRoot;
    if(rank[xRoot] == rank[yRoot] && xRoot != yRoot){
        rank[xRoot]++; 
    }
}

秩(高度)较小的树的秩(高度)无需更新，因为每次求一个元素所在集合的高度都会先找到该集合的树的根，秩(高度)较小的树在合并后其树根在新树中就不是树根了。这一点你当然了若于胸。
现在你回过头重新审视前述导致树高较高的基本合并方法，并尝试使用优化的「按秩(高度)合并」方法看看效果。对于{1, 2, 3, 5}集合，连续地合并它与单节点集合{6}, {7}, {8}，即执行union(6, 5), union(7, 5), union(8, 5)，在应用按秩(高度)求并之后，得到如下。


效果十分理想。但结点5显得异常扎眼，如果能将节点5也直接连到根节点2下，将得到最完美的高度为2的合并后树。这是否能做到呢？一番踌躇后，你发现在union方法中无法做到这一点，因为union的作用只是让一个树根指向另一个树根。那find方法能实现吗？勤学好问的你继续逼问自己，并想到 find(5) 从 5 沿着父结点方向走向根，看起来可以从优化find方法入手。于是，你再接再厉，在下一节中继续“发明”这一优化。如果实现该优化，将使得 5 到根结点 2 的路径缩短，因此你在这里提前把这个优化命名为 「路径压缩」，优化后的find方法称作 「带路径压缩的查找」。

路径压缩
前面提到，在 find(5) 时，如果能在查询过程中将 5 的父结点改为 2，就完成了「路径压缩」，熟悉递归的你立刻感觉到这相当容易，只需在find()方法中修改一行代码，就可以让find()在查询根节点的同时执行这个「压缩」的操作。于是你写下如下代码，改动了return语句，将递归的find[parent[x]]赋值给parent[x]，如下。略作推敲，你肯定该写法正确无误，可以让当前查找的节点到根节点路径上所有的节点都指向根节点。

// find方法：带路径压缩
public int find(int x) {
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]);  
}

你继续审视前述按秩(高度)合并的扎眼的5，在更新了「带路径压缩」的find方法后，重新执行一次union看下会发生什么。对{1, 2, 3, 5}集合，连续地与单节点集合{6}, {7}, {8}合并。首先执行union(6, 5)，方法内会执行find(5)来查找5的根结点，在带路径压缩的find中，5在寻找其所在树的根节点的过程中，实时地令其到根节点路径上的所有节点都指向了根节点，于是原路径被压缩，继续合并{7}和{8}之后你画出下图。


终于得到了一棵对于查询(及合并)来说最完美的树，心情不错的你为防万一，又检查了一遍实现过程，并有一个不大不小的中发现，5指向2发生在union(6, 5)时(其内调用find(5))，find方法不会修改树的高度，「压缩」前后rank[2]保持不变，即rank[2] = 3，但经过find的压缩，树的高度已经变为2了。这时你突然有所领悟，原来这就是称做「按秩求并」而非「按高度求并」原因。一声「なるほど」之后你快速写下如下总结（「好记忆不如烂笔头」是你小学三年级的座右铭，你还把这句话刻在了书桌右上角）：

「按秩求并」而非「按高度求并」：

在应用带路径压缩的查询和按秩求并后，rank[root]记录的数字是树实际高度的一个上界，树的实际高度可能小于此值。

※ Webster词典中给出的 "rank(秩)" 一词的释义。
至此，你完成了一个中等偏大的成就：先是独立发明基本并查集，再通过观察树的形态发现优化方向，主动提出优化方案，并最终实现了两种求并优化（「按大小求并」和「按秩求并」）和一种查询优化（「带路径压缩的查询」）。你略感激动，但也没有四下声张，只是给好朋友发了条带截图的微信炫耀了一把，还顺手编辑了一张喵喵表情，“并查集，就这？就这？”。

类的实现代码
现在你作为并查集发明人，用一般教程作者的口吻继续总结如下内容。

通过上述对实际问题处理过程的讲解，我们已经给出了能够处理集合代表元查询及合并问题的并查集数据结构。在按大小或按秩求并时，需要保存大小或秩(高度)信息的数组。现给出如下包含直接求并，按大小求并，按秩求并，直接查询，带路径压缩查询等方法的实现。实际使用时只需按需选择一种求并和一种查询方法即可，按秩求并 + 带路径压缩查询 的组合在多数情况下因其效率更高而成为首选。

class UnionFind{
    private int[] parent;
    private int[] rank; // 实际代码中，按秩求并和按大小求并选择其中一种即可
    private int[] size; // 实际代码中，按秩求并和按大小求并选择其中一种即可
    
    public UnionFind(int[] parent) {
        this.parent = parent;
        this.rank = new int[parent.length];
        this.size = new int[parent.length];
        for (int i = 0; i < parent.length; i++) {
            this.rank[i] = 1;
            this.size[i] = 1;
        }
    }
    
    // 直接求并
    public void unionDirect(int x, int y) {
        if(find(x) != find(y)){
            parent[find(y)] = find(x);
        }
    }
    
    // 按大小求并
    public void unionBySize(int x, int y){
        int xRoot = find(x), yRoot = find(y);
        
        if(xRoot != yRoot) { // 根节点不同才求并
            if(size[yRoot] <= size[xRoot]){
                parent[yRoot] = xRoot;
                size[xRoot] += size[yRoot];
            } else {
                parent[xRoot] = yRoot;
                size[yRoot] += size[xRoot];
            }
        }
    }
  
    // 按秩求并
    public void union(int x, int y){
    int xRoot = find(x), yRoot = find(y);
    if( xRoot != yRoot){
            if(rank[yRoot] <= rank[xRoot]) parent[yRoot] = xRoot;
            else parent[xRoot] = yRoot;
            if(rank[xRoot] == rank[yRoot]) rank[xRoot]++; 
        }
    }
    
    // 直接查找
    public int findDirect(int x) {
        if(parent[x] == x) return x;
        return findDirect(parent[x]);  
    }
    
    // 带路径压缩的查找
    public int find(int x) {
        if(parent[x] == x) return x;
        return parent[x] = find(parent[x]); 
    }
}

无需大小/秩数组空间的技巧
你还在一本书上学到一种技巧，并搬运到了自己的教程上。如果元素的表示不涉及负数（这是通常的做法）的话，可以用一个小技巧来节省大小或秩(高度)数组的开销。在以前的说明中，初始化集合时，我们令每一个元素的父节点指向自己，即parent[x] = x，表示这是根节点。本技巧以parent[x] = -1表示根节点，并以parent[x]是否为负数来判断x是否为根节点。需要注意的是，因其为负数，在两棵树比较大小或秩(高度)时，值越小，则大小或秩(高度)越大。在按大小求并时，size[root]的更新方法不变，但在按秩(高度)求并时，新树高度增高1时令rank[root]--。

应用此技巧，给出如下完整实现。同样地，实际使用时只需按需选择一种求并和一种查询方法即可。

※ 此技巧学习自Weiss的数据结构与算法分析：Java语言描述 。另外，在不用负数技巧的版本中，由于根节点相同不影响结果，考虑到在不同集合元素求并操作较多时，在union方法中可以省去 xRoot != yRoot 的判断。这个版本中，必须要执行 xRoot != yRoot 的判断，否则当两个同集合元素比较时，将使得parent[xRoot] = xRoot，也即原为一个负数的parent[xRoot]的值变成了一个非负数(xRoot)，将导致程序错误。

class UnionFind2{
    private int[] parent;
    
    public UnionFind2(int[] parent) {
        this.parent = parent;
    }
    
    // 直接求并
    public void unionDirect(int x, int y) {
        if(find(x) != find(y)){
            parent[find(y)] = find(x);
        }
    }
    
    // 按大小求并
    public void unionBySize(int x, int y){
        int xRoot = find(x), yRoot = find(y);
        
        if(xRoot != yRoot) { // 根节点不同才求并
            if(parent[xRoot] <= parent[yRoot]){ // 负数比较，较小者树较大
                parent[xRoot] += parent[yRoot];
                parent[yRoot] = xRoot;
            } else {
                parent[yRoot] += parent[xRoot];
                parent[xRoot] = yRoot;
            }
        }
    }
    
    // 按秩求并
    public void union(int x, int y){
        int xRoot = find(x), yRoot = find(y);
        if(xRoot != yRoot) {
            if(parent[xRoot] <= parent[yRoot]){
                parent[yRoot] = xRoot;
            } else {
                parent[xRoot] = yRoot;
            }
            // 当两棵树秩相等根节点不同时，新树的高度增高1（负数表示，减1）
            if(parent[xRoot] == parent[yRoot]){
                parent[xRoot]--; 
            }
        }
    }
    
    // 直接查找
    public int findDirect(int x) {
        if(parent[x] < 0) return x; // 只有代表元满足 parent[x] < 0
        return findDirect(parent[x]); 
    }
    
    // 带路径压缩的查找
    public int find(int x) {
        if(parent[x] < 0) return x;
        return parent[x] = find(parent[x]; 
    }
}

复杂度分析
这个部分你终于感到力有不逮，严格的复杂度证明你看了八遍，最终选择放弃，暂时只能写下如下内容（但你在行文中假装自己知道什么是反阿克曼函数）。
时间复杂度：严格的分析很复杂，省略。带路径压缩的按秩求并的并查集，其查询与合并操作的时间复杂度均为O(α(n)) （α(n)表示增长十分缓慢的反阿克曼函数），对于任何实际的问题的n，α(n)通常不会超过5。因此可以认为此复杂度为O(1)。
空间复杂度：取决于parent[] / size[] / rank[]数组所占空间，为O(n)。
实战应用
在「处理过程」中介绍了应用不相交集处理问题的通用过程，对于不同的具体问题，各步骤的应用是灵活的。

如下一些例题中我们将看到，同样是应用并查集，对于128.最长连续数列，只需在find时以路径压缩方式合并，除给定初始时的等价关系用到主动合并(直接求并)外，不再调用union。在547.省份数量中，等价关系在输入矩阵中是明显的，只需在isConnected[i][j] = 1时主动合并union(i, j)即可，find中可以不带合并(路径压缩)，当然也可以带路径压缩以提高效率。在200.岛屿数量中，其与省份数量问题的输入都是矩阵，但岛屿数量问题的初始时单节点元素是矩阵中的每一个“1”，而省份数量问题是列(或行)中的下标，这一点有所不同。

罗列以下并查集题目，由于这些题目用并查集求解时整体框架相同，只在细节上有所变化，由于你已经是「并查集」发明人，这里不再写出详细题解，一些重要过程在注释中说明。

128.最长连续数列 (中等)
547.省份数量 (中等)
200.岛屿数量 (中等)
695. 岛屿的最大面积 (中等)
785. 判断二分图 (中等)
684. 冗余连接 (中等)
839. 相似字符串组 (困难)
399. 除法求值 (中等)

128: 最长连续数列

public int longestConsecutiveUF(int[] nums) {
    if(nums.length < 2) {
        return nums.length;
    }
    UnionFind uf = new UnionFind(nums);
    for(int num : nums) {
        uf.union(num, num + 1);
    }
    int max = 1;
    for (int num : nums) {
        max = Math.max(max, uf.find(num) - num + 1);
    }
    return max;
}

class UnionFind{
    // 用HashMap存储并查集
    Map<Integer, Integer> parents = new HashMap<>();

    // 输入数组arr，初始化并查集，同时完成对arr的去重
    public UnionFind(int[] arr) {
        for(int i : arr) {
            parents.put(i, i);
        }
    }

    // 带路径压缩的查找
    public int find(int x) {
        if(x == parents.get(x)) {
            return x;
        }
        int p = parents.get(x);
        parents.put(x, find(p));
        return parents.get(x);
    }
    // 直接求并
    public void union(int x, int y) {
        if(parents.containsKey(y)) {
            parents.put(x, y); // rootx指向rooty
        }
    }
}

547: 省份数量

正文中已贴过代码，这里贴一个应用「负数技巧」节省rank数组的代码。

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        UnionFind uf = new UnionFind(parent);
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(isConnected[i][j] == 1) uf.union(i, j);
            }
        }
        return n - uf.unionCount;
    }
}
class UnionFind{
    private int[] parent;
    public int unionCount = 0;

    public UnionFind(int[] parent){
        this.parent = parent;
    }
    // 带路径压缩的查找
    public int find(int x){
        if(parent[x] < 0) return x;
        return parent[x] = find(parent[x]);
    }
    // 按秩合并
    public void union(int x, int y){
        int xRoot = find(x), yRoot = find(y);
        if(xRoot != yRoot){
            unionCount++; // 只有不属于一个集合时，合并才次数加1
            if(parent[yRoot] >= parent[xRoot]) parent[yRoot] = xRoot;// yRoot挂到xRoot上
            else parent[xRoot] = yRoot; // xRoot挂到yRoot上
            if (parent[xRoot] == parent[yRoot]) parent[xRoot]--; // 秩相同时才加1(注意应用负数技巧时是减1)
        }
    }
}

200: 岛屿数量

class Solution {
    int islandsCount = 0;
    int mergedCount = 0;
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        UnionFind uf = new UnionFind(grid);
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int landx = i * n + j;
                if(grid[i][j] == '1'){ // 以下两行，检测右侧和下侧是否联通，联通时合并之（用并列的if，在union中会检测是否属于同一集合）
                    if(j < n - 1 && grid[i][j + 1] == '1') { // 右侧
                        uf.union(landx, landx + 1);
                    }
                    if(i < m - 1 && grid[i + 1][j] == '1') { // 下侧
                        uf.union(landx, landx + n);
                    }
                }
            }
        }
        return islandsCount - mergedCount;
    }

    private class UnionFind{
        private int[] parents;
        private int[] rank;

        public UnionFind(char[][] grid){
            int m = grid.length, n = grid[0].length;
            this.parents = new int[m * n];
            this.rank = new int[m * n];
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++) {
                    if(grid[i][j] == '1'){ // 针对单格岛，累计岛屿数量，赋值parents[k] rank[k]
                        islandsCount++;
                        int k = i * n + j;
                        parents[k] = k;
                        rank[k] = 1;
                    }
                }
            }
        }
        // 带路径压缩的查找
        public int find(int x){
            if(parents[x] == x) return x;
            return parents[x] = find(parents[x]);
        }
        // 按秩合并
        public void union(int x, int y){
            int xRoot = find(x);
            int yRoot = find(y);
            if(xRoot != yRoot){
                mergedCount++; // 只有不属于一个集合时，合并才次数加1
                if(rank[yRoot] <= rank[xRoot]) parents[yRoot] = xRoot;// yRoot挂到xRoot上
                else parents[xRoot] = yRoot; // xRoot挂到yRoot上
                if (rank[xRoot] == rank[yRoot]) rank[xRoot]++; // 秩相同时才加1
            }
        }
    }

}

695. 岛屿的最大面积

class Solution {
    // 按大小合并的并查集
    // 初始化 > 遍历grid，对“1”的格子，考察其右侧及下侧的格子，分别执行合并，
    // 按大小合并，更新大小时更新max
    // 1. 初始化
    // parents[k] 将二维grid[i][j]映射到一维 k = i * COL + j
    // 初始化parents: grid[i][j] = 1时 parents[k] = k
    // 2. 遍历grid
    // 3. 返回max
    int max = 0;
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        UnionFind uf = new UnionFind(grid);
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int landx = i * n + j;
                if(grid[i][j] == 1){ // 以下两行，如果右侧或下侧能够合并到当前岛中，合并之 
                    if(j < n - 1 && grid[i][j + 1] == 1) uf.union(landx, landx + 1);
                    if(i < m - 1 && grid[i + 1][j] == 1) uf.union(landx, landx + n);
                }
            }
        }
        return max;
    }

    private class UnionFind{
        private int[] parents;
        private int[] size;

        public UnionFind(int[][] grid){
            int m = grid.length, n = grid[0].length;
            this.parents = new int[m * n];
            this.size = new int[m * n];
            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++) {
                    if(grid[i][j] == 1){ // 针对单格岛，赋值parents[k]和size[k]
                        int k = i * n + j;
                        parents[k] = k;
                        size[k] = 1;
                        if(max != 1) max = 1; // 有单格岛时更新max=1
                    }
                }
            }
        }
        // 带路径压缩的查找
        public int find(int x){
            if(parents[x] == x) return x;
            return parents[x] = find(parents[x]);
        }

        public void union(int x, int y){
            int xRoot = find(x);
            int yRoot = find(y);
            if(xRoot != yRoot){
                if(size[yRoot] <= size[xRoot]) { // y所在集合大小小于等于x所在集合时，yRoot挂到xRoot上
                    parents[yRoot] = xRoot;
                    size[xRoot] += size[yRoot];
                    max = Math.max(max, size[xRoot]); // 更新max
                }
                else { // xRoot挂到yRoot上
                    parents[xRoot] = yRoot;
                    size[yRoot] += size[xRoot];
                    max = Math.max(max, size[yRoot]); // 更新max
                }
            }
        }
    }
}

785. 判断二分图

class Solution {
    // 并查集
    // 针对每个顶点u，考察它的邻接顶点v。所有的v都必须在相同集合中且都不与u在同一集合中，否则返回false。
    // 初始化parents[]为每个顶点都指向自己的单节点集合。
    // 遍历graph，对每一个u，将它的所有邻接顶点v都合并起来。
    // 再次遍历graph，对每一个u，考察是否有find(u) == find(v)，满足则graph不是二分图
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        UnionFind uf = new UnionFind(graph);
        for(int i = 0; i < n; i++){
            int[] v = graph[i];
            for(int j = 1; j < v.length; j++) uf.union(v[0], v[j]); // 将所有v合并在一起
            if(v.length >0 && uf.find(i) == uf.find(v[0])) return false; // 合并完成后立即考察u(i)是否与其邻接顶点们在同一集合中
        }
        return true;
    }

    private class UnionFind{
        private int[] parents;
        private int[] rank;

        public UnionFind(int[][] graph){
            int n = graph.length;
            this.parents = new int[n];
            this.rank = new int[n];
            for(int i = 0; i < n; i++){
                parents[i] = i;
                rank[i] = 1;
            }
        }
        // 带路径压缩的查找
        public int find(int x){
            if(parents[x] == x) return x;
            return parents[x] = find(parents[x]);
        }
        // 按秩求并
        public void union(int x, int y){
            int xRoot = find(x);
            int yRoot = find(y);
            if(xRoot != yRoot){
                if(rank[yRoot] <= rank[xRoot]) parents[yRoot] = xRoot;
                else parents[xRoot] = yRoot; // xRoot挂到yRoot上
                if(rank[xRoot] == rank[yRoot]) rank[xRoot]++;
            }
        }
    }
}

684. 冗余连接

class Solution {
    // 并查集
    // 遍历edges，考察每一条边的两个顶点是否已经在同一个集合中，
    // 若已经在同一集合中，说明除去该边，剩下就是完整的树，输出该边
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length; 
        UnionFind uf = new UnionFind(n + 1); // 因为节点值是1～n，所以parent下标要从0～n，下标0实际上没用上
        for(int i = 0; i < n; i++){
            int u = edges[i][0], v = edges[i][1];
            if(uf.find(u) == uf.find(v)) return new int[]{u, v};
            else uf.union(u, v);
        }
        throw null;
    }

    private class UnionFind{
        int[] parent;
        int[] rank;

        public UnionFind(int n){
            this.parent = new int[n];
            this.rank = new int[n];
            for(int i = 0; i < n; i++){
                parent[i] = i;
                rank[i] = 1;
            }
        }

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

        public void union(int x, int y){
            int xRoot = find(x);
            int yRoot = find(y);
            if(xRoot != yRoot){
                if(rank[xRoot] <= rank[yRoot]) parent[yRoot] = xRoot;
                else parent[xRoot] = yRoot;
                if(rank[xRoot] == rank[yRoot]) rank[xRoot]++;
            }
        }
    }
}

839. 相似字符串

class Solution {
    // 并查集
    // 一开始每个字符串都是单节点集合
    // 如果两个字符串相似，合并，最终每一个不相交集合就是一个相似字符串组
    int mergedCount = 0;
    public int numSimilarGroups(String[] strs) {
        int n = strs.length;
        UnionFind uf = new UnionFind(n);
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                String si = strs[i], sj = strs[j];
                if(uf.find(i) == uf.find(j)) continue;
                if(isSimilar(si, sj)) uf.union(i, j);
            }
        }
        return n - mergedCount;
    }

    private boolean isSimilar(String s, String t){
        int n = s.length();
        int diff = 0;
        for(int i = 0; i < n; i++){
            if(s.charAt(i) != t.charAt(i)) diff++;
        } 
        return diff > 2 ? false : true;
    }

    private class UnionFind{
        int[] parent;
        int[] rank;

        public UnionFind(int n){
            this.parent = new int[n];
            this.rank = new int[n];
            for(int i = 0; i < n; i++){
                parent[i] = i;
                rank[i] = 1;
            }
        }

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

        public void union(int x, int y){
            int xRoot = find(x);
            int yRoot = find(y);
            if(xRoot != yRoot){
                mergedCount++;
                if(rank[xRoot] <= rank[yRoot]) parent[yRoot] = xRoot;
                else parent[xRoot] = yRoot;
                if(rank[xRoot] == rank[yRoot]) rank[xRoot]++;
            }
        }
    }
}

339. 除法求值

class Solution {
    // 并查集
    // 基本想法：
    // equations中例如 a / b = 2.0，可以将a，b视作同一集合的元素，a指向b，有向边权为2.0。
    // 对于equations中的所有x / y = w，将x和y都合并起来（x指向y），并将权重w记录到w[]中。
    // 当询问[x,y]时，应该合并x与y，任意一个不是equations里存在的字符时，返回-1.0，如果存在，
    // 查询他们是否在同一集合中，不在则返回-1.0，若在同一集合中，假设并查集已经写好了带路径压缩的
    // find()，那么查询的结果将得到x指向根节点z的边w1，y指向z的边权w2，x/y的结果为w1/w2。
    // 主要难点有两个：
    // 1. 在find(x)中按路径压缩的同时，实时地修改边权。路径压缩通过递归调用find实现，
    //    因此靠近根的节点先完成指向根节点的动作，那么递归地将边权乘起来即可。
    // 2. 在union(x, y)时，总是执行parents[xRoot] = yRoot，即将xRoot挂到yRoot上，
    //    此时的w[xRoot]必满足w[x] * w[xRoot] = w * w[yRoot] (x/y=w)，
    //    故有w[xRoot] = w * w[yRoot] / w[x]
    // 初始化：
    // parents[]应该保存所有变量，将String类型的变量转换成int，且从0开始，方便并查集操作。
    // 用HashMap来将String类型变量映射为int id。
    // 
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Integer> map = new HashMap<>();
        int id = 0;
        for(List<String> eq : equations){ // 完成String类型变量到int id的映射
            String x = eq.get(0);
            String y = eq.get(1);
            if(!map.containsKey(x)){
                map.put(x, id);
                id++;
            }
            if(!map.containsKey(y)){
                map.put(y, id);
                id++;
            }
        }
        // 完成并查集初始化及equations中所有除式变量对的合并
        UnionFind uf = new UnionFind(id); // 此时id正好等于不重复变量个数
        for(int i = 0; i < equations.size(); i++){ // 对算式x/y，完成x与y的合并
            List<String> eq = equations.get(i);
            uf.union(map.get(eq.get(0)), map.get(eq.get(1)), values[i]);
        }
        // 完成queries的查询
        double[] ans = new double[queries.size()];
        for(int i = 0; i < queries.size(); i++){
            List<String> q = queries.get(i);
            Integer xid = map.get(q.get(0));
            Integer yid = map.get(q.get(1));
            if(xid == null || yid == null) ans[i] = -1.0d;
            else ans[i] = uf.query(xid, yid);
        }
        return ans;
    }
    
    private class UnionFind{
        int[] parents;
        double[] w; // 指向父节点的权值

        public UnionFind(int n){
            this.parents = new int[n];
            this.w = new double[n];
            for(int i = 0; i < n; i++){
                parents[i] = i;
                w[i] = 1.0d;
            }
        }
        // 带路径压缩的查询
        public int find(int x){
            if(parents[x] == x) return x;
            else{
                int origin = parents[x];
                parents[x] = find(parents[x]);
                w[x] *= w[origin]; // x到xRoot上的每条边权连乘，最后一条边权是1
            }
            return parents[x];
        }
        // 简单求并
        public void union(int x, int y, double val){
            int xRoot = find(x);
            int yRoot = find(y);
            if(xRoot != yRoot){
                parents[xRoot] = yRoot;
                w[xRoot] = val * w[y] / w[x];
            }
        }

        public double query(int x, int y){
            int xRoot = find(x);
            int yRoot = find(y);
            if(xRoot == yRoot) return w[x] / w[y];
            return -1.0d;
        }
    }
}