unionfindsets.cpp

来自「并查集算法主要实现在若干个不相交集合中的两个操作：第一判断一个集合是否在另一个集」· C++ 代码 · 共 65 行

#include<iostream>
#include<fstream>
using namespace std;
class Sets
{
public: 
	Sets(int);
	~Sets();
public:
	int Find(int);
	void Union(int, int);
private:
	int EleNum;
	int *Parents;
	int *Rank;
};
Sets::Sets(int n)
{
	EleNum = n;
	Parents = new int[EleNum];
	Rank = new int[EleNum];
	for(int i = 0; i < EleNum; i++)
	{
		Parents[i] = -1;
		Rank[i] = 1;
	}
}
Sets::~Sets()
{
	delete[] Parents;
	delete[] Rank;
}
int Sets::Find(int i)
{
	int r = i;
	while(Parents[r] != -1) 
		r = Parents[r];
	while(r != i)
	{
		int q = Parents[i];
		Parents[i] = r;
		i = q;
	}
	return r;
}
void Sets::Union(int i, int j)
{
	int a = Find(i);
	int b = Find(j);
	if(a == b) return;
	if(Rank[a] > Rank[b])
	{
		Parents[b] = a;
		Rank[a] += Rank[b]; 
	}
	else
	{
		Parents[a] = b;
		Rank[b] += Rank[a];
	}
}
void main()
{

}