Given an undirected graph with V vertices represented by an adjacency list, determine whether any component contains a cycle.
A cycle exists when a path starts and ends at the same vertex without reusing an edge. The graph can be disconnected, so every component must be checked.
Example 1
Input: V = 4, adj = [[1,2],[0,2],[0,1,3],[2]]
Output: true
Explanation: Vertices 0, 1, 2 form a cycle.
Example 2
Input: V = 4, adj = [[1],[0,2],[1,3],[2]]
Output: false
Explanation: The graph forms a straight chain with no cycle.
Approach 1
Depth First Search explores each connected component by following one path as deeply as possible before backtracking. Since every undirected edge appears in both directions, the edge leading back to the immediate parent represents normal traversal and must be ignored.
Encountering an already visited neighbor different from the parent indicates an alternate route to a previously reached vertex, confirming a cycle. An outer traversal across all vertices ensures coverage of disconnected components.
Algorithm
Initialize a
visitedarray of sizeVwith all entries marked false, allowing previously explored vertices to be identified.Traverse every vertex and start DFS from each unvisited vertex with parent
-1, ensuring that every disconnected component is examined.Mark the current vertex as visited upon entering DFS, preventing repeated recursive exploration.
Examine every adjacent vertex of the current vertex to inspect all edges belonging to the component.
For an unvisited neighbor, continue DFS with the current vertex as the parent and immediately propagate a detected cycle.
For a visited neighbor, return true when the neighbor differs from the parent, as an alternate path confirms a cycle.
Return false after all connected components finish without detecting a cycle.
Dry Run
DETECT cycle
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Function to run DFS with parent tracking. bool dfs(int node, int parent, vector<int>& visited, vector<vector<int>>& adj) { visited[node] = 1; // Explore every adjacent vertex. for (int neighbor : adj[node]) { if (!visited[neighbor]) { if (dfs(neighbor, node, visited, adj)) { return true; } } else if (neighbor != parent) { return true; } } // No cycle found through current DFS path. return false; }public: // Function to detect a cycle in an undirected graph. bool isCycle(int vertices, vector<vector<int>>& adj) { vector<int> visited(vertices, 0); // Start DFS from every component. for (int node = 0; node < vertices; node++) { if (!visited[node]) { if (dfs(node, -1, visited, adj)) { return true; } } } // No component contains a cycle. return false; }};// Driver code.int main() { int vertices = 4; vector<vector<int>> adj = {{1, 2}, {0, 2}, {0, 1, 3}, {2}}; Solution sol; cout << (sol.isCycle(vertices, adj) ? "true" : "false"); return 0;}Complexity Analysis
Time Complexity: O(V+E), where V and E are the numbers of vertices and edges; DFS processes every vertex once and every undirected edge twice.
Space Complexity: O(V), where the visited array and recursive DFS stack can each store up to V vertices.
Approach 2
Breadth First Search explores each connected component level by level while storing every queued vertex with the corresponding parent. Parent tracking distinguishes the normal reverse edge of an undirected graph from an edge forming a cycle.
Encountering a visited neighbor different from the stored parent confirms two distinct routes to the same vertex. An outer traversal starts BFS for every unvisited vertex, covering disconnected components.
Algorithm
Initialize a
visitedarray of sizeVwith all entries marked false, allowing previously processed vertices to be recognized.Traverse every vertex and start BFS from each unvisited vertex, ensuring that all disconnected components are checked.
Mark the starting vertex as visited and add
{vertex, -1}to the queue, where-1indicates the absence of a parent.Continue processing while the queue contains pairs and remove the front
{current, parent}pair for level-order exploration.Examine every neighbor of
current; for an unvisited neighbor, mark the vertex before insertion and enqueue{neighbor, current}to record the traversal edge.Return true when a visited neighbor differs from
parent, as an alternate route to an already reached vertex confirms a cycle.Return false after every connected component has been processed without detecting a cycle.
Dry Run
detect-cycle-undirected-graph-bfs-corrected
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Function to run BFS with parent tracking. bool bfs(int start, vector<int>& visited, vector<vector<int>>& adj) { queue<pair<int, int>> q; visited[start] = 1; q.push({start, -1}); // Process vertices in breadth-first order. while (!q.empty()) { auto [node, parent] = q.front(); q.pop(); // Check all neighbors of current vertex. for (int neighbor : adj[node]) { if (!visited[neighbor]) { visited[neighbor] = 1; q.push({neighbor, node}); } else if (neighbor != parent) { return true; } } } // No cycle found inside current component. return false; }public: // Function to detect a cycle in an undirected graph. bool isCycle(int vertices, vector<vector<int>>& adj) { vector<int> visited(vertices, 0); // Start BFS from every component. for (int node = 0; node < vertices; node++) { if (!visited[node]) { if (bfs(node, visited, adj)) { return true; } } } // No component contains a cycle. return false; }};// Driver code.int main() { int vertices = 4; vector<vector<int>> adj = {{1}, {0, 2}, {1, 3}, {2}}; Solution sol; cout << (sol.isCycle(vertices, adj) ? "true" : "false"); return 0;}Complexity Analysis
Time Complexity: O(V+E), where V and E are the numbers of vertices and edges; BFS processes every vertex once and every undirected edge twice.
Space Complexity: O(V), where the visited array and BFS queue can each store up to V vertices.
Interview follow-up Questions
Every undirected edge appears in both directions, so the direct edge back to the parent must not be counted as a cycle.
Be the first to add a comment.