数据结构之不相交集类

  不相交集类是解决等价关系问题的一种非常有效的手段！等价关系是一种关系R,他满足自反性，对称性与传递性。有人说散列是最艺术的数据结构，优先队列是最优雅的数据结构

而不相交集类就是最简洁的数据结构！这些说法我非常赞同，因为不相交集类的实现代码真的太简洁了。

    处理等价关系最重要的问题就是要判断任意两个元素a，b是等价的，根据离散数学的知识，一个等价关系就决定了一个划分，所以我们要判断a，b是否属于同一个划分，而每个划分都会有一个代表元，所以我们只需要判断a，b，是否属于同一个代表元就行了！

   而不相交集类就实现了这个功能，首先他提供了union操作，如union(a,b)表示a，b是等价的，一般可以让b记住a，不过更有效的办法是按高度求并，即如果a高的话就让b记住a，否则就让a记住b。这里的“记住”其实就是一个指向，这种几何结构与树的结构刚好反过来了。他是由子节点指向父节点。

  还有就是find操作，其实就是找代表元，最容易想到的就是找到根节点就行了，不过我们不止这样，我们在找根节点的时候还对路径高度进行了压缩！从我的代码你就会发现仅仅一句代码就实现了这种听起来很麻烦的事，所以说这是一种特别简洁的数据结构！

 下面就是我的代码：

//Disjsets.h

#ifndef DISJSETS_H
#define DISJSETS_H
#include<iostream>
#include<vector>
using namespace std;
class Disjsets
{
private:
	vector<int>s;
public:
	Disjsets(int num):s(num)
	{
		for(int i=0;i<s.size();i++)
			s[i]=-1;
	}
	int find(int x)     //路径压缩查找
	{
		if(s[x]<0)
			return x;
		else
			return s[x]=find(s[x]);

	}
	void(unionSets)(int root1,int root2)  //按高度求并
	{
		if(s[root1]<s[root2])
			s[root1]=root2;
		else
		{
			if(s[root1]==s[root2])
				s[root1]--;
			s[root2]=root1;
		}
	}
};
#endif // DISJSETS_H

数据结构之不相交集类,布布扣,bubuko.com

数据结构之不相交集类

原文：http://blog.csdn.net/alop_daoyan/article/details/22603167