并查集概述

并查集的全名是Disjoint Set Union。

1

并查集就是解决若干元素所属的集合关系的一类问题
简单来说并查集一般有以下几个操作：将两个元素所在的集合合并；查找某个元素所在的集合（根节点）

2

初始化

一般的，在初始情况下，每个元素自成一个集合，这个集合的根节点就是元素本身。

用数组fa[]来记录该并查集的话，初始化应该是这样的：

void init(int x) {  //并查集元素个数
	for (int i = 1; i <= x; ++ i) fa[i] = i;
}

查找根节点

简单的，不断顺着数组fa[]“逆流而上”查找，直到fa[x] = x时就找到根节点了，可以用递归或者循环实现。

int get(int x) {  // 获取x的根节点
	if (fa[x] = x) return x;  //找到根节点后返回答案
	return get(fa[x]);
}

注意，并查集有可能遇到这样的糟糕情况：

当我们试图查找节点5的根节点时，我们需要遍历整个并查集才能找到节点1。在百万或以上的数据规模中，这种无意义的时间消耗是致命的，所以我们需要路径压缩，将上图的情况优化成这样：

这样从节点5就可以一次性找到节点1了。
代码优化后实现如下

int get(int x) {  // 获取x的根节点
	if (fa[x] = x) return x;  //找到根节点后返回答案
	return fa[x] = get(fa[x]); //在查找过程中将所有经过的点一并连接到根节点上
}

合并

将两个并查集合并，只要统一它们的父亲节点即可。当两个并查集拥有同一个根节点的时候，意味着它们是一个并查集。

举例，如图，合并并查集{1,2,3}和并查集{4,5}只需要将{1,2,3}的根节点置为4或将{4,5}的根节点置为1
像这样：

代码实现如下

void merge(int x, int y) { //将元素x和元素y所在的集合合并
	fa[get(x)] = get(y);
	//fa[get(y)] = get(x);  这也是一个可行的方案
}

3 例题

以洛谷P3367为例

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入输出格式

输入格式：

第一行包含两个整数N、M，表示共有N个元素和M个操作。
接下来M行，每行包含三个整数Zi、Xi、Yi
当Zi=1时，将Xi与Yi所在的集合合并
当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N

输出格式：

如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为Y或者N

输入输出样例

输入样例#1：

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

输出样例#1：

N
Y
N
Y

说明

时空限制：1000ms,128M
数据规模：
对于30%的数据，N<=10，M<=20；
对于70%的数据，N<=100，M<=1000；
对于100%的数据，N<=10000，M<=200000。

AC代码

#include <iostream>

int fa[10003];

void init(int x) {
    for (int i = 1; i <= x; ++ i) fa[i] = i;
}
int get(int x) {
    if (fa[x] == x) return x;
    return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
    fa[get(x)] = get(y);
}

int main () {
    std::ios::sync_with_stdio(false);
    register int i, j;
    int n, m, z, x, y;
    
    std::cin >> n >> m;
    init(n);
    for (i = 1; i <= m; ++ i) {
        std::cin >> z >> x >> y;
        if (z == 1) merge(x, y);
        if (z == 2) {
            if (get(x) == get(y)) std::cout << "Y\n";
            else std::cout << "N\n";
        }
    }
    
    return 0;
}