并查集

public class Main {
	public static void main(String[] args) {
		UFSTree[] u = new UFSTree[11];
		makeSet(u);
		union(u, 2, 4);
		union(u, 5, 7);
		union(u, 1, 3);
		union(u, 8, 9);
		union(u, 1, 2);
		union(u, 5, 6);
		union(u, 2, 3);
		System.out.println(isSimilar(u, 3, 4));
		System.out.println(isSimilar(u, 7, 10));
		System.out.println(isSimilar(u, 8, 9));
		
	}
	
	public static void  makeSet(UFSTree[] u) {
		
		for(int i = 1; i < u.length; i++) {
			u[i] = new UFSTree();
			u[i].data = i;
			u[i].rank = 1;
			u[i].parent = i;
		}
	}
	
	public static void union(UFSTree[] u, int x, int y) {
		int root_1 = findRoot(u, x);
		int root_2 = findRoot(u, y);
		if(root_1 != root_2) {
			if(u[root_1].rank > u[root_2].rank) {
				u[root_2].parent = root_1;
			} else {
				u[root_1].parent = root_2;
				if(u[root_1].rank == u[root_2].rank) {
					u[root_2].rank++;
				}
			}
		}
	}
	
	public static int findRoot(UFSTree[] u, int x) {
		if(x != u[x].parent) {
			return findRoot(u, u[x].parent);
		} else {
			return x;
		}
	}
	
	public static boolean isSimilar(UFSTree[] u, int x, int y) {
		if(findRoot(u, x) == findRoot(u, y)) {
			return true;
		} else {
			return false;
		}
	}
}

class UFSTree {
	public int data;
	public int rank;
	public int parent;
}

并查集

原文：http://blog.csdn.net/qhairen/article/details/47700315