啥叫并查集啊（战术后仰） 由定义到应用带你团灭并查集 （含例题和详细注释）_并查集如何使用

引用Wikipedia 对并查集的定义

在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个用于此数据结构的操作：
Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union：将两个子集合并成同一个集合。
由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（union-find data structure）或合并-查找集合（merge-find set）。其他的重要方法，MakeSet，用于创建单元素集合。有了这些方法，许多经典的划分问题可以被解决。
为了更加精确的定义这些方法，需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素，称为代表，以表示整个集合。接着，Find(x) 返回x所属集合的代表，而Union使用两个集合的代表作为参数。

如果你已经学过最小生成树问题的经典算法Kruskal算法，那你就应该对并查集有所了解（尽管你可能并没有意识到并查集的存在，没错，说的就是我 !o!）

回顾一下Kruskal算法的步骤：

1. 新建图G，G中拥有原图中相同的节点，但没有边
2. 将原图中所有的边按权值从小到大排序
3. 从权值最小的边开始，如果这条边连接的两个节点于图G中不在同一个连通分量中，则添加这条边到图G中
4. 重复3，直至图G中所有的节点都在同一个连通分量中

所以，关键在于怎么判断新加入的一条边的两个节点是不是属于一个连通分量（或者说，有没有形成环）。

看看当时是怎么写(抄)的代码

public Edge[] kruskal(){
    int[] ends = new int[getV()];
    Edge[] res = new Edge[getV()-1]; //存储最小生成树的边,边数 = 顶点数 - 1
    int index = 0;

    Edge[] e = getEdges();//获取图的所有边
    Edge[] edges = edgeSort(e);//对边进行排序

    for (int i = 0;i < edges.length;i++){
        int v1 = getIndexByVertex(edges[i].getV1());
        int v2 = getIndexByVertex(edges[i].getV2());

        int m = getEnd(ends, v1);
        int n = getEnd(ends, v2);
        if (m != n){//加上这条边后，如果不构成环
            res[index++] = edges[i];
            ends[m] = n; // !!!! 核心
        }
    }

    //返回最小生成树的边集合
    return res;
}

public int getEnd(int[] ends,int v){
    while (ends[v] != 0){
        v = ends[v];
    }
    return v;
}
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
30

如果我们从上面这段代码中拎些熟悉的片段出来

//p1
public int getEnd(int[] ends,int v){
    while (ends[v] != 0){
        v = ends[v];
    }
    return v;
}
1
2
3
4
5
6
7

//p2
int m = getEnd(ends, v1);
int n = getEnd(ends, v2);
if (m != n){//加上这条边后，如果不构成环
    res[index++] = edges[i];
    ends[m] = n; // !!!! 核心
}
1
2
3
4
5
6
7

看出点啥没？

• 第一段代码中的getEnd()就是并查集定义中的find();
• 第二段代码中就是union()

Type root = find (Type node)
传入某个节点，返回它的根节点
/
union (Type node1,Type node2)
把node1和node2所在的两个不同的连通分量合并成一个连通分量

在大概了解并查集的定义及其两个主要操作之后，通过几道例题来看看并查集的用法并在做题的过程中加深对并查集的理解。

0）LeetCode：685.冗余连接Ⅱ

在本问题中，有根树指满足以下条件的有向图。该树只有一个根节点，所有其他节点都是该根节点的后继。每一个节点只有一个父节点，除了根节点没有父节点。
输入一个有向图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。 每一个边 的元素是一对 [u, v]，用以表示有向图中连接顶点 u 和顶点 v 的边，其中 u 是 v 的一个父节点。
返回一条能删除的边，使得剩下的图是有N个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

分析：
可能会出现的两种情况

1. 没有入度为0的根节点，也没有入度为2的节点，此时会形成环。
2. 有入度为0的节点，但是也有入度为2的节点，根据定义有根树除根节点外每个节点只有一个父节点（即入度为1），有可能会形成环，如上图示例。

所以，显然这题的一个关键点在于判断加入某条边之后是否形成环，如果形成环，直接删除该边就是本题的解，如果没形成环，说明只能是出现度为2的情况，此时删除造成度为2的最后一条边。

int[] anc;//并查集
public int[] findRedundantDirectedConnection(int[][] edges) {
    int n = edges.length;
    int[] parent = new int[n+1];//记录父节点
    anc = new int[n+1];//并查集
    int[] edge1 = null;//针对情况2 保存导致入度为2的第一条边
    int[] edge2 = null;// 第二条边
    int[] lastEdgeCauseCircle = null; //记录导致形成环的边

    for(int i = 0;i < n;i++){// 遍历边集
        //初始化并查集
        if(anc[edges[i][0]] == 0) anc[edges[i][0]] = edges[i][0];
        if(anc[edges[i][1]] == 0) anc[edges[i][1]] = edges[i][1];
        
        if(parent[edges[i][1]] == 0){//如果第一次入度
            parent[edges[i][1]] = edges[i][0];// 记录父节点
            int ancU = find(edges[i][0]); //分别查找边的两个节点所属的连通分量（返回根节点）
            int ancV = find(edges[i][1]);
            if(ancU != ancV)//如果不是一个连通分量（无环），合并
                anc[ancU] = ancV;//只需将其中一个连通分量的根的值改为另一个分通分量的下标即可
            else//出现环
                lastEdgeCauseCircle = edges[i];//记录导致环形成的边
            
        }else{//发现入度为2
            edge1 = new int[]{parent[edges[i][1]],edges[i][1]};//第一次入度
            edge2 = edges[i];//第二次入度
        }
    }

    //两种情况，① 存在入度为2，删除造成环的边 ② 不存在入度为2的节点，即没有根节点，删除最后造成没有根节点的边
    if (edge1 != null && edge2 != null) return lastEdgeCauseCircle == null ? edge2 : edge1;
    else return lastEdgeCauseCircle;
}

