博客

1、子集结构体：

parent

为每个子集的根，

rank

为秩

struct Subset
{
	int parent;
	int rank;
}; 

2、初始化：

一开始每个顶点自成一个子集，它们的

parent

指向自身，

rank

初始化为

0


Subset* makeSet(int n)
{
	Subset *subset = new Subset[n];
	for(int i = 0; i < n; i++)
	{
		subset[i].parent = i;
		subset[i].rank = 0;
	}
	return subset; 
} 

3、查找：查找的时候路径压缩

subsets[i].parent = find(subsets, subsets[i].parent);


int find(Subset subsets[], int i)	
{
	if(subsets[i].parent != i)
	{
		subsets[i].parent = find(subsets, subsets[i].parent);		//路径压缩 
	}
	return subsets[i].parent;
}

4、给定两个集合的根rank值作比较，

rank

值小的合并到

rank

值大的集合里去

void unionSet(Subset subsets[], int x, int y)
{
	int xroot = find(subsets, x);
	int yroot = find(subsets, y);
	if(xroot == yroot)
	{
		return ;
	} 
	if(subsets[xroot].rank < subsets[yroot].rank)
	{
		subsets[xroot].parent = yroot;
	}
	else if(subsets[xroot].rank > subsets[yroot].rank)
	{
		subsets[yroot].parent = xroot;
	}
	else
	{//subsets[xroot].rank > subsets[yroot].rank
		subsets[yroot].parent = xroot;
		subsets[xroot].rank++;
	}
}

5、把他们放到类里的话：

class Subset
{
public:
	int* parent;
	int* rank;
	Subset(int n)
	{
		parent = new int[n];
		rank = new int[n];
		for (int i = 0; i < n; i++)
		{
			parent[i] = i;
			rank[i] = 0;
		}
	}
	int find(int x)			//找x的root 
	{
		if (parent[x] != x) 
		{
			parent[x] = find(parent[x]);	//压缩路径 
		}
		return parent[x];
	}
	void unionSet(int x, int y)
	{//将x和y所在集合合并
		int xroot = find(x);			 
		int yroot = find(y);
		if(xroot == yroot)
		{
			return;
		}
		
		if (rank[xroot] < rank[yroot])
		{
			parent[xroot] = yroot;
		}
		else if (rank[xroot] > rank[yroot])
		{
			parent[yroot] = xroot;
		}
		else
		{//rank[xroot] == rank[yroot]
			parent[yroot] = xroot;
			rank[xroot]++;
		}
	}
};