并查集

并查集是一种集合结构，用来处理集合的合并和查询问题。

主要有两个函数:合并和查询

合并函数表示合并两个不同的集合

查询表示当前元素属于那个集合

逻辑结构是单链表的结构，每个节点向上指向一个属于的集合的代表元素，这个集合的代表元素的next指向它自己成环，表示这个集合的代表元素就是这个有环的节点

牛客测试链接

#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>
#define u unsigned
#define ll long long
#define sc scanf
#define pr printf 
#define fr(i, j, n) for (int i = j; i < n; i++)
#define N 1000001//最大集合个数 

int n;//集合的个数 
int m;//操作的次数 
int f[N];//f[i]表示元素i的下一个元素是谁，如果f[i]等于i那么f[i]就是整个集合的代表元素 
int b[3];//读入输入的数

//查询元素x在那个集合里面 
int find(int x) {
	if (x != f[x]) {//只要不是集合的代表元素 
		f[x] = find(f[x]);//路径压缩 
	}
	
	return f[x];//返回集合的代表元素，向下传递的过程 
}
 
//判断元素a和b是不是在同一个集合当中 
bool isSameSet(int a, int b) {
	return find(a) == find(b);//判断代表两个集合的代表元素相同不相同就可以了 
}

//合并两个集合 
void unionSet(int a, int b) {
	f[find(a)] = find(b);//直接左边的合并到右边，对应着指向根节点 
}

int main(int argc, char* argv[])
{
	sc("%d %d", &n, &m);
	
	//初始化集合 
	for (int i = 1; i <= n; i++) {
		f[i] = i;
	}
	
	while(m--) {
		sc("%d%d%d", b, b + 1, b + 2);
		
		if (b[0] == 2) {
			unionSet(b[1], b[2]);
		}
		else {
			if (isSameSet(b[1], b[2])) {
				pr("Yes\n");
			}
			else {
				pr("No\n");
			}
		}
	} 
	
	return 0;
}

并查集的时间复杂度很高效，每个操作的时间复杂度近似为O(1)，本质是反阿克曼函数即O(a(n))，所以近似为O(1)。