数据结构初级——并查集

啥是并查集

一般可能会有这样的问题，判断两个元素是否在同一集合中，或者合并两个集合
可能会写出这样的代码

int t = 2;// 一个集合的编号for (int i = 1; i <= n; i++) {if (f[i] != t) {f[i] = t;}}

当然这样的复杂度是非常高的，如果我们有很多次的询问和亿点点多的集合，那就要死掉了=。=

那并查集是如何操作的？

我们在每个集合选出一个代表元素，用来表示这个集合，在查询是否在同一个集合的时候，只需要判断这两个元素的代表元素f[x] == f[y]是否相同就可以了
而且合并也变的简单了，只需要将集合代表元素的元素标号改成另一个集合就好了f[当前集合的代表元素] = 另一个集合的代表元素

还存在的问题，可以想象，这样的话是一个类似树的结构，如果我们要询问两个在叶子节点的元素属于哪个集合，我们需要一路向上查询到根节点，这个东西是很慢的
如何优化这个问题
我们可以减小这个树的深度，让所有的元素都和代表元素直接相连，这样就可以直接比较这两个元素的代表元素了

一般的模板代码

int top[N];void init() {for (int i = 1; i <= n; i++)top[i] = i;}int find(int x) {return x == top[x] ? x : top[x] = find(top[x]);//核心在这里}top[find(x)] = find(y);//合并

例题

#include #include #define N_MAX 100000 + 1using namespace std;int n, top[N_MAX];int find(int x) {return x == top[x] ? x : top[x] = find(top[x]);}int main() {ios::sync_with_stdio(false);int m;cin >> n >> m;for (int i = 1; i <= n; i++) {top[i] = i;}while (m--) {int x, y, z;cin >> z >> x >> y;if (z == 1) {top[find(x)] = find(y);}if (z == 2) {puts(top[find(x)] == find(y) ? "Y" : "N");}}return 0;}