Problem

Submissions

Hints & solutions

Discuss

Cycle Detection In Undirected Graph

Moderate

0/80

Contributed by

203 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

Sample output 1:

No

Explanation of Sample output 1:

 The above graph can be represented as

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

Sample Input 2:

Sample output 2:

No
Yes

Hint 1

Hint 2

Hint 3

Try to use DFS to solve the problem.

Approaches (3)

Approach 1

Approach 2

Approach 3

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”.

Time Complexity

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).

Space Complexity

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).

(100% EXP penalty)

Cycle Detection In Undirected Graph

Rishabh Shairy

Interview problems

BFS Java Solution

public class Solution {
    static class Node {
        int currNode;
        int parentNode;

        public Node(int currNode, int parentNode) {
            this.currNode = currNode;
            this.parentNode = parentNode;
        }
    }


    public static String cycleDetection(int[][] edges, int n, int m) {
        // Write your code here.
        List<List<Integer>> adjacencyList = generateAdjList(edges, n);

        boolean[] visited = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                if (checkCycleBFS(i, visited, adjacencyList)) {
                    return "Yes";
                }
            }
        }
        return "No";
    }

    private static boolean checkCycleBFS(int i, boolean[] visited, List<List<Integer>> adjacencyList) {
        Queue<Node> nodeQueue = new LinkedList<>();
        nodeQueue.offer(new Node(i, -1));
        visited[i] = true;

        while (!nodeQueue.isEmpty()) {
            int currNode = nodeQueue.peek().currNode;
            int parentNode = nodeQueue.peek().parentNode;
            nodeQueue.poll();

            for (Integer adjNode : adjacencyList.get(currNode)) {
                if (!visited[adjNode]) {
                    nodeQueue.offer(new Node(adjNode, currNode));
                    visited[adjNode] = true;
                } else if (adjNode != parentNode) {
                    return true;
                }
            }
        }
        return false;
    }

    private static List<List<Integer>> generateAdjList(int[][] edges, int n) {
        List<List<Integer>> graph = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

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

24 views

0 replies

0 upvotes

VATSAL SINGH

Interview problems

Dumb Framing

Apparantly the question provider was unaware of the presence of bool datatype.

7 views

0 replies

0 upvotes

Nisha Anand

Interview problems

bfs implementation

#include<bits/stdc++.h>
using namespace std;


bool isCycleBfs(unordered_map<int, list<int>> &adj, unordered_map<int, bool> &vis, int node){
    
    unordered_map<int, int> parent;
    parent[node] = -1;
    queue<int> q;
    q.push(node);
    vis[node] = 1;


    while(!q.empty()){
        int frontNode = q.front();
        q.pop();


        for(auto i: adj[frontNode]){


            
            
            if(vis[i] && i != parent[frontNode]){
                    return true;
            }
            else if(!vis[i]){
            q.push(i);
            vis[i] = 1;
            parent[i] = frontNode;
            }
        }
    }


return false;


}
string cycleDetection (vector<vector<int>>& edges, int n, int m)
{


    unordered_map<int, bool> vis;
    unordered_map<int, list<int>> adj;
    //adj list for the graph
    for(int i=0; i<m; i++){
        int u = edges[i][0];
        int v = edges[i][1];


        adj[u].push_back(v);
        adj[v].push_back(u);
    }


    for(int i=0; i<n; i++){
        if(!vis[i]){
            bool ans = isCycleBfs(adj, vis, i);
            if(ans==1){
                return "Yes";
            }
        }
    }
return "No";




}

147 views

0 replies

0 upvotes

Harshita Verma

Interview problems

Easy BFS Implementation in C++|| Most Intuitive || without Maps

Do Upvote if you found it helpful! Happy Coding.

#include<bits/stdc++.h>
string cycleDetection (vector<vector<int>>& edges, int n, int m)
{
 vector<vector<int>> adj(n + 1);
    vector<bool> visited(n + 1, false);
    
    for (const auto& edge : edges) {
        adj[edge[0]].push_back(edge[1]);
        adj[edge[1]].push_back(edge[0]);
    }
    
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            queue<pair<int, int>> q;
            visited[i] = true;
            q.push({i, -1});
            
            while (!q.empty()) {
                int node = q.front().first;
                int parent = q.front().second;
                q.pop();
                
                for (int neighbor : adj[node]) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        q.push({neighbor, node});
                    } else if (neighbor != parent) {
                        return "Yes"; // Cycle detected
                    }
                }
            }
        }
    }
    
    return "No";
}

