Quick Union

• 逻辑：
  将点连成如图所示的树状图，如果两个点具备一个相同的根，那么说明两点之间相连。

  
  
  image.png

image.png

……

image.png

• Java:

public class QuickUnionUF
{
    private int[] id;
    // 初始化array
    public QuickUnionUF(int N)
    {
        id = new int[N];
        for (int i = 0; i < N; i++) id[i] = i;
    }
    // 组成树，并返回根
    private int root(int i) 
    {
        while (i != id[i]) i = id[i];
        return i;
    }
    // 检测两点是否连接
    public boolean connected(int p, int q)
    {
        return root(p) == root(q);
    }
    // 形成union
    public void union(int p, int q)
    {
        int i = root(p);
        int j = root(q);
        id[i] = j;
    }
}

Java的代码很好理解，下面是C++的代码，就略显凌乱了：

#include <iostream>
using namespace std;
const int N = 10;
// 
int main()
{
    int i,j,p,q,id[N];
    // 初始化array，相当于Java中的QuickUnionUF方法
    for(i = 0; i < N; i++) {
        id[i] = i;
    }
    // 输入两点坐标，如果两点之前未连接，则返回两点坐标
    while (cin >> p >> q){
        // 功能类似Java代码中的root方法，i最后等于根的坐标
        for (i = p; i != id[i]; i = id[i]);
        // 功能类似Java代码中的root方法，j最后等于根的坐标
        for (j = q; j != id[j]; j = id[j]) ;
        // 此时i和j都为根的坐标，比较根坐标；根相同，则两点相连，跳过之后的代码，开始新的循环
        if (i == j) continue; 
        // 根不同，则连接两点，创建新的union
        id[i] = j; 
        // 返回没有相连的两点的坐标
        cout << " " << p << " " << q << endl;
    } 
}