private int find(int node){
    while(anc[node] != node)//循环，不断往前找，直到找到该连通分量的根
        node = anc[node];
    return node;
}
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
30
31
32
33
34
35
36
37
38
39

再看看这题，本题中并查集的索引下标表示某个节点，元素值表示其父节点。
find()函数其实就是不断找父节点的父节点的父节点的父节点……直到找到根节点，最后返回根节点，而如果一条边的两个节点所在的连通分量的根节点是同一个，说明两个节点本就属于同一个连通分量，如果加入这条边就会形成环，反之不形成环。
合并两个连通分量，其实只需要把其中一个连通分量的根的元素值（它的根节点）改为另一个连通分量的根节点。

---

有冗余连接Ⅱ，那肯定不能忘了它兄弟，冗余连接I，如果你已经对上一题中并查集的用法真正理解了，那么这一题就是弟弟了。
建议先自己做，然后再看解析

1) 684. 冗余连接

在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。
返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。

一句话，冗余连接Ⅱ是有向图（需要考虑父节点），冗余连接Ⅰ无向图。所以，这题就更纯粹的考并查集的应用了。

int[] ufa;
public int[] findRedundantConnection(int[][] edges) {
    //并查集 判断有没有环就行了
    int n = edges.length;
    ufa = new int[n+1];//union-find-algorithm 并查集
    int[] ans = null;//记录删除的边
    for (int[] pair : edges){
        int u = pair[0];
        int v = pair[1];
        if(ufa[u] == 0) ufa[u] = u;
        if(ufa[v] == 0) ufa[v] = v;

        int uRoot = find(u);
        int vRoot = find(v);
        if(uRoot != vRoot){//union
            ufa[uRoot] = vRoot;
        }else{
            ans = pair;
            break;
        }
    }
    return ans;
}

private int find(int node){//递归版
    if (ufa[node] == node) return node;
    node = find(ufa[node]);
    return node;
}
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

有没有因为几个变量的改变，又看的模模糊糊？？
没有？ 恭喜你，你已经会用并查集解决问题了。

---

再试一题

2）990.等式方程的可满足性

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一：“a==b” 或 “a!=b”。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。

int[] ufa;
public boolean equationsPossible(String[] equations) {
    //并查集
    ufa = new int[26];//26个小写字母
    int n = equations.length;

    //需要把相等的排在前面，不相等的关系写在后面
    List<String> listEqn = new ArrayList<>();
    List<String> listNotEqn = new ArrayList<>();
    for(int i = 0; i < n;i++){//分别把相等和不相等的筛出来
        if(equations[i].charAt(1) == '!')
            listNotEqn.add(equations[i]);
        else
            listEqn.add(equations[i]);
    }
    for(int i = 0;i < listEqn.size();i++)//再放回去
        equations[i] = listEqn.get(i);
    for(int i = 0;i < listNotEqn.size();i++)
        equations[listEqn.size()+i] = listNotEqn.get(i);

    for (int i = 0;i < 26;i++)//初始化
        ufa[i] = i;

    int ul,ur;
    for(int i = 0;i < n;i++){
        ul = find(equations[i].charAt(0)-'a');
        ur = find(equations[i].charAt(3)-'a');
        if(equations[i].charAt(1) == '!' && ul == ur)
            return false;
        if(equations[i].charAt(1) == '=')
            ufa[ul] = ur;//union
    }

    return true;
}

private int find(int node){
    if(node == ufa[node]) return node;
    node = find(ufa[node]);
    return node;
}
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
30
31
32
33
34
35
36
37
38
39
40
41

这题可能需要解释的地方可能是“需要把相等的排在前面，不相等的关系写在后面” 这句话。

首先，先看本题的解题思路，把==的两个字母加入一个并查集，然后再检查!=的两个字母是不是在一个连通分量里，如果是，那么return false,反之，如果所有表达式都满足要求，则return true。

所以，这就要求==的式子必须在!=的式子前面，否则，如果先判断a!=b，此时ul!=ur满足条件，a和b不在一个连通分量里。

但是，后来再判断a==b，此时，如果ul!=ur你是无法确定是什么原因造成的，可能是因为之前出现过a!=b，也有可能a、b还没有比较过。

因此，我个人的看法，由于题目给定数组大小在[2,500]之间，大小其实并不大，我可以以暴力的方式排序，将!=和==的式子筛选出来，然后再依次放回==，最后放回!=。