1.5：union-find算法（临渊羡鱼不如退而结网啊）

原书目录

动态连通性

我们输入一对一对的整数，每个整数表示一台计算机，整数对表示这两台计算机可以通信，当我们在已有一些整数对的情况下，需要去判断，新进来一个整数对p,q，是否需要在它俩之间架设新的连接才能通信，还是说我们可以在已有的连接上使二者可以通信

我们会一步步地去优化问题的解决方案，你可以在看每个解决方案之前想一想

定义一份API

上述表格你可以对于连通分量有疑问，是这样的，我们怎么表示两台电脑已经可以通信了呢？把它们放到同一个连通分量中，一开始我们有N个连通分量，将两个分量归并的每次union()操作都会使连通分量总数减一

class UF{
private:
    vector<int> id;
    int count;

public:
    UF(int N) //构造函数
    {
        count = N;
        for (int i = 0; i < N; ++i)
        {
            id.push_back(i);
            sz.push_back(1);
        }        
    }

    int Count(){ return count; }

    bool connected(int p, int q){ return find(p) == find(q); }

    int find(int p);

    void Union(int p, int q)
};

这份代码是我们队UF的实现，它维护一个整型数组id，用来表示每台电脑的所在的连通分量，count表示连通分量的数量，最开始为N，接下来就是最主要的工作，find函数和union函数的实现

方案一

quick-find算法

int find(int p){
    return id[p];
}
void union(int p, int q){
    int pID = find(p);
    int qID = find(q);
    //如果p和q已经在同一个连通分量中，则不需要做任何事
    if(pID!=qID){
        //把p的连通分量修改为q的，反过来也行
        for(int i=0; i<id.size(); ++i){
            if(id[i] == pID) id[i] = qID;
        }
        --count;
    }
}

这个方案确实能解决我们的问题，而且它的find操作超级快，但是它有一个致命缺点——union函数，因为对于每一对输入，union都需要去扫描整个id数组，如果我们处理的问题是上百万台电脑，你每处理一对，就要扫描上百万，这显然太慢了

方案二

quick-union算法
我们的重点就是要提高union函数的速度，我们还是采用id这个数组，不过它的含义要变一下，注意下面这句话：
每台电脑所对应的id元素都是同一个分量中的某台电脑的名称，我们将这种关系称为链接
当且仅当分别由两台电脑开始的这个过程到达同一台“根电脑”时，它们存在于同一个连通分量

可能到现在还不是很好理解，没关系，看代码我慢慢解释：

//首先明确一下p和id[p]的关系，id[p]是p的父节点
//再明确id[p]=p什么意思，父节点是自己，那就是根节点
//所以下面的find函数我把它称为找老子算法
int find(int p){
    while(p != id[p]) p = id[p];
    return p;
}

再看union算法：

//找到p和q的根节点，将一个根节点链接到另一个即可
void Union(int p, int q)
    {
        int proot = find(p);
        int qroot = find(q);
        if (proot == qroot){return;}
        else
        {
            id[proot] = qroot;
        }
    }

为什么这个算法要比上一个的union快呢，因为它在连通分量时，充分利用了前面连通分量的***果实，把之前的连通分量用一棵树表示，然后再连通到新的分量时，只需要把根节点链接上去就好了

应该说这个算法已经很优秀了，但是它还是会有些小小的不足，如果输入的整数对很坏，导致我们最后形成的树变成了一条单链表，那可想而知我们的复杂度也会很大，当然，很少见

方案三

加权quick-union算法
幸好，我们只需要简单的修改quick-union算法，牺牲一点点空间，就可以保证这种糟糕的情况不再出现：
我们在之前的union算法中，一直是随意地将一棵树链接到另一棵，我们现在要维护一个记录树大小的数组，并且在union时，总是把小树连到大树上：

class UF
{
private:
    vector<int> id;
    vector<int> sz;
    int count;

public:
    UF(int N) //构造函数
    {
        count = N;
        for (int i = 0; i < N; ++i)
        {
            id.push_back(i);
            sz.push_back(1);
        }        
    }

    int Count(){ return count; }

    bool connected(int p, int q){ return find(p) == find(q); }

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

    void Union(int p, int q)
    {
        int i = find(p);
        int j = find(q);
        if (i == j){return;}
        else
        {
            if (sz[i] < sz[j]){ id[i] = j; sz[j] += sz[i]; }
            else { id[j] = i; sz[i] += sz[j]; }
        }
    }
};