并查集与最小生成树（Kruskal算法）
并查集
什么是“并查集”？
可以这么理解，并查集就是查询两个元素之间有没有什么关联，就像一个家族，你兄弟姐妹的亲戚可以算做你亲戚。
并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。
顾名思义，并查集支持两种操作：
- 合并（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]);
}
这就是并查集的简单的实现过程（一般不会超时吧）。如果遇到数据量巨大的时候，我们可以对查询与合并进行优化，这是后话了。
题目描述
如题，现在有一个并查集，你需要完成合并和查询操作。
输入格式
第一行包含两个整数 ,表示共有
个元素和
个操作。
接下来 行，每行包含三个整数
。
当 时，将
与
所在的集合合并。
当 时，输出
与
是否在同一集合内，是的输出
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算法：
