union find 即 并查集 算法是在本书的 1.5 节中作为一个样例来学习的，可知其是非常基础的一种算法，本书给出了三种实现。

1. quick-find 算法 O(N^2)

即把主要工作放到 union 中完成，以 hdu OJ 1232 为例

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int towns[1002] = {0};
int count = 0,size=0;

int find(int p) {
    return towns[p];
}

int Union(int p, int q) {
    int pVal = find(p);
    int qVal = find(q);

    if(pVal == qVal) return count;

    for(int i=1;i<=size;i++) {
        if(towns[i] == qVal) {
            towns[i] = pVal;
        }
    }
    return (--count);

}

int main() {
    int n=0,m=0;
     while(scanf("%d%d",&n,&m)!=EOF){
         if(n==0)break;
         size = n;
         count = n-1;
         for(int i=1;i<=size;i++) {
             towns[i] = i;
         }
         for(int i=0;i<m;i++) {
             int p=0,q=0;
             scanf("%d %d",&p,&q);
             Union(p,q);
         }
         printf("%d\n",count);
     }

}

2. quick-union 算法，用树表示连通分量,同样以 hdu OJ 1232 为例

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int towns[1002] = {0};
int count = 0,size=0;

int find(int p) {
    while(p != towns[p]) p = towns[p];
   return p;
}

int Union(int p, int q) {
    int pRoot = find(p);
    int qRoot = find(q);

    if(pRoot == qRoot) {
      return count;
   } else {
      towns[qRoot] = pRoot;
   }
    return (--count);

}

int main() {
    //同上....

}

3. 加权 quick-union 算法

这个算法本质上和第二种算法是一致的，都是利用树来表示连通分量，只是在第二种算法中会有可能将一个大树连到一个树树上，导致在 find 时增加了不必要的次数，加权算法就是记录每一棵树，即每一个连通分量所包含的元素数量，在 Union 时总是保证将小树直接连在大树的根节点上。

#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
int towns[1002] = {0};
int size[1002] = {0};
int count = 0;

int find(int p) {
    while(p != towns[p]) p = towns[p];
   return p;
}

int Union(int p, int q) {
    int pRoot = find(p);
    int qRoot = find(q);

    if(pRoot == qRoot) {
      return count;
   } else {
      //比较两棵树的大小  
      if(size[p] < size[q]) {
         towns[pRoot] = qRoot;
         size[qRoot] += size[pRoot];
      } else {
         towns[qRoot] = pRoot;
         size[pRoot] += size[qRoot];
      }
      
   }
    return (--count);

}

int main() {
    int n=0,m=0;
     while(scanf("%d%d",&n,&m)!=EOF){
         if(n==0)break;
         count = n-1;
         for(int i=1;i<=n;i++) {
             towns[i] = i;
            //size 用于记录每个连通分量所包含的节点数
            size[i] = i;
         }
         for(int i=0;i<m;i++) {
             int p=0,q=0;
             scanf("%d %d",&p,&q);
             Union(p,q);
         }
         printf("%d\n",count);
     }

}