不相交集python实现

1.不相交集是解决等价关系的一种数据结构，执行合并和查找的速度都很快，M次执行合并和查找的执行时间为（M*logN）。

在一个集合中。对于每一对元素(a,b)，a,b∈S，对于关系R假设满足以下三个条件，则成关系R为等价关系：

(1)自反性  对于全部a∈S,aRa

(2)对称性   aRb当且仅当bRa

(3)传递性   若aRb且bRc,则aRc

有关不相交集的介绍和C语言实现，点此查看

本文介绍的是不相交集的find和union操作的python实现:

def init(a):

	for i in range(0,110):

		a.append(-1);

def unionset(root1,root2):              #依照大小求并

	tmp=a[root1]+a[root2];

	if a[root1]<=a[root2]:

		a[root2]=root1;

		a[root1]=tmp;

	else :

		a[root1]=root2;

		a[root2]=tmp;

def unions(root1,root2):                #依照高度求并

	if a[root1]>a[root2]:

		a[root1]=root2;

	else:

		if a[root1] is a[root2]:   #仅仅有在高度同样的时候才进行合并

			a[root1]=a[root1]-1;

		a[root2]=root1;

def find(a,x):

	if a[x]<=-1:

		return x;

	else :

		return find(a,a[x]);

a=[];            #測试代码

init(a);

unionset(1,2);   #按大小求并

unionset(3,4);

unions(5,6);     # 按高度求并

unions(5,7);

print find(a,2);

unionset(1,3);

print find(a,4);

print find(a,5);

print find(a,7);