并查集的相关函数

  1：相关知识

（1）树：

    并查集主要是在解决树的问题中的一种算法，那么什么是树？树其实就是由N个结点通过N-1条边相连且树内不能有环路的一种结构。

树可以有很多的父结点，但一个树中只有一个根结点，通常定义一个数组per[n]  (n=1,2,3.....n),用数组序号 i 表示树中的一个元素，per[i]表示元素i的父结点。

根结点的父结点是其本身。

  2：并查集的相关函数  （首先定义了一个数组per[100]）  

（1）  find函数----找某个元素的根结点   

   int find(int x){

 int r = x;

 while(r != per[r])

  r = per[r];

 return r;

     }

 （2）link（）合并根结点结点

  void join (int x, int y){

 int fx = find(x);

 int fy = find(y);

 if(fx != fy)

  per[fx] = fy;

  }

（3）在find函数中压缩路径

int find(int x)

{

 int r = x;

 while(r != per[r])

  r = per[r];

 int i ,j;

 i = x;

 while(i != r){

  j = per[i];

  per[i] = r;

  i = j;

 }

 return r;

}

（3）判断环以及环的个数

int flag=1,count=0

int join(int x,int y){

   int fx=find(x);

   int fy=find(y);

   if(fx!=fy){

    per [fx] = fy;

   else

   { flag=0;//flag=0;说明能构成环

     count++;//计算能构成的环总数

     }

}

（4）计算一棵树中的结点总数

  定义另一个数组an[10000]并对其中元素初始化为一，刚开始树的中的结点都未相连，每个元素的根结点都是其本身。

  当连一个结点是就把an[i]中的值加到其父结点中，最后当一个树连好时，根结点上的对应的an[i]的值就是整个树的结点数。

  1.初始化：int per[1100],an[1100];

 void init(){

 for(int i =1; i <= N; ++i)

 {

     per[i] = i;

     an[i] = 1 ;

    }

}

 2.连接结点并计算结点数

 void join (int x, int y){

 int fx = find(x);

 int fy = find(y);

 if(fx != fy)

       {  

  per[fx] = fy;

                an[y]+=an[x];//将结点数存在根结点上

   }