理论

考虑这样一道题，判断图中是否有环：

我们该如何去做呢？

利用并查集的方法，过程如下：

1. 0->1有边，所以0和1加入一个连通集合中：
   
2. 1->2有边，同样加入到连通集合中。
3. 接着检查3->4有边，3和4作为一个集合：

4. 1->3有边，把上面两个集合合并，形成0,1,2,3,4集合。（此时已经使用的边有(0,1), (1,2), (3,4), (1,3)）
5. 此时并查集中任意两点，都有可达路径。当接着来一个新的边(2,4)时，由于没有(2,4)这条边时，它们已经连通，再加上(2,4)就会形成一个环，此时判断结束。

代码

我们要如何表示节点之间的关系呢，同时如何进行并查集合并呢？

首先我们来看并查集的关系如何表示：

• 初始化一个大小为6的数组，用来表示节点i的父节点，并赋初始值为-1。

那么(0,1)和(1,2)边的表示如图：

• 首先根据(0,1)一条边，将0的父亲赋值为1（反过来也可以），代表1和0是连通的
• 接着根据边(1,2)，将2的父亲赋值为1的父亲（就是1），如上图。

合并过程

当进行到如上一步。遇到(1,3)这条边时，要进行并查集合并：

• 显然我们可以将1直接指向3，但这样会使树过长
• 因此，我们将1（父节点）指向3的父节点4，并更新parent数组

代码

对于任意两个节点x和y，我们需要分别获取它们的父节点x_root, y_root，然后将parent[x_root]指向y_root。

代码可以分解为两步：

1. find_root(x)
2. union(x, y)

#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

#define VERTICES 6

void init(int parent[])
{
    fill(parent, parent+VERTICES, -1);
}

int find_root(int x, int parent[])
{
    int x_root = x;
    while(parent[x_root] != -1){
        x_root = parent[x_root];
    }
    return x_root;
}

/*1 - union successfully, 0 - failed（两个节点在同一结合）*/
int union_vertices(int x, int y, int parent[]){
    int x_root = find_root(x, parent);
    int y_root = find_root(y, parent);
    if(x_root != y_root)
    {
        parent[x_root] = y_root;//把x的父节点复制成y
        return 1;
    }
    return 0;
}

int main()
{
    int parent[VERTICES];/*Vertices代表节点*/
    int edges[5][2] = {{0,1}, {1,2}, {1,3}, {3,4}, {2,5}};
    init(parent);
    for(int i = 0; i < 5; i++)
    {/*遍历边，合并*/
        int x = edges[i][0];
        int y = edges[i][1];
        if(union_vertices(x, y, parent) == 0){
            printf("Cycle detected!\n");
            return 0;
        }
    }
    printf("No cycles found.\n");
    return 0;
}

其实上面代码，有一个缺陷，就是一直是将x_root的parent指向y_root，对于极端数据，可能会使得查找父节点的链过长，时间复杂度最差退化为o(n)，我们可以加上一个层数Rank,根据Rank来判断如何添加：

/*1 - union successfully, 0 - failed（两个节点在同一结合）*/
int union_vertices(int x, int y, int parent[], int Rank[]){
    int x_root = find_root(x, parent);
    int y_root = find_root(y, parent);
    if(x_root != y_root)
    {
        //parent[x_root] = y_root;//把x的父节点复制成y
        if(Rank[x_root] > Rank[y_root])
        {
            parent[y_root] = x_root;
        }
        else if(Rank[x_root] < Rank[y_root])
        {
            parent[x_root] = y_root;
        }
        else
        {
            parent[x_root] = y_root;
            Rank[y_root]++;//加上一层
        }
        return 1;
    }
    return 0;
}

具体就不展开了。

参考B站大佬讲解视频:https://www.bilibili.com/video/av38498175?from=search&seid=12476310733420597220