Disjoint Set (Or Union-Find)

A disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:

Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.

Union: Join two subsets into a single subset.

1. Use Array Data Structure

input graph shown as below:

     0
    |  \
    |   \
    1-----2

output should be: find a cycle

public static void main(String[] args) {
	// TODO Auto-generated method stub
	int[][] edges = {{0, 1}, {1, 2}};
	int[] parent = new int[3];
	for(int i = 0; i < parent.length; i++)
		parent[i] = i;
	for(int i = 0; i < edges.length; i++){
		int lParent = find(parent, edges[i][0]);
		int rParent = find(parent, edges[i][1]);
		if(lParent == rParent){
			System.out.println("find a cycle");
			return;
		}
		union(parent, lParent, rParent);
	}
	System.out.println("no cycle");
}

private static int find(int[] parent, int i){
	if(parent[i] == i)
		return i;
	return find(parent, parent[i]);
}

private static void union(int parent[], int x, int y){
	int xSet = find(parent, x);
	int ySet = find(parent, y);
	parent[xSet] = ySet;
}

See Problem #547. Friend Circles, Problem #130. Surrounded Regions. Problem #261. Graph Valid Tree