Editorial for Directed Cycle Detection

Use this editorial only when stuck, and do not copy-paste code from it.

Please be respectful to the problem author and editorialist. Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Use depth-first search with three states for each vertex:

$0$ means the vertex has not been visited yet.
$1$ means the vertex is currently in the active DFS path.
$2$ means the vertex and all vertices reachable through its DFS exploration are finished.

While exploring an edge $u \to v$ , if $v$ is already in state $1$ , then the edge goes back to a vertex currently on the DFS path. This creates a directed cycle, so the answer is YES.

If all searches finish without finding such an edge, the graph has no directed cycle and the answer is NO.

The implementation below uses an explicit stack instead of recursive DFS, which avoids recursion depth issues for long paths. Each vertex enters and leaves the stack at most once, and each edge is checked once, so the time complexity is $O(n + m)$ and the memory complexity is $O(n + m)$ .

Solution (Python)

Code 1

import sys


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    n, m = data[0], data[1]
    adj = [[] for _ in range(n)]

    idx = 2
    for _ in range(m):
        a = data[idx] - 1
        b = data[idx + 1] - 1
        idx += 2
        adj[a].append(b)

    state = [0] * n
    next_edge = [0] * n

    for start in range(n):
        if state[start] != 0:
            continue

        stack = [start]
        state[start] = 1

        while stack:
            u = stack[-1]
            if next_edge[u] == len(adj[u]):
                state[u] = 2
                stack.pop()
                continue

            v = adj[u][next_edge[u]]
            next_edge[u] += 1

            if state[v] == 1:
                print("YES")
                return
            if state[v] == 0:
                state[v] = 1
                stack.append(v)

    print("NO")


if __name__ == "__main__":
    main()

Comments0

No comments yet

Be the first to comment.

Editorial for Directed Cycle Detection

Approach

Solution (Python)

Comments0

New comment