解决问题
给一系列对点0~N-1的连接，判断某两个点p与q是否相连。
private int[] id; // 判断p和q是否属于同一个连通分量 public boolean connected(int p, int q) // 连接两个点 public void union(int p, int q)
Quick-find
connected(p, q):判断p 和 q 的id值是否相同
union(p, q): 将与p 的id 相同的所有点都改为q的id
缺点：union太慢，需要遍历id数组
Quick-union
connected(p, q):判断p 和 q 的根的id值是否相同
union(p, q): 将与p 的根的 id 改为q的根的 id
本质上是将并查集之间的关系看做一棵树
缺点：最坏情况下仍然需要遍历数组
Weighted Quick-union
connected(p, q):判断p 和 q 的根的id值是否相同
union(p, q): 判断p和q所在的树哪个大（包含的节点多），将较小的树根的 id 改为较大的树根的 id
某个节点高度增加1，当且仅当它在一颗小树T1上且被union并入大树T2中，生成的树节点数大于T1的两倍，所以某个节点的高度最多只能是lg(N)
Weighted Quick-union with Path Compression
connected(p, q):判断p 和 q 的根的id值是否相同
union(p, q): 判断p和q所在的树哪个大（包含的节点多），将较小的节点到较小的树根这条路径上所有节点的 id 改为较大的树根的 id
总结
四种方法复杂度如下，其中lg* 表示需要取对数多少次才能将N的值变为≤1，WQUPC复杂度是由论文中所得，lg*可以视为常数复杂度。
| algorithm | 初始化 | union | connected |
| quick find | N | N | 1 |
| quick union | N | N | N |
| weighted quick union | N | lg N | lg N |
| weighted quick union with path compression | N | lg* N | lg* N |
实现
public class UF {
private int[] parent; // parent[i] = parent of i
private byte[] rank; // rank[i] = rank of subtree rooted at i (never more than 31) 记录的是树的高度
private int count; // number of components
/**
* Initializes an empty union-find data structure with <tt>N</tt> sites
* <tt>0</tt> through <tt>N-1</tt>. Each site is initially in its own
* component.
*
* @param N the number of sites
* @throws IllegalArgumentException if <tt>N < 0</tt>
*/
public UF(int N) {
if (N < 0) throw new IllegalArgumentException();
count = N;
parent = new int[N];
rank = new byte[N];
for (int i = 0; i < N; i++) {
parent[i] = i;
rank[i] = 0;
}
}
/**
* Returns the component identifier for the component containing site <tt>p</tt>.
*
* @param p the integer representing one site
* @return the component identifier for the component containing site <tt>p</tt>
* @throws IndexOutOfBoundsException unless <tt>0 ≤ p < N</tt>
*/
public int find(int p) {
validate(p);
while (p != parent[p]) {
parent[p] = parent[parent[p]]; // path compression by halving 【完成路径压缩】
p = parent[p];
}
return p;
}
/**
* Returns the number of components.
*
* @return the number of components (between <tt>1</tt> and <tt>N</tt>)
*/
public int count() {
return count;
}
/**
* Returns true if the the two sites are in the same component.
*
* @param p the integer representing one site
* @param q the integer representing the other site
* @return <tt>true</tt> if the two sites <tt>p</tt> and <tt>q</tt> are in the same component;
* <tt>false</tt> otherwise
* @throws IndexOutOfBoundsException unless
* both <tt>0 ≤ p < N</tt> and <tt>0 ≤ q < N</tt>
*/
public boolean connected(int p, int q) {
return find(p) == find(q);
}
/**
* Merges the component containing site <tt>p</tt> with the
* the component containing site <tt>q</tt>.
*
* @param p the integer representing one site
* @param q the integer representing the other site
* @throws IndexOutOfBoundsException unless
* both <tt>0 ≤ p < N</tt> and <tt>0 ≤ q < N</tt>
*/
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
// make root of smaller rank point to root of larger rank
if (rank[rootP] < rank[rootQ]) parent[rootP] = rootQ;
else if (rank[rootP] > rank[rootQ]) parent[rootQ] = rootP;
else {
parent[rootQ] = rootP;
rank[rootP]++; //【只有此处才增加联通分量的rank】
}
count--;
}
// validate that p is a valid index
private void validate(int p) {
int N = parent.length;
if (p < 0 || p >= N) {
throw new IndexOutOfBoundsException("index " + p + " is not between 0 and " + (N-1));
}
}
/**
* Reads in a an integer <tt>N</tt> and a sequence of pairs of integers
* (between <tt>0</tt> and <tt>N-1</tt>) from standard input, where each integer
* in the pair represents some site;
* if the sites are in different components, merge the two components
* and print the pair to standard output.
*/
public static void main(String[] args) {
int N = StdIn.readInt();
UF uf = new UF(N);
while (!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();
if (uf.connected(p, q)) continue;
uf.union(p, q);
StdOut.println(p + " " + q);
}
StdOut.println(uf.count() + " components");
}
}