C++ 实现并查集

并查集

并查集实际上就是并集和查集的过程。集(集合)可以理解为一棵树，即一个根结点连着无数个子节点。

例题解析

输入格式：
第一行包含两个整数N、M，表示共有N个元素和M个操作。
接下来M行，每行包含三个整数Zi、Xi、Yi
当Zi=1时，将Xi与Yi所在的集合合并
当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N
输出格式：
如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为Y或者N
输入输出样例
输入样例：
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
输出样例：
N
Y
N
Y

AC代码如下
test.cpp

#include <fstream>

#include <iostream>
#include <string>

using namespace std;

int findFather(int *father, int x) {
    int i = x;
    while (father[i] != i) {
        i = father[i];
    }
    return i;
}

void gather_union(int *father, int x, int y) {
    int fx = findFather(father, x);
    int fy = findFather(father, y);
    if (fx != fy) {
        father[fx] = fy;
    }
}

int main() {
    ifstream infile;
    infile.open("input.txt");

    int num, num_oper;
    infile >> num >> num_oper;
    int *father = new int[num + 1];
    for (int i = 1; i <= num; i++) {  //初始化 将祖先设为自己
        father[i] = i;
    }

    int oper, x, y;
    for (int i = 0; i < num_oper; i++) {
        infile >> oper >> x >> y;
        if (oper == 1) {
            gather_union(father, x, y);
        }
        else {
            int fx = findFather(father, x);
            int fy = findFather(father, y);
            if (fx == fy) {
                cout << "Y" << endl;  //x和y同属一个集合
            }
            else {
                cout << "N" << endl;  //x和y不属于同一集合
            }
        }
    }


    infile.close();
    return 0;
}

input.txt

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

初始化
并查集要有一个记录每个节点的根节点的地址 (father[])，开始时将每个节点独立开来，(后面再进行合并操作)

int *father = new int[num + 1];
for (int i = 1; i <= num; i++) {  //初始化 将祖先设为自己
    father[i] = i;
}

查找
查找一个元素再其所在集合中的根节点(father)，可用来判断两个元素是否再同一个集合当中
当一个节点的father是它本身，则说明该节点是该集合的根节点

int findFather(int *father, int x) {
    int i = x;
    while (father[i] != i) {
        i = father[i];
    }
    return i;
}

合并
将两个集合合并起来，即将一个集合的根节点的father设为另一个集合的根节点，从而两个集合拥有相同的根节点，即合并为同一个集合

void gather_union(int *father, int x, int y) {
    int fx = findFather(father, x);
    int fy = findFather(father, y);
    if (fx != fy) {
        father[fx] = fy;
    }
}

应用： PTA L2-010