Cycle Detection In Undirected Graph
You have been given an undirected graph with 'N' vertices and 'M' edges. The vertices are labelled from 1 to 'N'.

Your task is to find if the graph contains a cycle or not.

A path that starts from a given vertex and ends at the same vertex traversing the edges only once is called a cycle.

Example :

In the below graph, there exists a cycle between vertex 1, 2 and 3.

Note:

1. There are no parallel edges between two vertices. 2. There are no self-loops(an edge connecting the vertex to itself) in the graph. 3. The graph can be disconnected.

For Example :

Input: N = 3 , Edges = [[1, 2], [2, 3], [1, 3]]. Output: Yes Explanation : There are a total of 3 vertices in the graph. There is an edge between vertex 1 and 2, vertex 2 and 3 and vertex 1 and 3. So, there exists a cycle in the graph.

Input Format:

The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow. The first line of each test case contains two single space-separated integers ‘N’ and ‘M’ representing the total number of vertices and edges, respectively. The next ‘M’ lines contain two single space-separated integers representing an edge of the graph.

Output Format:

For each test case, the only line of output will return “Yes” if there exists a cycle in the graph. Else print “No”.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints:

1

Question

Cycle Detection In Undirected Graph

You have been given an undirected graph with 'N' vertices and 'M' edges. The vertices are labelled from 1 to 'N'.

Your task is to find if the graph contains a cycle or not.

A path that starts from a given vertex and ends at the same vertex traversing the edges only once is called a cycle.

Example :

In the below graph, there exists a cycle between vertex 1, 2 and 3.

Example

Note:

1. There are no parallel edges between two vertices.

2. There are no self-loops(an edge connecting the vertex to itself) in the graph.

3. The graph can be disconnected.

For Example :

Input: N = 3 , Edges =  [[1, 2], [2, 3], [1, 3]].
Output: Yes

Explanation : There are a total of 3 vertices in the graph. There is an edge between vertex 1 and 2, vertex 2 and 3 and vertex 1 and 3. So, there exists a cycle in the graph.

Input Format:

The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains two single space-separated integers ‘N’ and ‘M’ representing the total number of vertices and edges, respectively.

The next ‘M’ lines contain two single space-separated integers representing an edge of the graph.

Output Format:

For each test case, the only line of output will return “Yes” if there exists a cycle in the graph. Else print “No”.

Note:

You are not required to print the expected output, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N <= 5000
0 <= M <= min(5000, (N * (N - 1)) / 2)
1 <= edges[i][0] <= N 
1 <= edges[i][1] <= N 

Time Limit: 1 sec

Accepted Answer

DFS Approach (Slow)

