并查集

1 int findx(int x)
2 {
3     if(x!=parent[x])
4         parent[x]=findx(parent[x]);  //   回溯的时候压缩路径  这个是 压缩路径的精髓
5     return parent[x];  //   实际上我也看不出来  到底哪里好 ......
6 }
7 son :       1 3 8 9
8 parent :    1 1 3 8

并查集有两个优化。

一、按秩合并

描述：就是在对两个不同子集连接时，按照rank来连，也就是rank低的连在rank高的下面。rank高的做父亲节点。

作用，这样类似维护了一棵树，树是rank高的在上。

二、路径压缩

描述：假如fa数组已经嵌套了N层，那么传统的做法去找祖先要做N次，当N很大时，这种做法很没效率。

这是朴素查找的代码,适合数据量不大的情况：

int findx(int x)
{
   while(parent[x]!=x)        //     如果 这不是掌门的话  继续执行  向上寻找的 过程   
        x=parent[x];      //       直到  找到掌门   然后  就开始返回  所有的 x 都变成 掌门的身份证号码  然后就返回了 
   return x;
}

下面是采用路径压缩的方法查找元素：

/* 　　路径压缩　顾名思义就是将原来需要走的很长的路径很快的走过去用跳跃来相当于压缩　　　*/

int find(int x)
{
    int k,j,r;      
    r = x;
    while(r != parent[r])       //  
        r = parent[r];
    k = x;        
    while(k != r)           
    {
        j = parent[k];       
        parent[k] = r;
        k = j;              
    }
    return r;            
}