并查集

并查集是一种树型的数据结构，主要用于查询某元素是否位于某个集合当中以及集合间的合并。因此往往以森林的形式表现。而对于并查集的操作正如其名，主要是对集合的合并与查询。它的主要用途是构建连通分支。

在离散中我们可以通过连通分支的边看出简单无向图中各个节点的可达性，现假设有8个节点，现给出一组形如（x, y）（0 <= x,y <= 8）的数据，表示x与y节点间是相互可达的，数据如下：

1, 2
4, 5
3, 4
1, 4
6, 7
3, 8

那么通过画图我们可以得到以下连通分支，如图：

通过连通分支的边我们可以轻易地看出任意两个节点间是否相互可达，然而要如何在计算机中表示这样的连通分支以及查询某两个节点是否属于同一集合呢？

一种最简单的思想就是指定一个代表来代表一个连通分支，就上图而言存在两个连通分支，它们构成两个集合A={1,2,3,4,5}和B={6,7}，不妨指定1为集合A的代表，6作为集合B的代表，询问节点3与7是否在同一个连通分支内？由上图我们可以得到以下两棵树：

我们可以让计算机首先查询3的上级，发现为4，而4不是代表，因此继续查询4的上级，此时发现为1，而1恰是集合A的代表故停止查询。另外由节点7向上级查询，发现为节点6，而6恰是集合B的代表故停止查询，比较查询所得的两个代表发现不是同一个，因此计算机能判断出二者不在同一连通分支当中。以下是实现的函数代码：

int find_boss(int x)
{
     int r = x;
     while(pre[r] != r)     //pre[r]表示当前节点的上级节点，而代表节点也是最高级节点，因此它的上级就是它自身
     {
          r = pre[r];      //寻找根节点
     }                 
     int i = x, j;
     while(pre[i] != r)
     {
          j = pre[i];
          pre[i] = r;
          i = j;
     }              //优化路径
     return r;
}

注意，以上函数多了一项路径优化，这是为什么呢？以上述为例，我们第一次调用函数访问到了3所在集合的代表为1。如果此时要求访问8所在集合的代表，在优化前，计算机又得通过8->3->4->1这种顺序访问，然而实际上，在访问节点3所在集合的过程中我们就可以知道节点3和4都属于代表为1的集合。因此我们所做的优化就是，将pre[3]和pre[4]的值都改为1，所以在优化之后，计算机只要通过8->3->1这种顺序访问，同时在访问完节点8所在的集合后pre[8]的值也被改为1。这点优化对于大规模节点运算效率的提高很有必要。

另外为了进一步简练代码，以下给出了上式的递归写法：

int find_boss(int x)
{
     if(x == pre[x])
          return x;
     else
          return pre[x] = find_boss(pre[x]);
}

以上讲了如何实现对于节点所在集合的判断，接下来就涉及到到集合合并的实现，然而这一步意外的简单，所以我只以注释说明。以下是代码：

void join(int x, int y)
{
     int f1 = find_boss(p1), f2 = find_boss(p2);
     if(f1 != f2)       //分别找出p1,p2的代表f1,f2，如果f1 != f2就进行合并操作
          pre[f2] = f1;     //令f2的代表为f1，实现两集合的合并
}

到目前为止已经介绍完了并查集的主要实现思想，接下来就以杭电的一道题作为应用练习：http://acm.hdu.edu.cn/showproblem.php?pid=1232

以下是我的代码，另外此代码中还将涉及并查集的初始化问题。

#include <iostream>
#include <stdio.h>

using namespace std;

int pre[1100];

int find_boss(int x)
{
     if(x == pre[x])
          return x;
     else
          return pre[x] =
find_boss(pre[x]);
}

void join(int x, int y)
{
     int f1 = find_boss(p1), f2 = find_boss(p2);
     if(f1 != f2)
          pre[f2] = f1;
}

int main()
{
    int num_city, num_road;  
    while(scanf("%d", &num_city))
    {
         if(num_city == 0)
         {
              return 0;
         }
         scanf("%d", &num_road);
         int total = 0;
         for(int i = 1; i <= num_city; i++)
         {
            pre[i] = i;       //并查集初始化，也就是一开始时默认每个节点都是一个连通分支。
         }
         while(num_road--)
         {
              int p1, p2;
              scanf("%d %d", &p1, &p2);
              join(p1, p2);
         }
         for(int i = 1; i <= num_city; i++)
               if(pre[i] == i)
                   total++;
         printf("%d\n", total-1);
    }
    return 0;
}