并查集

什么是“并查集”？

可以这么理解，并查集就是查询两个元素之间有没有什么关联，就像一个家族，你兄弟姐妹的亲戚可以算做你亲戚。

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

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

• 合并（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【模板】并查集

题目描述

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

输入格式

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

接下来 行，每行包含三个整数 。

当 时，将 与 所在的集合合并。

当 时，输出 与 是否在同一集合内，是的输出 Y ；否则输出 N 。

输出格式

对于每一个 的操作，都有一行输出，每行包含一个大写字母，为 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

提示

对于 的数据，，。

对于 的数据，，。

对于 的数据，，，，。

AC code:

//And in that light,I'll find deliverance;;
#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;


}

最小生成树

最小生成树有两种算法，一种是Prim算法，还有一种是Kruskal算法。

Prim算法：

Kruskal算法：