## Cycle in undirected graph using disjoint set

In post disjoint set data structure, we discussed the basics of disjoint sets. One of the applications of that data structure is to find if there is a cycle in a directed graph.

In graph theory, a cycle is a path of edges and vertices wherein a vertex is reachable from itself.

For example, in the graph shown below, there is a cycle formed by path : 1->2->4->6->1.

Disjoint-set data structure has two operations: `union` and `find`. Union operation merges two sets into one, whereas find operation finds the representative of the set a given element belongs to.

### Using disjoint set to detect a cycle in directed grah

How can use the data structure and operations on it to find if a given directed graph contains a cycle or not?

We use an array A, which will store the parent of each node. Initialize the array with the element itself, that means to start with every node is the parent of itself.

Now, process each `edge(u,v)`

in the graph and for each edge to the following: Get the root of both vertices u and v of the edge. If the roots of both nodes are different, update the root of u with the root of v. If roots are same, that means they belong to the same set and hence this edge creates a cycle.

How can we find the root of a vertex? As we know A[i] represents the parent of i; we start with i= u and go up till we find A[i] = i. It means there is no node parent of i and hence i is the root of the tree to which u belongs.

Let’s take an example and see how does it work. Below is the given directed graph and we have to if there is a cycle in it or not?

To start with, we initialize array A with the elements themselves.

Now, we process each node of the graph one by one. First is `edge(1,2)`

. The root of `node(1)`

is 1 and the root of `node(2)`

is 2. Since the roots of two vertices are different, we update the *parent of the root of 2* which is `A[2]` to the *root of 1 * which is `1`.

Next, we process `edge(2,3)`

, here root of the `node(2)`

is 1, whereas the root `node(3)`

is 3. Again they differ, hence update A[root of 3] with root 2, i.e A[3] = 1;

Now, process `edge(2,4)`

, it will end up with A[4] = 1, can you deduce why? And similarly `edge(4,6)`

will also lead to update A[6] = 1.

Now, we process the `edge(6,1)`

. Here, root of `node(6)`

is 1 and also the root of `node(1)`

is 1. Both the nodes have same root, that means there is a cycle in the directed graph.

#### To detect a cycle in direct graph : Implementation

package com.company.Graphs; import java.util.*; /** * Created by sangar on 21.12.18. */ public class AdjacencyList { private Map<Integer, ArrayList<Integer>> G; private boolean isDirected; private int count; public AdjacencyList(boolean isDirected){ this.G = new HashMap<>(); this.isDirected = isDirected; } public void addEdge(int start, int dest){ if(this.G.containsKey(start)){ this.G.get(start).add(dest); }else{ this.G.put(start, new ArrayList<>(Arrays.asList(dest))); } if(!this.G.containsKey(dest)) { this.G.put(dest, new ArrayList<>()); } //In case graph is undirected if(!this.isDirected) { this.G.get(dest).add(start); } } public boolean isEdge(int start, int dest){ if(this.G.containsKey(start)){ return this.G.get(start).contains(dest); } return false; } public boolean isCycleWithDisjointSet() { int[] parent = new int[this.G.size() + 1]; for (int u = 1; u < this.G.size() + 1; u++) { //Process edge from each node. //Find root of u int i, j; //Worst complexity is O(V) for(i=u; i != parent[i]; i = parent[i]); /*This loop will run for O(E) times for all the vertices combined. */ for(int v: this.G.get(u)){ for(j=v; j != parent[j]; j = parent[j]); if(i == j){ System.out.println("Cycle detected at ("+ u + "," + v + ")"); return true; } parent[i] = j; } } return false; } }

Test cases

package test.Graphs; import com.company.Graphs.AdjacencyList; import org.junit.jupiter.api.Test; import static org.junit.jupiter.api.Assertions.assertEquals; /** * Created by sangar on 21.12.18. */ public class AdjacencyListTest { @Test public void detectCycleInDirectedGraphTest() { AdjacencyList tester = new AdjacencyList(false); tester.addEdge(1,5); tester.addEdge(3,4); tester.addEdge(2,4); tester.addEdge(1,3); tester.addEdge(3,5); tester.addEdge(5,2); assertEquals(true, tester.isEdge(3,4)); assertEquals(false, tester.isEdge(1,4)); assertEquals(true, tester.isCycleWithDisjointSet()); } }

Complexity of this algorithm is `O(EV)`

where `E` is number of edges and `V` is vertices, where as union function in disjoint set can take linear time w.r.t to vertices and it may run for number of edge times.

Please share if there is something wrong or missing. If you are preparing for interview and interested in personalized coaching, please signup for free demo class.