并查集
并查集实际上就是并集和查集的过程。集(集合)可以理解为一棵树，即一个根结点连着无数个子节点。
例题解析
输入格式：
第一行包含两个整数N、M，表示共有N个元素和M个操作。
接下来M行，每行包含三个整数Zi、Xi、Yi
当Zi=1时，将Xi与Yi所在的集合合并
当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N
输出格式：
如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为Y或者N
输入输出样例
输入样例：
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
输出样例：
N
Y
N
Y
AC代码如下
test.cpp
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
int findFather(int *father, int x) {
int i = x;
while (father[i] != i) {
i = father[i];
}
return i;
}
void gather_union(int *father, int x, int y) {
int fx = findFather(father, x);
int fy = findFather(father, y);
if (fx != fy) {
father[fx] = fy;
}
}
int main() {
ifstream infile;
infile.open("input.txt");
int num, num_oper;
infile >> num >> num_oper;
int *father = new int[num + 1];
for (int i = 1; i <= num; i++) { //初始化 将祖先设为自己
father[i] = i;
}
int oper, x, y;
for (int i = 0; i < num_oper; i++) {
infile >> oper >> x >> y;
if (oper == 1) {
gather_union(father, x, y);
}
else {
int fx = findFather(father, x);
int fy = findFather(father, y);
if (fx == fy) {
cout << "Y" << endl; //x和y同属一个集合
}
else {
cout << "N" << endl; //x和y不属于同一集合
}
}
}
infile.close();
return 0;
}
input.txt
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
初始化
并查集要有一个记录每个节点的根节点的地址 (father[])，开始时将每个节点独立开来，(后面再进行合并操作)
int *father = new int[num + 1];
for (int i = 1; i <= num; i++) { //初始化 将祖先设为自己
father[i] = i;
}
查找
查找一个元素再其所在集合中的根节点(father)，可用来判断两个元素是否再同一个集合当中
当一个节点的father是它本身，则说明该节点是该集合的根节点
int findFather(int *father, int x) {
int i = x;
while (father[i] != i) {
i = father[i];
}
return i;
}
合并
将两个集合合并起来，即将一个集合的根节点的father设为另一个集合的根节点，从而两个集合拥有相同的根节点，即合并为同一个集合
void gather_union(int *father, int x, int y) {
int fx = findFather(father, x);
int fy = findFather(father, y);
if (fx != fy) {
father[fx] = fy;
}
}
应用： PTA L2-010
