Undirected Graph Cycle GFG

• Link: https://www.geeksforgeeks.org/problems/detect-cycle-in-an-undirected-graph/1?utm_source=youtube&utm_medium=collab_striver_ytdescription&utm_campaign=detect-cycle-in-an-undirected-graph

Question

Given an undirected graph with V vertices labelled from 0 to V-1 and E edges, check whether the graph contains any cycle or not. The Graph is represented as an adjacency list, where adj[i] contains all the vertices that are directly connected to vertex i.

NOTE: The adjacency list represents undirected edges, meaning that if there is an edge between vertex i and vertex j, both j will be adj[i] and i will be in adj[j].

Examples:

Input: adj = 1], [0,2,4], [1,3], [2,4], [1,3 
Output: 1
Explanation:

1->2->3->4->1 is a cycle.

Input: adj = ], [2], [1,3], [2
Output: 0
Explanation:

No cycle in the graph.

Constraints:
1 ≤ adj.size() ≤ 105

Try more examples

Approach 1: BFS

Intuition

• BFS
• If already visited cycle exists
• Consider connected components
• Maintain parent node

Algorithm

1. 1. Create a visited array initialized with 0.
2. Loop through the visited array
   1. If node is not visited
      1. if (Call bfs on that node) return true, return true

Code

class Solution {
  public:
    // Function to detect cycle in an undirected graph.
    bool bfs(int startNode, vector<vector<int>>& adj, vector<int>& visited) {
        queue<pair<int, int>> q;
        
        q.push({startNode, -1});
        visited[startNode] = 1;
        
        while (!q.empty()) {
            int node = q.front().first;
            int source = q.front().second;
            q.pop();
            
            for (auto neighbor: adj[node]) {
                if (neighbor == source) continue;
                if (!visited[neighbor]) {
                    q.push({neighbor, node});
                    visited[neighbor] = 1;
                } else {
                    return true;
                }
            }
        }
        return false;
    }
    
    bool isCycle(vector<vector<int>>& adj) {
        // Code here
        int n = adj.size();
        vector<int> visited(n, 0);
        // node, source
        
        for (int i = 0 ; i < n ; i++) {
            if (!visited[i]) {
                if (bfs(i, adj, visited)) return true;
            }
        }
        
        return false;
    }
};

Complexity Analysis

• Time Complexity: $O(V+E)$
• Space Complexity: $O(V)$

Approach 2: DFS

Intuition

• DFS
• Maintain parent node

Algorithm

1. Create a visited array initialized with 0.
2. Loop through the visited array
   1. If node is not visited
      1. if (Call dfs on that node) return true, return true

Code

class Solution {
  public:
    bool dfs(int node, int parent, vector<vector<int>>& adj, vector<int>& visited) {
        if (visited[node]) return false;
        
        visited[node] = 1;
        for (auto neighbor: adj[node]) {
            if (neighbor == parent) continue;
            if (visited[neighbor]) {
                return true;
            }
            if(dfs(neighbor, node, adj, visited)) return true ;
        }
        return false;
    }
    
    bool isCycle(vector<vector<int>>& adj) {
        // Code here
        int n = adj.size();
        vector<int> visited(n, 0);
        // node, source
        
        for (int i = 0 ; i < n ; i++) {
            if (!visited[i]) {
                if (dfs(i, -1 adj, visited)) return true;
            }
        }
        
        return false;
    }
};

Complexity Analysis

• Time Complexity: $O(V+2E)$
• Space Complexity: $O(V)$