并查集
并查集實際上就是并集和查集的過程家乘。集(集合)可以理解為一棵樹，即一個根結點連著無數個子節(jié)點耀找。
例題解析
輸入格式：
第一行包含兩個整數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
初始化
并查集要有一個記錄每個節(jié)點的根節(jié)點的地址 (father[])，開始時將每個節(jié)點獨立開來旨袒，(后面再進行合并操作)
int *father = new int[num + 1];
for (int i = 1; i <= num; i++) { //初始化 將祖先設為自己
father[i] = i;
}
查找
查找一個元素再其所在集合中的根節(jié)點(father)砚尽，可用來判斷兩個元素是否再同一個集合當中
當一個節(jié)點的father是它本身，則說明該節(jié)點是該集合的根節(jié)點
int findFather(int *father, int x) {
int i = x;
while (father[i] != i) {
i = father[i];
}
return i;
}
合并
將兩個集合合并起來必孤，即將一個集合的根節(jié)點的father設為另一個集合的根節(jié)點隧魄，從而兩個集合擁有相同的根節(jié)點，即合并為同一個集合
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
