[数据结构与算法]C并查集的两个重要函数union和find的实现C++

今天看了并查集的实现，重点是两个函数find 以及union 现记录如下。
视频参考
讲解

#include <iostream>
#include<vector>
using namespace std;
//中间包括了find与union的快和慢的版本
class UnionFind
{
public:
	//find 快 union慢
	int size;
	vector<int> data;
	UnionFind(int _size = 5) :size(_size) {
		cout <<"size " <<size << endl;
		data.resize(size);
	for (int i = 0; i < size; i++)
		data[i] = i;
	
	}

	int find(int index)
	{    
		if (index >= size)
		{
			cout << "index " << index << endl;
			cout << "error " << endl;
			return -1;
		}
		return data[index];
	}

	int Quick_Find(int index)
	{
		while (index != data[index])
		{
			index = data[index];
		}
		return index;
	}
	void union_x_y(int x, int y);
	void Quick_union_x_y(int x,int y)
	{
		int temp_x = find(x);
		int temp_y = find(y);

		if (temp_x != temp_y)
		{
			data[temp_y] = temp_x;
		}
	}
	bool isconnect(int x, int y)
	{
		return Quick_Find(x) == Quick_Find(y);
	}


};

void UnionFind::union_x_y(int x, int y)
{
	int temp_x = find(x);
	int temp_y = find(y);

	

	if (temp_x != temp_y)
	{
		for (int i = 0; i < size; i++)
		{
			if (data[i] == temp_y)
				data[i] = temp_x;
		}
	}
}
//按照秩合并
class Union_Rank
{
public:
	int size;
	vector<int>data;
	vector<int>rank;

	Union_Rank(int _size = 10) :size(_size)
	{
		data.resize(size, 0);
		for (int i = 0; i < size; i++)
			data[i] = i;
		rank.resize(size, 1);
	}

	int find(int index)
	{
		if (index >= size)
		{
			cout << "error " << endl;
			return -1;
		}
		while (index != data[index])
			index = data[index];

		return index;
	}

	void union_x_y(int x, int y)
	{
		int temp_x = find(x);
		int temp_y = find(y);

		if (temp_x != temp_y)
		{
			if (rank[temp_x] > rank[temp_y])
				data[temp_y] = temp_x;
			else
				if (rank[temp_x] < rank[temp_y])
					data[temp_x] = temp_y;
				else
				{
					data[temp_x] = temp_y;
					rank[temp_y]++;
				}
		}
	}

	bool is_connect(int x,int y)
	{

		return find(x) == find(y);
	}

};



//压缩路径递归思想
class Union_Pres
{
	vector<int>data;
	
	int size;
	Union_Pres(int _size = 100) :size(_size)
	{
		data.resize(size);
		for (int i = 0; i < size; i++)
			data[i] = i;
	}

	int find(int index)
	{
		if (index >= size)
		{
			cout << "error " << endl;
			return -1;
		}

		if (index == data[index])
			return index;

		return data[index] = find(data[index]);
	}


	void union_x_y(int x,int y)
	{
		int temp_x = find(x);
		int temp_y = find(y);

		if (temp_y != temp_x)
		{

			data[temp_y] = temp_x;
		}

	}


};



//基于压缩与按照秩合并
class Union_Final
{
	vector<int>data;
	vector<int>rank;
	int size;
	Union_Final(int _size=100):size(_size)
	{
		data.resize(size);
		rank.resize(size,1);
		for (int i=0;i<size;i++)
		{
			data[i] = i;
		}

		
	}
	
	int find(int x)
	{
		if (x == data[x])
			return x;

		return data[x] = find(data[x]);

	}
		//按秩合并
	void union_x_y(int x, int y)
	{
		int temp_x = find(x);
		int temp_y = find(y);

		if (temp_x != temp_y)
		{	
			if (rank[temp_x] > rank[temp_y])
			{
				data[temp_y] = temp_x;

			}
			else
			{
				if(rank[temp_x] < rank[temp_y])
					data[temp_x] = temp_y;
				else
				{
					data[temp_x] = temp_y;
					temp_y++;
				}

			}
		
		}
	}

};
int main()
{
	int size = 100;
	Union_Rank test(size);
	

	test.union_x_y(1, 3);
	test.union_x_y(2, 5);
	test.union_x_y(3, 7);
	
	if (test.is_connect(1, 7))
		cout << "connected " << endl;
		

	return 0;
}