There is a cycle in the graph only if there is a back edge (back edge is an edge that connects a vertex to another vertex that is discovered before it's parent) present in the graph. To detect a back edge, we will keep track of vertices that have been already visited. If we reach a vertex that is already visited and is not the parent vertex of the current vertex, then there is a cycle in the graph.

Here is the complete algorithm:

We create a graph using the ‘EDGES’ array and initialise an array ‘VISITED’ to keep track of the visited vertices.
We iterate over all vertices of the graph and if the vertex is unvisited, we call the ‘IS_CYCLE’ function from that vertex. The ‘IS_CYCLE’ function works as follows:
1. Mark the current vertex true in the ‘VISITED’ array.
2. Find all the adjacent vertices of the current vertex.
  1. If an adjacent vertex is not visited
    1. Recursively call the ‘IS_CYCLE’ function for the adjacent vertex.
    2. If the recursive function returns true, then return true.
  2. Else if the adjacent vertex is already visited and is not the parent vertex of the current vertex.
    1. Return true.
3. Finally, return false.
If the ‘IS_CYLCE’ function returns true, then return “Yes”. Else return “No”.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of vertices in the graph.

We are using an extra array ‘VISITED’ to keep track of visited vertices and in the worst case, we have all the vertices of the graph in the recursion stack. Hence, the space complexity is O(N).

Time Complexity: OtherExplanation:

O(N + M), where ‘N’ is the number of vertices and ‘M’ is the number of edges in the graph.

In the worst case, we are visiting each vertex and edge of the graph only once. Hence, the time complexity is O(N + M).

Java (SE 1.8)

/*
    Time Complexity : O(N + M)
    Space Complexity : O(N)

    where 'N' is the number of vertices and
    'M' is the number of edges in the graph.
*/
    
import java.util.ArrayList;

public class Solution {
    public static boolean isCycle (int vertex, ArrayList< ArrayList < Integer > > graph, ArrayList < Boolean > visited, int parent)
	{
	    visited.set(vertex, true);

	    for (int adjVertex : graph.get(vertex))
	    {
	        if (visited.get(adjVertex) == false)
	        {
	            if (isCycle (adjVertex, graph, visited, vertex) == true)
	            {
	                return true;
	            }
	        }
	        else if (adjVertex != parent)
	        {
	            return true;
	        }
	    }

	    return false;
	}

    public static String cycleDetection(int[][] edges, int n, int m) {
        ArrayList< ArrayList < Integer > > graph = new ArrayList < ArrayList < Integer > > (n + 1);
        for(int i = 0; i <= n; i++){
        	graph.add(new ArrayList< Integer >());
        }

	    for (int i = 0; i < m; i++)
	    {
	        graph.get(edges[i][1]).add(edges[i][0]);
	        graph.get(edges[i][0]).add(edges[i][1]);
	    }

	    ArrayList < Boolean > visited = new ArrayList < Boolean > (n + 1);
	    for(int i = 0; i <= n; i++){
	    	visited.add(false);
	    }

	    for (int i = 1; i <= n; i++)
	    {
	        if (visited.get(i) == false)
	        {
	            if (isCycle (i, graph, visited, -1) == true)
	            {
	                return "Yes";
	            }
	        }
	    }

	    return "No";
    }
}

Python (3.5)

'''

    Time Complexity : O(N + M)

    Space Complexity : O(N)



    where N is the number of vertices and

    M is the number of edges in the graph.

'''





def isCycle(vertex, graph, visited, parent):



    visited[vertex] = True;



    for adjVertex in graph[vertex]:



        if(visited[adjVertex] == False):

            if (isCycle(adjVertex, graph, visited, vertex) == True):

                return True

           

        elif(adjVertex != parent):

            return True



    return False





def cycleDetection(edges, n, m):



    graph = [[] for i in range(n + 1)] 



    for i in range(m):    



        graph[edges[i][1]].append(edges[i][0])

        graph[edges[i][0]].append(edges[i][1])



    visited = [False] * (n + 1)



    for i in range(n + 1):

    

        if(visited[i] == False):

            if(isCycle(i, graph, visited, -1) == True):

                return "Yes"



    return "No"

Accepted Answer

BFS Approach (Slow)

In this approach, we will use breadth-first search algorithm to find the cycle in the undirected graph.

The approach is similar to the previous approach with some changes in the ‘IS_CYCLE’ function.

The ‘IS_CYCLE’ function will work as follows:

We push the current vertex in the queue.
We then run a while loop until the queue becomes empty.
1. Pop the front vertex from the queue.
2. We mark it true in the ‘VISITED’ array.
3. Find all the adjacent vertices of the current vertex.
  1. If the adjacent vertex is not visited:
    1. We mark it true in the ‘VISITED’ array and push it in the queue.
  2. Else if the adjacent vertex is visited and it is not the parent vertex of the current vertex.
    1. Return true
4. Finally, return false.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of vertices in the graph.

We are using an extra array to keep track of visited vertices and in the worst case, the size of the queue can go up to ‘N’. Hence, the space complexity is O(N).

Time Complexity: OtherExplanation:

O(N + M), where ‘N’ is the number of vertices and ‘M’ is the number of edges in the graph.

In the worst case, we are visiting each vertex and edge of the graph only once. Hence, the time complexity is O(N + M).

Java (SE 1.8)

/*
    Time Complexity : O(N + M)
    Space Complexity : O(N)

    where 'N' is the number of vertices and
    'M' is the number of edges in the graph.
*/

import java.util.*;

public class Solution {

  public static boolean isCycle(int vertex, ArrayList < ArrayList < Integer >> graph, boolean[] visited, int[] parent) {
    visited[vertex] = true;

    Queue < Integer > q = new LinkedList < Integer > ();

    q.add(vertex);

    while (q.size() != 0) {
      int remVertex = q.peek();
      q.remove();

      for (int adjVertex: graph.get(remVertex)) {
        if (visited[adjVertex] == false) {
          visited[adjVertex] = true;
          q.add(adjVertex);
          parent[adjVertex] = remVertex;
        } else if (visited[adjVertex] == true && parent[remVertex] != adjVertex) {
          return true;
        }
      }
    }

    return false;
  }

  public static String cycleDetection(int[][] edges, int n, int m) {
    ArrayList < ArrayList < Integer >> graph = new ArrayList < ArrayList < Integer >> (n + 1);
    for (int i = 0; i <= n; i++) {
      graph.add(new ArrayList < Integer > ());
    }

    for (int i = 0; i < m; i++) {
      graph.get(edges[i][1]).add(edges[i][0]);
      graph.get(edges[i][0]).add(edges[i][1]);
    }

    boolean[] visited = new boolean[n + 1];
    int[] parent = new int[n + 1];
    for (int i = 0; i <= n; i++) {
      parent[i] = -1;
    }

    for (int i = 1; i <= n; i++) {
      if (visited[i] == false) {
        if (isCycle(i, graph, visited, parent) == true) {
          return "Yes";
        }
      }
    }

    return "No";
  }

}

C++ (g++ 5.4)

/*
    Time Complexity : O(N + M)
    Space Complexity : O(N)

    where 'N' is the number of vertices and
    'M' is the number of edges in the graph.
*/

#include 

bool isCycle (int vertex, vector>& graph, vector& visited, vector& parent)
{
    visited[vertex] = true;

    queue q;

    q.push(vertex);

    while(q.size()!=0)
    {
        int remVertex = q.front();
        q.pop();

        for(int adjVertex : graph[remVertex])
        {
            if (visited[adjVertex] == false)
            {
                visited[adjVertex] = true;
                q.push(adjVertex);
                parent[adjVertex] = remVertex;
            }

            else if (visited[adjVertex] == true && parent[remVertex] != adjVertex)
            {
                return true;
            }
        }
    }
    return false;
}

string cycleDetection (vector>& edges, int n, int m)
{
    vector> graph(n + 1, vector());

    for (int i = 0; i < m; i++)
    {
        graph[edges[i][1]].push_back(edges[i][0]);
        graph[edges[i][0]].push_back(edges[i][1]);
    }

    vector visited(n + 1, false);
    vector parent(n + 1, -1);

    for (int i = 1; i <= n; i++)
    {
        if (visited[i] == false)
        {
            if (isCycle (i, graph, visited, parent) == true)
            {
                return "Yes";
            }
        }
    }

    return "No";
}

Python (3.5)

'''

    Time Complexity : O(N + M)

    Space Complexity : O(N)



    where N is the number of vertices and

    M is the number of edges in the graph.

'''





from collections import deque





def isCycle(vertex, graph, visited, parent):



    visited[vertex] = True



    q = deque()



    q.append(vertex)



    while len(q):

    

        remVertex = q[-1]

        q.pop()



        for adjVertex in graph[remVertex]:

        

            if(visited[adjVertex] == False):

                visited[adjVertex] = True

                q.append(adjVertex)

                parent[adjVertex] = remVertex



            elif(visited[adjVertex] == True and parent[remVertex] != adjVertex):

                return True

            

    return False

    



def cycleDetection(edges, n, m):



    graph = [[] for i in range(n + 1)] 



    for i in range(m):    



        graph[edges[i][1]].append(edges[i][0])

        graph[edges[i][0]].append(edges[i][1])



    visited = [False] * (n + 1)

    parent = [-1] * (n + 1)



    for i in range(n + 1):



        if(visited[i] == False):

            if(isCycle (i, graph, visited, parent) == True):

                return "Yes"



    return "No"

Accepted Answer

Union-find Algo

In this approach, we will use the union-find algorithm to find the cycle in the undirected graph.

The main idea behind using this algorithm is that if we have two subsets that are already connected through an edge and if they get connected by another edge then they form a cycle.

The union-find algorithm is an algorithm that performs two useful operations on a disjoint-set 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.

We will iterate through all edges and whenever we find two vertices with the same parent we return “Yes”.

Here is the algorithm:

We initialise two arrays ‘PARENT’ and ‘RANK’ to keep track of the parent and rank of the subsets. Here rank denotes the depth of the tree (subset).
Now we will iterate through all edges of the graph:
1. Find the parent of both vertices (say ‘PARENT1’ and ‘PARENT2’).
2. If ‘PARENT1’ == ‘PARENT2’
  1. Return “Yes”. Here, ‘PARENT1’ == ‘PARENT2’ represents that both subsets are initially connected and now we have another edge connecting them. Hence a cycle exists.
3. Else If ‘PARENT1’ != ‘PARENT2’
  1. Union both subsets into a single set. We are doing this because we have two subsets and an edge connecting them. Now both subsets combine and become a single subset.
Finally, return “No”.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of vertices in the graph.

We are using extra arrays ‘PARENT’ and ‘RANK’ each of size N to keep track of the parent and rank of the subsets. Hence, the space complexity is O(N).

Time Complexity: OtherExplanation:

O(M * logN), where ‘N’ is the number of vertices and ‘M’ is the number of edges in the graph.

In the worst case, we are calling ‘FIND_PARENT’ function M times and the maximum height of any subset can be log(N). Hence, the time complexity is O(M * logN).

C++ (g++ 5.4)

/*
    Time Complexity : O(M * log(N))
    Space Complexity : O(N)

    where 'N' is the number of vertices and
    'M' is the number of edges in the graph.
*/

int findparent (int i, vector& parent)
{
    if (i == parent[i])
    {
        return i;
    }
    return parent[i] = findparent (parent[i], parent);
}

string cycleDetection (vector>& edges, int n, int m)
{
    vector parent(n + 1, 0);
    vector rank(n + 1, 0);

    for (int i = 1; i <= n; i++)
    {
        rank[i] = 1;
        parent[i] = i;
    }

    for (vector& ar : edges)
    {
        int u = ar[0];
        int v = ar[1];

        int p1 = findparent (u, parent);
        int p2 = findparent (v, parent);

        if (p1 != p2)
        {
            if (rank[p1] < rank[p2])
            {
                parent[p1] = p2;
            }
            else if (rank[p1] > rank[p1])
            {
                parent[p2] = p1;
            }
            else
            {
                parent[p1] = p2;
                rank[p2]++;
            }
        }
        else
        {
            return "Yes";
        }
    }
    
    return "No";
}

Java (SE 1.8)

/*
    Time Complexity : O(M * log(N))
    Space Complexity : O(N)

    where 'N' is the number of vertices and
    'M' is the number of edges in the graph.
*/

public class Solution {
  public static int findparent(int i, int[] parent) {
    if (i == parent[i]) {
      return i;
    }
    return parent[i] = findparent(parent[i], parent);
  }

  public static String cycleDetection(int[][] edges, int n, int m) {

    int[] parent = new int[n + 1];
    int[] rank = new int[n + 1];

    for (int i = 1; i <= n; i++) {
      rank[i] = 1;
      parent[i] = i;
    }

    for (int[] ar: edges) {
      int u = ar[0];
      int v = ar[1];

      int p1 = findparent(u, parent);
      int p2 = findparent(v, parent);

      if (p1 != p2) {
        if (rank[p1] < rank[p2]) {
          parent[p1] = p2;
        } else if (rank[p1] > rank[p1]) {
          parent[p2] = p1;
        } else {
          parent[p1] = p2;
          rank[p2]++;
        }
      } else {
        return "Yes";
      }
    }

    return "No";
  }

}

Python (3.5)

'''

    Time Complexity : O(M * log(N))

    Space Complexity : O(N)



    where N is the number of vertices and

    M is the number of edges in the graph.

'''





def findparent(i, parent):



    if(i == parent[i]):

        return i

    

    parent[i] = findparent(parent[i], parent)



    return parent[i]





def cycleDetection(edges, n, m):



    parent = [0] * (n + 1)

    rank = [0] * (n + 1)



    for i in range(n + 1):



        rank[i] = 1

        parent[i] = i



    for ar in edges:



        u = ar[0]

        v = ar[1]



        p1 = findparent(u, parent)

        p2 = findparent(v, parent)



        if(p1 != p2):

            if(rank[p1] < rank[p2]):

                parent[p1] = p2

            elif(rank[p1] > rank[p1]):

                parent[p2] = p1

            else:

                parent[p1] = p2

                rank[p2] += 1

                

        else:

            return "Yes"



    return "No"

You have been given an undirected graph with 'N' vertices and 'M' edges. The vertices are labelled from 1 to 'N'.

Your task is to find if the graph contains a cycle or not.

A path that starts from a given vertex and ends at the same vertex traversing the edges only once is called a cycle.

Example :

Note:

For Example :

Input Format:

Output Format:

Note:

Constraints:

Top Lifesight Software Developer interview questions & answers

Popular interview questions of Software Developer