Editorial for Directed Cycle Detection

Remember to use this editorial only when stuck, and not to 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)

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()

Comments

There are no comments at the moment.