Use recursionStack[] array to keep track of vertices currently in the DFS recursion stack

How Different is Recursion Stack From Visited Array?

visited[] is used to keep track of already visited vertices during the entire DFS process and never gets reset
recursionStack[] is used to keep track of visiting vertices during DFS from a particular vertex and gets reset once we backtrack from that vertex
This distinction is crucial for directed graphs as we need to detect back edges within the current DFS path

Code

[{"language":"C++","code":"class Solution {\npublic:\n    bool hasCycle(int n, vector<vector<int>>& edges) {\n        // Build adjacency list\n        vector<vector<int>> adj(n);\n        for (auto& edge : edges) {\n            adj[edge[0]].push_back(edge[1]);\n        }\n        \n        vector<bool> visited(n, false);\n        vector<bool> recursionStack(n, false);\n        \n        // Check each component\n        for (int i = 0; i < n; i++) {\n            if (!visited[i]) {\n                if (dfs(i, adj, visited, recursionStack)) {\n                    return true;\n                }\n            }\n        }\n        \n        return false;\n    }\n    \nprivate:\n    bool dfs(int u, vector<vector<int>>& adj, vector<bool>& visited, vector<bool>& recursionStack) {\n        // Mark current node as visited and add to recursion stack\n        visited[u] = true;\n        recursionStack[u] = true;\n        \n        // Visit all adjacent vertices\n        for (int v : adj[u]) {\n            if (!visited[v]) {\n                // If not visited, recurse\n                if (dfs(v, adj, visited, recursionStack)) {\n                    return true;\n                }\n            } else if (recursionStack[v]) {\n                // If visited and in recursion stack, cycle found\n                return true;\n            }\n        }\n        \n        // Remove from recursion stack before backtracking\n        recursionStack[u] = false;\n        return false;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    bool</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> hasCycle</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> n</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"colo

Related Tags