[数据结构]并查集

什么是“并查集”？

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

顾名思义，并查集支持两种操作：

• 合并（Union）：合并两个元素所属集合（合并对应的树）
• 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合

并查集在经过修改后可以支持单个元素的删除、移动；使用动态开点线段树还可以实现可持久化并查集。（摘自OI WIKI）

并查集（easy.ver）的实现包含几个个步骤：

1.初始化数组

并查集通过构建一个一维数组来实现，本质上是维护一个森林。我们先定义出一个一维数组f[N]（其中N代表森林中元素个数）用来存放每一棵树的编号。一开始的时候每一棵树都是一个独立的集合。

代码实现如下：

for(int i=1;i<=n;i++) {
        f[i] = i;
    }

2.查询（Find）

我们需要沿着树向上移动，如果上一级是其父节点，则函数会继续进行查询，直至找到根节点（即祖宗节点）。

代码实现如下：

int find(int x) {
    if (f[x]!=x) {
        return f[x]=find(f[x]);
    }
    return f[x];
}

3.合并（Union）

我们由上一步查询可得知相对应的集合的祖宗节点（即根节点），我们只需要将这两个集合的祖父节点相连即可。

代码实现如下：

void union(){
    f[find(b)] = find(f[a]);
}

这就是并查集的简单的实现过程（一般不会超时吧）。如果遇到数据量巨大的时候，我们可以对查询与合并进行优化，这是后话了。

接下来我们看例题！！！

洛谷p3367【模板】并查集

题目描述

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

输入格式

第一行包含两个整数 $N,M$ ,表示共有 $N$ 个元素和 $M$ 个操作。

接下来 $M$ 行，每行包含三个整数 $Z_i,X_i,Y_i$ 。

当 $Z_i=1$ 时，将 $X_i$ 与 $Y_i$ 所在的集合合并。

当 $Z_i=2$ 时，输出 $X_i$ 与 $Y_i$ 是否在同一集合内，是的输出
Y ；否则输出 N 。

输出格式

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

样例 #1

样例输入 #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

提示

对于 $30\%$ 的数据，$N \le 10$，$M \le 20$。

对于 $70\%$ 的数据，$N \le 100$，$M \le 10^3$。

对于 $100\%$ 的数据，$1\le N \le 10^4$，$1\le M \le 2\times 10^5$，$1 \le X_i, Y_i \le N$，$Z_i \in \{ 1, 2 \}$。

AC code:

//And in that light,I'll find deliverance;
//可以和我打一辈子ACM吗？;
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int>PII;
const int N = 2e5 + 10;
int op;
ll f[N];

int find(int x) {
    if ( f[x] != x ) {
        return f[x] = find(f[x]);
    }
    return f[x];
}
int n, q;
int a, b;

void solve() {
    if (op == 1) {
        f[find(b)] = find(f[a]);
    }
    if (op == 2) {
        if (find(a) == find(b))
            cout << "Y" << endl;
        else
            cout << "N" << endl;
    }
}

int main() {
    IOS;
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        f[i] = i;
    }
    while (q--) {
        cin >> op >> a >> b;
        solve();
    }
    return 0;


}

这是我新生赛的一道题目，因为板子记错了WA了25发，呜呜呜呜呜呜呜~~~~