直觉描述
依旧是动态联通性问题。换一种方法来处理。
Quick Union
与Quick Find一样，我们需要用到index。
针对节点，有[0, 1, ...9]作为index。
看看有哪些连接。
union(0, 1), union(1, 2), union(0, 5), union(1, 6),
union(2, 7), union(3, 4), union(3, 8), union(4, 9)
Quick Find使用的方式是，将联通的节点index改为一样的，所以更新后的index可以分为若干组，每个组内的index是相同的，每个组表示相互联通的节点组合。组员间的关系可以看作是平级的。
Quick Union使用的方式是，将联通的节点之间用父子关系串联起来，所以组员间的关系可以看作是树状的。
为了方便起见，我们将每次union(m, n)定义为，m为子，n为父。每次union，都是用m所代表的组的顶部，即父节点，连接到n节点所代表的组的父节点之下，这样，m所代表的这一组有了新的顶部节点，也就是n那一组的父节点。整个过程如下面的示例分步进行：
-
union(0, 1)
图2: union(0, 1)
index更新为：
[1，1，2，3，4，5，6，7，8，9]
-
union(1, 2)
图3: union(1, 2)
index更新为：
[1，2，2，3，4，5，6，7，8，9]
-
union(0, 5)
图4: union(0, 5)
index更新为：
[1，2，5，3，4，5，6，7，8，9]
-
union(1, 6)
图5: union(1, 6)
index更新为：
[1，2，5，3，4，6，6，7，8，9]
-
union(2, 7)
图6: union(2, 7)
index更新为：
[1，2，5，3，4，6，7，7，8，9]
-
union(3, 4)
图7: union(3, 4)
index更新为：
[1，2，5，4，4，6，7，7，8，9]
-
union(3, 8)
图8: union(3, 8)
index更新为：
[1，2，5，4，8，6，7，7，8，9]
-
union(4, 9)
图9: union(4, 9)
index更新为：
[1，2，5，4，8，6，7，7，9，9]
接下来就很好办，如果我们想知道两个节点是否联通，只需要查询它们所属的顶端父节点是否相同就可以了。比如:
connected(2, 3) = false
2的顶端父节点是7，3的顶端父节点是9，因此它们不联通；
复杂度
接下来我们看一下Quick Union的复杂度。这种方法做了如下的事情，和Quick Find一样：
- 给每一个节点初始index；
- 记录union；
- 查询联通性；
代码如下：
public class QuickUnionUF
{
private int[] id;
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);
}
public void union(int p, int q)
{
int i = root(p);
int j = root(q);
id[i] = j;
}
}
给每一个节点初始index；
用到的是constructor中的for循环，即：
for (int i = 0; i < N; i++)
id[i] = i;
很明显，这里访问了index对象N次。
记录union
如下，可以发现每一次union操作，都涉及到一个root方法
private int root(int i)
{
while (i != id[i]) i = id[i];
return i;
}
public void union(int p, int q)
{
int i = root(p);
int j = root(q);
id[i] = j;
}
首先看看root这个方法，它用来查询一个节点的父节点。那么这个查询需要的计算量，取决于节点所在组的树的深度。比如0节点所在的组，深度为6，那么前面的计算步骤union(0, 5)，需要的计算量如下：
// root(0)
// i = 0
while (0 != id[0] = 1) i = 1;
while (1 != id[1] = 2) i = 2;
while (2 = id[2] = 2)
return 2
// root(5)
// i = 5
while (5 = id[5] = 5)
return 5
// id[0] = 5
可以发现，计算量 = 3(当前tree深度) + 1(当前tree深度) + 1 = 5
考虑到树的深度有可能为N，比较Quick Find和Quick Union，那么出现了如下的复杂度局面。
那也就是说，考虑到N次的union操作，Quick Union也需要N2的计算复杂度，依旧是个不好的方法，Quick Find无法规模化的问题依旧存在。
