Given a directed graph with V vertices (numbered from 1 to V) and E directed edges, determine if the graph contains at least one cycle. The graph is represented as a list of edges, where each edge is a pair [u, v] indicating a directed edge from vertex u to vertex v.
Input: V=3, E=3, edges=[[1,2],[2,3],[3,1]]
Output: Yes
Explanation: The graph forms a cycle 1→2→3→1.
Input: V=4, E=3, edges=[[1,2],[2,3],[3,4]]
Output: No
Explanation: The graph is a linear chain with no cycles.
Input: V=5, E=5, edges=[[1,2],[2,3],[3,1],[4,5],[5,4]]
Output: Yes
Explanation: There are two cycles: one among vertices 1,2,3 and another among vertices 4,5.
The key insight is that a cycle in a directed graph exists if, during a Depth-First Search (DFS), we encounter a node that is already present in the current recursion stack. This indicates a back edge, which forms a cycle.
visited to track all visited nodes, and recStack to mark nodes in the current DFS recursion stack.recStack.recStack, a cycle is detected; return true.recStack and return false.#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
bool isCyclic(int V, vector<vector<int>>& edges) {
vector<vector<int>> adj(V+1);
for (auto& e : edges) {
adj[e[0]].push_back(e[1]);
}
vector<bool> visited(V+1, false);
vector<bool> recStack(V+1, false);
for (int i = 1; i <= V; i++) {
if (!visited[i] && dfs(i, adj, visited, recStack)) {
return true;
}
}
return false;
}
private:
bool dfs(int node, vector<vector<int>>& adj, vector<bool>& visited, vector<bool>& recStack) {
visited[node] = true;
recStack[node] = true;
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
if (dfs(neighbor, adj, visited, recStack)) {
return true;
}
} else if (recStack[neighbor]) {
return true;
}
}
recStack[node] = false;
return false;
}
};
int main() {
Solution sol;
int V1 = 3;
vector<vector<int>> edges1 = {{1,2},{2,3},{3,1}};
cout << (sol.isCyclic(V1, edges1) ? "Yes" : "No") << endl;
int V2 = 4;
vector<vector<int>> edges2 = {{1,2},{2,3},{3,4}};
cout << (sol.isCyclic(V2, edges2) ? "Yes" : "No") << endl;
int V3 = 5;
vector<vector<int>> edges3 = {{1,2},{2,3},{3,1},{4,5},{5,4}};
cout << (sol.isCyclic(V3, edges3) ? "Yes" : "No") << endl;
return 0;
}import java.util.*;
public class Solution {
public boolean isCyclic(int V, List<int[]> edges) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i <= V; i++) {
adj.add(new ArrayList<>());
}
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
}
boolean[] visited = new boolean[V+1];
boolean[] recStack = new boolean[V+1];
for (int i = 1; i <= V; i++) {
if (!visited[i] && dfs(i, adj, visited, recStack)) {
return true;
}
}
return false;
}
private boolean dfs(int node, List<List<Integer>> adj, boolean[] visited, boolean[] recStack) {
visited[node] = true;
recStack[node] = true;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
if (dfs(neighbor, adj, visited, recStack)) {
return true;
}
} else if (recStack[neighbor]) {
return true;
}
}
recStack[node] = false;
return false;
}
public static void main(String[] args) {
Solution sol = new Solution();
int V1 = 3;
List<int[]> edges1 = Arrays.asList(new int[]{1,2}, new int[]{2,3}, new int[]{3,1});
System.out.println(sol.isCyclic(V1, edges1) ? "Yes" : "No");
int V2 = 4;
List<int[]> edges2 = Arrays.asList(new int[]{1,2}, new int[]{2,3}, new int[]{3,4});
System.out.println(sol.isCyclic(V2, edges2) ? "Yes" : "No");
int V3 = 5;
List<int[]> edges3 = Arrays.asList(new int[]{1,2}, new int[]{2,3}, new int[]{3,1}, new int[]{4,5}, new int[]{5,4});
System.out.println(sol.isCyclic(V3, edges3) ? "Yes" : "No");
}
}def detect_cycle(V, edges):
adj = [[] for _ in range(V+1)]
for u, v in edges:
adj[u].append(v)
visited = [False] * (V+1)
rec_stack = [False] * (V+1)
def dfs(node):
visited[node] = True
rec_stack[node] = True
for neighbor in adj[node]:
if not visited[neighbor]:
if dfs(neighbor):
return True
elif rec_stack[neighbor]:
return True
rec_stack[node] = False
return False
for i in range(1, V+1):
if not visited[i] and dfs(i):
return True
return False
if __name__ == "__main__":
V1, edges1 = 3, [[1,2],[2,3],[3,1]]
print("Yes" if detect_cycle(V1, edges1) else "No")
V2, edges2 = 4, [[1,2],[2,3],[3,4]]
print("Yes" if detect_cycle(V2, edges2) else "No")
V3, edges3 = 5, [[1,2],[2,3],[3,1],[4,5],[5,4]]
print("Yes" if detect_cycle(V3, edges3) else "No")function detectCycle(V, edges) {
const adj = Array.from({ length: V + 1 }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
}
const visited = new Array(V + 1).fill(false);
const recStack = new Array(V + 1).fill(false);
function dfs(node) {
visited[node] = true;
recStack[node] = true;
for (const neighbor of adj[node]) {
if (!visited[neighbor]) {
if (dfs(neighbor)) {
return true;
}
} else if (recStack[neighbor]) {
return true;
}
}
recStack[node] = false;
return false;
}
for (let i = 1; i <= V; i++) {
if (!visited[i] && dfs(i)) {
return true;
}
}
return false;
}
const V1 = 3, edges1 = [[1,2],[2,3],[3,1]];
console.log(detectCycle(V1, edges1) ? "Yes" : "No");
const V2 = 4, edges2 = [[1,2],[2,3],[3,4]];
console.log(detectCycle(V2, edges2) ? "Yes" : "No");
const V3 = 5, edges3 = [[1,2],[2,3],[3,1],[4,5],[5,4]];
console.log(detectCycle(V3, edges3) ? "Yes" : "No");Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. Each vertex and edge is processed once during DFS.
Space Complexity: O(V), due to the adjacency list, visited array, recursion stack array, and recursion depth, all proportional to V.
Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.