Cycle Detection with DFS

1. In Undirected Graphs: When DFS visits a node, it marks it as visited. If it encounters a node that has already been visited and it's not the parent of the current node, a cycle is detected.

2. In Directed Graphs: DFS marks nodes as visited and also tracks nodes currently in the recursion stack (the path it's exploring). If it encounters a node already in the stack, a cycle is detected, indicating a back edge.

In both cases, DFS helps identify cycles by checking if a node is revisited in an unexpected way.

DFS(graph, node, visited, recursion_stack):
    // Mark the current node as visited
    visited[node] = true
    recursion_stack[node] = true

    // Visit all the neighbors of the current node
    for each neighbor in graph[node]:
        if not visited[neighbor]:
            DFS(graph, neighbor, visited, recursion_stack)
        else if recursion_stack[neighbor]:
            // A cycle is detected
            return true

    // Backtrack, remove the node from recursion stack
    recursion_stack[node] = false

    return false