博客

今天写的这个并查集

说实话一开始还是有一些绕的，你得明白x代表什么，s[x]代表什么

搞懂之后基本就没问题了

在Union优化的操作时，合并树的时候，一定要先改变大树根节点的数值，如果在合并完小树之后，就会将本身根节点的次序加到-1上面

在main函数里面，每操作一步我就把关键的数值给出来了，可以帮助理解

#include<iostream>
using namespace std;
#define MAXSIZE 20

int s[MAXSIZE];
//x为元素的下标
//s[x]为元素的父节点的下标


//初始化为-1
void Init(int s[]) {
	for (int i = 0; i < MAXSIZE; i++)
		s[i] = -1;
}

//查找结点的根
int Find(int s[], int x) {
	//root给出的是结点次序
	while (s[x] > 0) {
		x = s[x];
	}
	return x;
}

//优化查找
int _Find(int s[], int x) {
	int root = x;//根节点下标
	while (s[root] > 0) {//找到根
		root = s[root];
	}
	while (x != root) {//把路径上的结点挂在根下面
		int y = x;
		x = s[x];
		s[y] = root;
	}
	return root;
}

//合并
void Union(int s[], int root1, int root2) {
	//root1和root2不能相同，这里就不判断了
	s[root2] = root1;//变为他的孩子
}

//优化合并
void _Union(int s[], int root1, int root2) {
	//同样root1和root2不相同，这里也不先不做判断
	int x = _Find(s, root1);//1的根
	int y = _Find(s, root2);//2的根
	if (s[x] > s[y]) {//y,也就是root2是大树，这里是负数，不要忘了
		s[y] = s[y] + s[x];
		s[x] = y;
		//要先合并结点的个数，然后再改变父节点下标
	}
	else {
		s[x] = s[x] + s[y];
		s[y] = x;
	}
}

int main() {
	int s[MAXSIZE];
	Init(s);

	int x=_Find(s, 4);
	cout << x << endl;
	_Union(s, 4, 5);
	//把5挂在4下面，s[4]=-2，s[5]=4

	_Union(s, 5, 6);
	//把6挂在4的下面，s[4]=-3
	cout << "s[4]:" << s[4] << endl;

	_Union(s, 1, 3);
	//3挂在1下面，s[1]=-2，s[3]=1
	cout << "s[3]:" << s[3] << endl;

	_Union(s, 3, 6);
	//这是两个集合，s[1]=-2，s[4]=-3
	//会把1挂在4的下面，s[4]=-5
	cout << "s[4]:"<<s[4] << endl;

	_Find(s, 3);
	//会优化，把3直接挂在根节点4的下面
	//操作后，会把s[3]=4
	//这里与上面的s[3]=1形成对比，代表查找优化了
	cout << "s[3]:" << s[3] << endl;
	return 0;
}