union-find算法用于处理动态连通分量问题。跟不相交集合是相同的东东，可以参考
https://blog.csdn.net/jiangxt211/article/details/38476051
（1）处理连通分量的问题
1）找到元素所属的连通分量；
2）判断两元素是否属于同一连通分量；
3）合并两元素（连通分量）。
（2）API

（3）实现
使用id[]数组来放置元素所属连通分量的标志（id），通过三种不同的实现来展示对算法改进的过程。
1）quick-find
2）quick-union
id[]数组用父链接的形式表示一片树林。

3）weighted quick-union
使用sz[]数组放置各个根节点对应分量的大小（权重），将权重小的分量合并到权重大的分量。路径压缩的加权quick-union（weighted quick-union with path compresson）已是union-find的最优算法。

代码实现

package myutil;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

/* quick-find */	
public class MyUF {
	private int[] id;
	private int count;
	
	public MyUF(int n) {
		count = n;
		id = new int[n];
		for (int i = 0; i < n; i++) {
			id[i] = i;
		}
	}
	
	public int count() {
		return count;
	}
	
	public boolean connected(int p, int q) {
		return find(p) == find(q);
	}
	
	public int find(int p) {
		return  id[p];
	}
	
	public void union(int p, int q) {
		if (find(p) == find(q)) {
			return;
		}
		
		int pid = find(p);		
		int qid = find(q);
		for (int i = 0; i < id.length; i++) {
			if (id[i] == qid) {
				id[i] = pid;
			}
		}
		count--;
	}
	
	public static void main(String[] args) {
		//In in = new In("tinyUF.txt");
		In in = new In(args[0]);
		int n = in.readInt();
		MyUF uf = new MyUF(n);
		
		while (!in.isEmpty()) {
			int p = in.readInt();
			int q = in.readInt();
			if (uf.connected(p, q)) {
				continue;
			}
			uf.union(p, q);
			StdOut.println(p + " " + q);
		}
		StdOut.println(uf.count() + " components");
	}
}
复制

package myutil;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

/* quick-union */	
public class MyUFQU {
	private int[] id;
	private int count;
	
	public MyUFQU(int n) {
		count = n;
		id = new int[n];
		for (int i = 0; i < n; i++) {
			id[i] = i;
		}
	}
	
	public int count() {
		return count;
	}
	
	public boolean connected(int p, int q) {
		return find(p) == find(q);
	}
	
	public int find(int p) {
		while (p != id[p]) 
			p = id[p];
		
		return p;
	}
	
	public void union(int p, int q) {
		if (find(p) == find(q)) {
			return;
		}
		
		int proot = find(p);		
		int qroot = find(q);
		id[proot] = qroot;
		
		count--;
	}
	
	public static void main(String[] args) {
		//In in = new In("tinyUF.txt");
		In in = new In(args[0]);
		int n = in.readInt();
		MyUFQU uf = new MyUFQU(n);
		
		while (!in.isEmpty()) {
			int p = in.readInt();
			int q = in.readInt();
			if (uf.connected(p, q)) {
				continue;
			}
			uf.union(p, q);
			StdOut.println(p + " " + q);
		}
		StdOut.println(uf.count() + " components");
	}
}

复制

package myutil;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

/* weighted quick-union */
public class MyUFWQU {
	private int[] id; // parent
	private int[] sz; // size
	private int count;
	
	public MyUFWQU(int n) {
		count = n;
		id = new int[n];
		sz = new int[n];
		for (int i = 0; i < n; i++) {
			id[i] = i;
			sz[i] = 1;
		}
	}
	
	public int count() {
		return count;
	}
	
	public boolean connected(int p, int q) {
		return find(p) == find(q);
	}
	
	public int find(int p) {
//		while (p != id[p]) 
//			p = id[p];
//		return p;
		
        /* 路径压缩（path compression） */
		if (p != id[p]) {
			id[p] = find(id[p]);
		}
		return id[p];
	}
	
	public void union(int p, int q) {
		if (find(p) == find(q)) {
			return;
		}
		
		int proot = find(p);		
		int qroot = find(q);
		if (sz[proot] < sz[qroot]) {	
			id[proot] = qroot;
			sz[qroot] += sz[proot];
		} else {
			id[qroot] = proot;
			sz[proot] += sz[qroot];		
		}
		
		count--;
	}
	
	public static void main(String[] args) {
		//In in = new In("tinyUF.txt");
		In in = new In(args[0]);
		int n = in.readInt();
		MyUFWQU uf = new MyUFWQU(n);
		
		while (!in.isEmpty()) {
			int p = in.readInt();
			int q = in.readInt();
			if (uf.connected(p, q)) {
				continue;
			}
			uf.union(p, q);
			StdOut.println(p + " " + q);
		}
		StdOut.println(uf.count() + " components");
	}
}
复制

总结
好的算法会因为能够解决实际问题而变得更为重要。
1）完整而详细地定义问题，找出解决问题所必需的基本抽象操作并定义一份基本的API；
2）简洁地实现一种初级算法，给出一种精心组织的开发用例并使用实际数据作为输入；
3）逐步改进实现，通过经验性分析或（和）数学分析验证改进后的结果。
最近想学些图相关的算法，之前看《算法导论》，看的很吃力，就整了本简单些的《算法4》，发现有些前导知识需要补下。都是经典的好书，希望能坚持，希望有收获。