-
逻辑：
将点连成如图所示的树状图，如果两个点具备一个相同的根，那么说明两点之间相连。
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;
}
}
