上一次写并查集是在看《数据结构》的时候写了树模型的拓展，当时那一章讲到了并查集，并提出了基本的思想。

并查集是我在第一次寒假集训学到的，当时学完写了总结月球美容计划之并查集。

今天在看生成树的时候，图论那本书又讲到了并查集。

经过各种资料的查阅，确定并查集并没有特别深入的应用，并查集只不过就是一种判断集合属性的方法，说白了，就是有若干种关系，判断谁和谁是同一种关系。

并查集算法是由3个函数组成的，就三个函数：

初始化函数

根据初始化的不同，并查集有两种写法，这两种写法没有优劣差异，就是初始化不同而已。

初始化为-1

int bc[100];

int UFset1()
{
    for(int i = 0;i < 100;i++)
        bc[i] = -1;
}

初始化为-1是《数据结构》和《图论》都采取的方法，但我学的时候是使用的第二种初始化

初始化为下标

int UFset2()
{
    for(int i = 0;i < 100;i++)
        bc[i] = i;
}

初始化的不同，在剩下两个函数直接造成细节上的差异，但是并没有造成时间复杂度和空间复杂度的差异。

查找函数

查找函数便是用来查找任一元素的根结点（祖先），而在并查集算法中，唯一的优化便是对查找函数的优化。

未优化的查找函数

//初始化为-1
int fin1 (int a)  //查
{
    int r = a;

    while (-1 != bc[r])
        r = bc[r];

    return r;
}

//初始化为下标
int fin2 (int a)  //查
{
    int r = a;

    while (r != bc[r])
        r = bc[r];

    return r;
}

因为并查集数组bc[]，存储的是当前结点的父结点，溯流而上，就能找到根结点，找到之后便返回根结点。

对查找函数的优化

//初始化为-1
int fin1 (int a)  //查
{
    int r = a;

    while (-1 != bc[r])
        r = bc[r];

    while (r != bc[a])  //优化，压缩路径
    {
        int t = bc[a];
        a = bc[a];
        bc[t] = r;
    }

    return r;
}

//初始化为下标
int fin2 (int a)  //查
{
    int r = a;

    while (r != bc[r])
        r = bc[r];

    while (r != bc[a])  //优化，压缩路径
    {
        int t = bc[a];
        a = bc[a];
        bc[t] = r;
    }

    return r;
}

因为bc数组是记录前驱（父结点）的一棵多叉树，那么如果存在最坏情况（整棵树是线形存在），那么每次查找将最高消耗O(n)，也就是说，如果树的深度越低，那么，查找效率越高。因此对其优化、压缩路径。

合并函数

我们可以用查找函数来判断是非属于同一个集合，用合并函数来把两个集合合并成一个集合。

对于合并集合，函数，初始化成什么对其没有影响。

void Union(int R1,int R2)
{
    int fa = fin(R1),fb = fin(R2);
    bc[fa] = fb;
}

 进一步优化

在图论这本书了提到了一个灰常奇妙的优化。

原理很简单，这个并查集浪费时间在查找上，因为如果树长的很奇葩（线形），那么查找时间将灰常壮观，因此，在查找函数中对其压缩路径，来解决这个问题，那么压缩完路径之后，深度不超过3，那么，查找的时间复杂度解决了，但是还有一个东西浪费时间，就是压缩路径本身。

这样想，如果我们在建树的过程中就尽量让树平衡（相关概念参考：数据结构之二叉树），那么在压缩路径的时候，也会节省一些时间。

至于怎么实现，书中给出的解决方案是靠根结点来记录这个根结点下有多少子节点。

首现，要选择初始化为-1的那种方案，然后对查找进行修改

//初始化为-1
int fin1 (int a)  //查
{
    int r = a;

    while (bc[r] >= 0)  //在这里修改了，
        r = bc[r];      //因为如果是根结点，其值为负数而不仅为-1

    while (r != bc[a])  //优化，压缩路径
    {
        int t = bc[a];
        a = bc[a];
        bc[t] = r;
    }

    return r;
}

然后对合并函数进行修改：

void Union(int R1,int R2)
{
    int fa = fin(R1),fb = fin(R2);
    int tmp = bc[fa] + bc[fb];  //结点个数、负数

    if(bc[fa] > bc[fb])    //加权法则
    {
        bc[fa] = fb;
        bc[fb] = tmp;
    }else
    {
        bc[fb] = fa;
        bc[fa] = tmp;
    }
}