并查集是一种集合结构,用来处理集合的合并和查询问题。
主要有两个函数:合并和查询
合并函数表示合并两个不同的集合
查询表示当前元素属于那个集合
逻辑结构是单链表的结构,每个节点向上指向一个属于的集合的代表元素,这个集合的代表元素的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)。
标签:元素,int,查集,集合,include,find,define From: https://www.cnblogs.com/lwj1239/p/17980684