97 views

0 replies

0 upvotes

Harshit Patil

Interview problems

Using BFS and DFS Approach

#include<bits/stdc++.h>

Using BFS Approach

bool Bfs(int vertex, vector<int> adj[], vector<int> &visited){

queue<pair<int, int>> q;

q.push({vertex, -1});

while(!q.empty()){

int node = q.front().first;

int parent = q.front().second;

q.pop();

for(auto it : adj[node]){

if(parent == it){

continue;

}

if(visited[it]){

return true;

}

visited[it] = 1;

q.push({it, node});

}

return false;

}

string cycleDetection (vector<vector<int>>& edges, int n, int m)

{

vector<int> adj[n+1];

for(int i=0; i<m; i++){

int u = edges[i][0];

int v = edges[i][1];

adj[u].push_back(v);

adj[v].push_back(u);

}

vector<int> visited(n+1, 0);

for(int i=0; i<visited.size(); i++){

if(!visited[i]){

if(Bfs(i, adj, visited)){

return "Yes";

}

return "No";

}

// Using DFS Approach

bool Dfs(int node, int parent, vector<int> adj[], vector<int> &visited){

visited[node] = 1;

for(auto it : adj[node]){

if(parent == it){

continue;

}

if(visited[it]){

return true;

}

if(Dfs(it, node, adj, visited)){

return true;

}

return false;

}

string cycleDetection (vector<vector<int>>& edges, int n, int m)

{

vector<int> adj[n+1];

for(int i=0; i<m; i++){

int u = edges[i][0];

int v = edges[i][1];

adj[u].push_back(v);

adj[v].push_back(u);

}

vector<int> visited(n+1, 0);

for(int i=0; i<visited.size(); i++){

if(!visited[i]){

if(Dfs(i, -1, adj, visited)){

return "Yes";

}

return "No";

}

204 views

0 replies

1 upvote

Deependra Parmar

Interview problems

Best C++ Solution using DFS

bool isCyclicUsingDFS(unordered_map<int,list<int>> &adj, unordered_map<int,bool> &visited, int src, int parentNode){
    visited[src] = 1;


    for(auto neighbour: adj[src]){
        if(!visited[neighbour]){
            bool cycleDetected = isCyclicUsingDFS(adj, visited, neighbour, src);


            if(cycleDetected)
                return true;
        }
        else if(neighbour != parentNode){
            return true;
        }
    }


    return false;
}
string cycleDetection (vector<vector<int>>& edges, int n, int m)
{
    unordered_map<int,list<int>> adj;
    unordered_map<int,bool> visited;


    for(int i=0; i<edges.size(); i++){
        int u = edges[i][0];
        int v = edges[i][1];


        adj[u].push_back(v);
        adj[v].push_back(u);
    }


    // for all disconnected components
    for(int i=0; i<n; i++){
        if(!visited[i]){
            bool ans = isCyclicUsingDFS(adj, visited, i, -1);


            if(ans == 1)
                return "Yes";
        }
    }


    return "No";
}

101 views

0 replies

0 upvotes

Deependra Parmar

Interview problems

Best C++ Solution using BFS

#include<unordered_map>
#include<list>
#include<queue>
#include<bits/stdc++.h>


bool isCyclicUsingBFS(unordered_map<int,list<int>> &adj, unordered_map<int,bool> &visited, int src){
    unordered_map<int,int> parent;
    queue<int> q;


    parent[src] = -1;
    visited[src] = 1;


    q.push(src);


    while(!q.empty()){
        int frontNode = q.front();
        q.pop();


        for(auto i: adj[frontNode]){
            if(visited[i] == true && i != parent[frontNode])
                return true;
            
            else if(!visited[i]){
                q.push(i);
                visited[i] = 1; 
                parent[i] = frontNode;
            }
        }
    }


    return false;
}
string cycleDetection (vector<vector<int>>& edges, int n, int m)
{
    unordered_map<int,list<int>> adj;
    unordered_map<int,bool> visited;


    for(int i=0; i<edges.size(); i++){
        int u = edges[i][0];
        int v = edges[i][1];


        adj[u].push_back(v);
        adj[v].push_back(u);
    }


    // for all disconnected components
    for(int i=0; i<n; i++){
        if(!visited[i]){
            bool ans = isCyclicUsingBFS(adj, visited, i);


            if(ans == 1)
                return "Yes";
        }
    }


    return "No";
}

81 views

0 replies

0 upvotes

Survi Sharma

Interview problems

Python (3.5) solution

def cycleDetection(edges, n, m):

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

for u, v in edges:

graph[u].append(v)

graph[v].append(u)

def has_cycle(current_vertex, parent, visited):

visited[current_vertex] = True

for neighbor in graph[current_vertex]:

if not visited[neighbor]:

if has_cycle(neighbor, current_vertex, visited):

return True

elif neighbor != parent:

return True

return False

visited = [False] * (n + 1)

for vertex in range(1, n + 1):

if not visited[vertex]:

if has_cycle(vertex, -1, visited):

return "Yes" # Cycle is present

return "No" # No cycle found

31 views

0 replies

0 upvotes

Abhishek Sachdeva

Interview problems

easy c++ code || cycle detection in undirected graph || upvote

#include <bits/stdc++.h>

bool solve(vector<vector<int>>&adj,vector<bool>&visited,int pointer,int vertices)

{

visited[pointer]=true;

vector<int>parent(vertices+1,-1);

queue<int>q;

q.push(pointer);

while(!q.empty())

{

int top = q.front();

q.pop();

for(auto child:adj[top])

{

if(parent[top]!=child && visited[child])

{

return true;

}

else if(!visited[child])

{

visited[child]=true;

q.push(child);

parent[child] = top;

}

return false;

}

string cycleDetection (vector<vector<int>>& edges, int n, int m)

{

// Write your code here.

vector<vector<int>>adj(n+1);

for(int i=0; i<m; ++i)

{

int x = edges[i][0];

int y = edges[i][1];

adj[x].push_back(y);

adj[y].push_back(x);

}

vector<bool>visited(n+1,false);

for(int i=1; i<=n; ++i)

{

if(!visited[i])

{

bool check = solve(adj,visited,i,n);

if(check){return "Yes";}

}

return "No";

}

179 views

0 replies

1 upvote

Ashish chauhan

Interview problems

somewhat easier approach using bfs(c++)

#include <bits/stdc++.h>

bool bfs(int src,vector<vector<int>> adj,vector<int>& visited){

queue <pair<int,int>> q;

q.push({src, -1}); // src means source node or starting node

visited[src]=1;

while(q.empty()!=true){

int node=q.front().first;

int parentNode=q.front().second;

q.pop();

for(auto it: adj[node]){

if(visited[it]==0){

visited[it]=1;

q.push({it,node});

}

else if(it!=parentNode){

return true;

}

return false;

}

string cycleDetection (vector<vector<int>>& edges, int n, int m)

{

// Write your code here.

vector<vector<int>> adj(n+1);

vector<int> visited(n+1,0);

for(int i=0;i<m;i++){

int node1=edges[i][0];

int node2=edges[i][1];

adj[node1].push_back(node2);

adj[node2].push_back(node1);

}

for(int i=1;i<=n;i++){

if(visited[i]!=1){

if(bfs(i, adj, visited)) return "Yes";

}

return "No";

}

70 views

0 replies

0 upvotes

Console