并查集的实现及优化

并查集是一种用于在森林中判断子图数量及点的归属的数据结构，由于其特殊的路径压缩操作，使得这一过程可以异常地快。

并查集主要由一个pre数组以及两个函数组成：find函数和join函数。
pre数组表示每一节点的前驱，最终已完成的并查集，每一个子图的所有点只有一个前驱（这也是其高效的原因），而初始化的并查集每一个点都是自己的前驱。
find函数负责寻找一个点的总前驱，比如：若有a->b->c->d这样的链状结构，a->b表示b是a的前驱，则在这个结构中，a的总前驱是d。
join函数负责将两个子图合并：给出任意两个点，判断他们是否分别属于两个子图，若是，则找到他们的总前驱，将一个变成另一个的子点。

示例代码;

int pre[MAXN], Rank[MAXN];
void init(int n)
{
    for(int i = 1; i <= n; i++)
        pre[i] = i;
}

int Find(int x)
{
    while(x != pre[x]) //寻找总前驱
        x = pre[x];
    return x;
}

void Join(int p1, int p2)
{
    int root1, root2;
    root1 = Find(p1);
    root2 = Find(p2);
    if(root1 != root2)
            pre[root2] = root1; //总前驱合并
}

并查集的最终效果是在查询结构上将森林中每一个图变成有且仅有一个根节点的树，这样，每一个图中所有点的前驱都是一样的，大大方便了查询判断与子图计数。

这里的一个优化（对“查”的优化）：在用Find函数寻找总前驱的过程中，若开始点位于一条长长的链上，则每次要从链上开始时，时间复杂度都是O(n)，效率比较低，但是如果我们在寻找的同时就把路径给压缩了（把这条链上的所有点的前驱都变成总前驱），下一次再碰上原属于这条链上的点时，寻找总前驱的过程会快很多。

示例代码：

int Find(int x)
{
    int r = x;
    while(r != pre[r]) //寻找总前驱
        r = pre[r];
    int i = x, j;
    while(i != r) //路径压缩
    {
        j = pre[i];
        pre[i] = r;
        i = j;
    }
    return r;
}

另一个优化（对“并”的优化）：在Join函数中，我们将一子图的根节点作为另一子图根节点的子点，而两树（子图）的高度，也就是秩，不一样，如果我们将秩大的树合并到了另一图之中，那么下次Find操作是就要多费几步，所以，我们用启发式的方式——比较两树的秩，将秩小的合并到秩大的之中。
不过这样我们需要建立一个rank数组并全部初始化为0。

示例代码：

void Join(int p1, int p2)
{
    int root1 = Find(p1);
    int root2 = Find(p2);
    if(root1 == root2) return;
    if(Rank[root1] < Rank[root2])
        pre[root1] = root2;
    else
    {
        if(Rank[root1] == Rank[root2])
            Rank[root1]++;
        pre[root2] = root1;    
    }
}

优化后的并查集示例代码：

void init(int n)
{
    for(int i = 1; i <= n; i++)
        pre[i] = i;
    memset(Rank, 0, sizeof(Rank));
}

int Find(int x)
{
    int r = x;
    while(r != pre[r]) //寻找总前驱
        r = pre[r];
    int i = x, j;
    while(i != r) //路径压缩
    {
        j = pre[i];
        pre[i] = r;
        i = j;
    }
    return r;
}

void Join(int p1, int p2)
{
    int root1 = Find(p1);
    int root2 = Find(p2);
    if(root1 == root2) return;
    if(Rank[root1] < Rank[root2])
        pre[root1] = root2;
    else
    {
        if(Rank[root1] == Rank[root2])
            Rank[root1]++;
        pre[root2] = root1;    
    }
}