并查集算法理解

并查集主要就是解决判断两个点两个物体是否有关系，如在最小生成树kruskal算法中是为了判断两个村庄是否已经连通，在练习中有判断学生的宗教信仰，和某个人有关系的其他人等等之类的问题。

对于并查集的实现是先初始化f[]数组，在不知道关系的情况下每个点的父亲祖先都是自己本身，当两个点有关系时，改变f[]数组值，根据啊哈算法上介绍是根据靠左原则存储父辈，将有关系的点都练习起来他们都有一个共同的祖先即根节点，在判断两个点是否有关系时，只需判断两点的根节点是否相同，相同则说明两点有关系；并查集也可查找共有几个组织（有几个点的根节点为自己本身则说明有几个组织）。

初始化：

for(i=1;i<=n;i++)
    f[i]=i;

模板：

int getf(int i)
{
	if(f[i]==i)
		return i;
	else
	{
		f[i]=getf(f[i]);
		return f[i];
	}
}
void merge(int u,int v)
{
	int t1,t2;
	t1=getf(u);
	t2=getf(v);
	if(t1!=t2)
	    f[t2]=t1;	
}