struct lset
{
int p[N],sz;
void link(int x, int y) {
   if (x == y) return;
   if (x<y) p[y] = x;
   else p[x] = y;
}
void makeset(int n) {   //初始化
   sz = n;
   for (int i=1;i<=n;i++) {
    p[i] = i;
   }
}
int findset(int x) {   //查找并降低树的高度
   if (x != p[x]) p[x] = findset(p[x]);
   return p[x];
}
void unin(int x, int y) {   //合并两个集合
   link(findset(x), findset(y));
}
void compress() {    //树最简化，高度为2
        for (int i = 1; i < =sz; i++) findset(i);
}
};

操作之初始化：

struct lset pset;
pset.makeset(n);

两元素a,b在同一集合：

pset.unin(a, b);

终态简化的集合：

pset.compress();

3625 并查集加最小连通图

2421 同上

并查集

int p[N],d[N];

int parent(int i)

{

     if(p[i]==i)

         return i;

     return p[i]=parent(p[i]);

}

int link(int a,int b)

{

     int t1=parent(a);

     int t2=parent(b);

     if(t1<=t2){

         p[t2]=t1;

         return t1;

     }

     p[t1]=t2;

     return t2;

}

初始化：

                 for(i=1;i<=n;i++)

              p[i]=i;

当集合分成两份并告诉一些不在同一集合的组合数<a,b>时：

d[i]记录与i不在同一集合的，初始化为0，只记录部分小的i的d[i]k=parent(a);

j=parent(b);

if(d[k]){

         d[k]=link(d[k],j);

         if(d[j]) d[d[k]]=link(d[j],k);

         else d[d[k]]=k;

}

else{

if(d[j]){ d[j]=link(d[j],k);d[d[j]]=j;}

     else{

         d[k]=j;

         d[j]=k;

     }

}

如果在遇到建立好的并查集中会涉及到删除关系（让一些点独立出来）的情况，可以考虑复制这些点进一步处理。

例子参考：http://acm.hdu.edu.cn/showproblem.php?pid=2473

#include <iostream> using namespace std ;#define M 100001 int f [M *5 ],p [M ]; int tag [M *5 ]; int father ( int a ){ if (f [a ] == a ) return a ; return f [a ] = father (f [a ]);} void link ( int a , int b ){ int x = father (a ); int y = father (b ); if (x == y ) return ; if (x > y ){ f [a ] = f [x ] = y ; tag [y ] += tag [x ]; } else { f [b ] = f [y ] = x ; tag [x ] += tag [y ]; }} int main (){ int n ,m ,a ,b ,i ; char c [2 ]; int ncase = 1 ; while (scanf ("%d%d" ,&n ,&m ),n ) { for (i = 0 ;i < n ;i ++) f [i ] = i ; for (i = 0 ;i < n ;i ++) p [i ] = i ; for (i = 0 ;i < n ;i ++) tag [i ] = 1 ; for (i = 0 ;i < m ;i ++) { scanf ("%s" ,&c ); if (c [0 ] == 'M' ) { scanf ("%d%d" ,&a ,&b ); if (a == b ) continue ; link (p [a ],p [b ]); } else { scanf ("%d" ,&a ); int x = father (p [a ]); if (tag [x ] > 1 ){ tag [x ] --; tag [n ] = 1 ; f [n ] = n ; p [a ] = n ++; } } } int ans = 0 ; for (i = 0 ;i < n ;i ++) if (father (i ) == i ) ans ++; printf ("Case #%d: %d\n" ,ncase ++,ans ); } return 0 ;}