[C++知识库]高级数据结构---并查集

高级数据结构—并查集

原理：参考趣学数据结构

代码：

#include<stdio.h>
#include<stdlib.h>
#define N 100
int father[N];
int find(int x) {//寻找共同祖先
	if (x != father[x]) {
		father[x] = find(father[x]);
	}
	return father[x];//找到了祖先是自己,不能是x自己，一定是x的祖先
}
void merge(int x1, int x2) {//将二个有关系的结点合并，时间复杂度为O(2elogn)
	int p = find(x1);
	int q = find(x2);//先查找祖先
	if (p == q) {
		return ;
	}
	else if (p > q) {//合并到祖先小的
		father[x1] = q;
	}
	else {
		father[x2] = p;
	}
	return;
}
int main() {
	printf("输入元素的个数:");
	int n;
	scanf_s("%d",&n);
	for (int i = 1; i <=n; i++) {
		father[i] = i;
	}
	int e1, e2;
	printf("输入有关系的元素对:\n");
	int eNumber;
	scanf_s("%d", &eNumber);
	for (int i = 0; i < eNumber; i++) {
		scanf_s("%d%d", &e1, &e2);
		merge(e1, e2);
	}
	printf("判断二个人是否有亲戚关系:\n");
	scanf_s("%d%d", &e1, &e2);
	int p = find(e1), q = find(e2);
	if (p == q) {
		printf("%d和%d二个人有亲戚关系:\n",e1,e2);
	}
	else {
		printf("%d和%d二个人没有亲戚关系:\n", e1, e2);
	}
	system("pause");
	return 0;
}

测试截图：

时间复杂度O(elogn)，空间复杂度O(1)

如果存在什么问题，欢迎批评指正！谢谢！