# Cycle Detection in Directed Graph

##### February 6, 2024

## Problem Statement #

Given a directed graph with `n`

nodes labeled from `0`

to `n-1`

, and a list of `edges`

where `edges[i] = [ai, bi]`

represents a directed edge from node `ai`

to node `bi`

, determine if the graph contains a cycle. A cycle occurs if a node can be visited more than once by following the directed edges. Return `true`

if the graph contains at least one cycle, otherwise return `false`

.

## Solution Approach #

The solution involves using Depth-First Search (DFS) to explore the graph from each unvisited node, keeping track of nodes currently in the recursion stack. If we revisit a node that is already in the recursion stack, a cycle exists.

## Algorithm Steps #

- Create an adjacency list from the
`edges`

to represent the graph. - Initialize a visited set to keep track of visited nodes and a recursion stack set to keep track of nodes in the current DFS path.
- Iterate over each node and, if it’s not visited, start a DFS from it.
- In the DFS, mark the node as visited and add it to the recursion stack. Then, visit all its neighbors. If any neighbor is already in the recursion stack, a cycle is found.
- After visiting all neighbors, remove the node from the recursion stack.
- If no cycle is found after exploring all nodes, return
`false`

.

## Code (Python) #

```
def cycleDetection(n, edges):
graph = {i: [] for i in range(n)}
for u, v in edges:
graph[u].append(v)
visited = set()
recStack = set()
def dfs(node):
if node in recStack:
return True
if node in visited:
return False
visited.add(node)
recStack.add(node)
for neighbor in graph[node]:
if dfs(neighbor):
return True
recStack.remove(node)
return False
for node in range(n):
if node not in visited:
if dfs(node):
return True
return False
# Example usage
print(cycleDetection(4, [[0, 1], [1, 2], [2, 3], [3, 1]])) # Output: True
```

## Time Complexity #

O(V + E), where `V`

is the number of vertices and `E`

is the number of edges in the graph. Each node and edge is visited at most once.

## Space Complexity #

O(V + E), for storing the graph, visited set, and recursion stack. In the worst case, the space complexity can approach O(V + E) when the graph is densely connected.