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;
}