并查集

01.jpg 02.jpg 03.jpg

/********************************
* 程序名称：并查集
* 开发时间：2021-02-05
* 参考教程 B站 https://www.bilibili.com/video/BV13t411v7Fs
*******************************/
#include <iostream>
#include <cstdio>

#define VERTICES 6     //节点数

using namespace std;

//init
void init(int parent[]) {
    for(int i=0; i<VERTICES; i++) {
        parent[i] = -1;
    }
}

int find_root(int x, int parent[]) {
    int x_root = x;        //为-1是根节点 
    while(parent[x_root] != -1) {  //查找父节点 
        x_root = parent[x_root];
    }
    return x_root;
}

/**
 * 1 - 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) {
        return 0;     //合并失败 
    } else {  //否则把x_root节点的父节点设置为x_root 
        parent[x_root] = y_root;
        return 1;     //合并成功 
    }   
} 
//main() star
int main() {
    //code here
    int parent[VERTICES] = {0};   //全部初始化为0，也可以写{}
    int edges[6][2] = {{0, 1}, {1, 2}, {1, 3}, 
                       {2, 4}, {3, 4}, {2, 5}}; // 1 2 3 4 5 6  二叉树 
    init(parent);
    int i;
    for(i=0; i<6; i++) {
        int x = edges[i][0];    //第i节点的第一条边 
        int y = edges[i][1];    //第i节点的第二条边
        if(union_vertices(x, y, parent) == 0) {
            printf("Cycle detected!\n");
            exit(0);
        } 
    }
    printf("No Cycle found.\n");
    
    return 0;
}

测试1：

Cycle detected!

--------------------------------
Process exited after 0.5338 seconds with return value 0
请按任意键继续. . .

测试2：

...
    int edges[5][2] = {{0, 1}, {1, 2}, {1, 3}, 
                       {3, 4}, {2, 5}}; // 1 2 3 4 5 6  二叉树 
    init(parent);
    int i;
    for(i=0; i<5; i++) {
...

No Cycle found.

--------------------------------
Process exited after 0.2785 seconds with return value 0
请按任意键继续. . .