Union Find

Union Find by rank and path compression
Time complexity of union and find operations is O(log n) by using rank and path compression.

// Detect cycle in an undirected graph.

public class Main {
	
	public static class Edge {
		int v1, v2;
		
		public Edge(int v1, int v2) {
			this.v1 = v1;
			this.v2 = v2;
		}
	}
	
	public static class Graph {
		int v;
		Edge[] e;
		
		public Graph(int v, int edgeCount) {
			this.v = v;
			e = new Edge[edgeCount];
		}
	}	
	
	public static class UnionFind {
		int rank;
		int parent;
		
		public UnionFind(int rank, int parent){
			this.rank = rank;
			this.parent = parent;
		}
	}
	
	public static int find(int x, UnionFind[] uf) {
		if(uf[x].parent != x) {
			uf[x].parent = find(uf[x].parent, uf);
		}
		
		return uf[x].parent;
	}
	
	public static void union(int v1, int v2, UnionFind[] uf) {
		int p1 = find(v1, uf);
		int p2 = find(v2, uf);
		
	    if(uf[p1].rank < uf[p2].rank){ 	    	uf[p1].parent = p2; 	    } else if(uf[p1].rank > uf[p2].rank){
	    	uf[p2].parent = p1;
	    } else {
	    	uf[p1].parent = p2;
	    	uf[p2].rank++;	    	
	    }
	}
	
	public static int checkCycle(Graph g){
		
		UnionFind[] uf = new UnionFind[g.v];
		
		for(int i=0; i<g.v; i++) {
			uf[i] = new UnionFind(0,i);
		}
		
		for(int i=0; i<g.e.length; i++) {
			int p1 = find(g.e[i].v1, uf);
			int p2 = find(g.e[i].v2, uf);
			
			if(p1 == p2){
				return 1;
			}			
			union(g.e[i].v1, g.e[i].v2, uf);			
		}			
		return 0;
	}
	
	public static void main(String[] arsg){
		Main m = new Main();
		Graph g = new Graph(5, 4);
		
		g.e[0] = new Edge(0,1);
		g.e[1] = new Edge(1,2);
		g.e[2] = new Edge(2,3);
		g.e[3] = new Edge(3,0);
		
		if(checkCycle(g) == 1){
			System.out.println("Graph contains cycle");
		} else {
			System.out.println("Graph does not contains cycle");
		}		
	}
}

In naive implementation the time complexity of union and find operations in O(n)

// Naive implementation of find
int find(int parent[], int i)
{
    if (parent[i] == -1)
        return i;
    return find(parent, parent[i]);
}
  
// Naive implementation of union()
void Union(int parent[], int x, int y)
{
    int xset = find(parent, x);
    int yset = find(parent, y);
    parent[xset] = yset;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s