对于并查集： 很多次都是迷迷糊糊，尤其是对并查集的优化：

1.路径压缩  2.按秩合并

对此个人整理了一下：

对于最基本的并查集建议看看： 

百度百科： 

以例题的形式分析，并用算法描述了

博客园：   对于有点基础的可以参考下，清晰明了

对于第二个优化按秩合并的部分处理有点异议：

if(rank[x] < rank[y])

              {

                  num[x]=y;

               

              }

              else if(rank[x]> rank[y])

              {

                  num[y]=x;

              }

              else rank[y]++;

看到很多博客上都是这么写的，就连维基百科上也是这么处理的！

个人感觉这样会大大使按秩合并的优化打折，这样处理应该比上面的哪个要严谨多了

           if(rank[x] <= rank[y])

              {

                  num[x]=y;

                  rank[y]+=rank[x];

              }

              else if(rank[x]> rank[y])

              {

                  num[y]=x;

                  rank[x]+=rank[y];

              }

而在sdutoj 2391测试  时间只是略快 

题目推荐：

poj 1611  The Suspects

模版题不解释 

 

#include
      
        #include
       
         #define N 30005 int num[N];int rank[N]; int match(int n) {
    if(n!=num[n])     num[n]=match(num[n]); return num[n]; } int main() {
    int n,m,k; while(scanf("%d%d",&n,&m),n+m)     {
    //memset(rank,1,sizeof(rank));         for(int i=0;i<=n;i++)         {
                num[i]=i; rank[i]=1;         } while(m--)         {
    int a,b,x,y;         scanf("%d%d",&k,&a); for(int i=1;i
       
      

sdut 2391  Dark roads

#include
      
        #include
       
         using namespace std; #define N 200005 int n,m,road; struct node  {
    int s,e,cost;  }root[N]; int num[N]; int cmp(node a,node b)  {
    return a.cost
       
      

 以上纯属个人见解，望大家批评指正