解决问题
给一系列对点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 N sites * 0 through N-1. Each site is initially in its own * component. * * @param N the number of sites * @throws IllegalArgumentException if N < 0 */ 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 p. * * @param p the integer representing one site * @return the component identifier for the component containing site p * @throws IndexOutOfBoundsException unless 0 ≤ p < N */ 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 1 and N) */ 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 true if the two sites p and q are in the same component; * false otherwise * @throws IndexOutOfBoundsException unless * both 0 ≤ p < N and 0 ≤ q < N */ public boolean connected(int p, int q) { return find(p) == find(q); } /** * Merges the component containing site p with the * the component containing site q. * * @param p the integer representing one site * @param q the integer representing the other site * @throws IndexOutOfBoundsException unless * both 0 ≤ p < N and 0 ≤ q < N */ 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 N and a sequence of pairs of integers * (between 0 and N-1) 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"); }}