Detect Cycle in an undirected graph - DFS

Practice Link

Given an undirected graph with V vertices and E edges, check whether it contains any cycle or not.

No Cycle

Cycle exists

Note#

Graph can also be disconnected -> Check for every node as source/starting node.

Visited array cannot be the only check here since for DFS the adjacent node can also be the parent node itself, which will always be visited.

DFS#

DFS detects a cycle in an undirected graph by tracking the parent of each recursive call. When DFS visits a neighbor that is already marked as visited and that neighbor is not the immediate parent, it means we have reached a previously visited node via a different path — confirming a cycle. This avoids the false-positive that would arise from treating the back-edge to the parent as a cycle.

• Start from one node (unvisited) and explore all nodes; keep track of the parent node in each recursive call.
• Use a visited array to keep track of explored nodes.
• For every node, iterate over the adjacent nodes:
  • If not visited, call dfs() on the node and return true if a cycle is found deeper.
  • If already visited and the node is not the parent of the current node → cycle exists.
• Return false after exhausting all neighbors (handles disconnected graphs by restarting from every unvisited node).

Implementation#

bool checkCycleDFS(vector<vector<int>>& adj, vector<bool> &visited, int source, int parent)
    {
        
        visited[source]=true;
        
        for(auto dest: adj[source])
        {
            if(!visited[dest])
            {
                if(checkCycleDFS(adj, visited, dest, source))
                    return true;
            }
            else if(dest != parent)
                return true;
        }
        
        return false;
    }
  
    // Function to detect cycle in an undirected graph.
    bool isCycle(vector<vector<int>>& adj) {
        vector<bool> visited(adj.size(), false);
        vector<int> visitedNodes;
        
        for(int i=0;i<adj.size();i++)
        {
            if(!visited[i] && checkCycleDFS(adj, visited, i, -1))
                return true;
        }
        return false;
    }

Complexities#

Time Complexity: O(V+E) + O(N),#

We are exploring every vertex V and exploring all its edges. O(N) -> For covering disconnected components

Space Complexity: O(N)+O(V+E),#

O(N) to keep visited nodes, and O(V+E) to create the adjacency list.