graph에서 cycle 유무 확인하기

정점의 갯수와 간선이 주어졌을 때 그래프에 사이클이 있는지 없는지 확인하는 방법 각 정점의 pre_time과 post_time을 이용하는 것이다.

어떤 정점 v에서 이동 가능한 경로를 탐색하기 시작했을 때 순간을 pre_time, 이동가능한 경로를 모두 탐색하고 난 뒤 다시 v로 되돌아왔을 때의 순간을 post_time 으로 정의한다.

아래 그림은 DAG(Directed Acyclic Graph)의 정점 A에서 시작하는 DFS 과정이다. 정점을 방문할 때 pre_time을 기록하고, 탐색 후 다시 정점으로 돌아왔을 때 post_time을 기록한다. (pre_time/post_time 으로 표현)

Directed Acyclic Graph에서의 DFS

D에서 C를 방문하려고 할 때 C의 pre_time과 post_time이 이미 기록되어 있는 것을 볼 수 있다.

반대로 사이클이 존재하는 그래프에서의 DFS 과정은 아래와 같다.

Directed Cyclic Graph에서의 DFS

D에서 A를 방문하려고 할 때 A의 pre_time은 기록되어 있으나 post_time은 기록되어 있지 않은 것을 볼 수 있다. 따라서 어떤 정점과 인접한 다른 정점을 방문하고자 할 때 pre_time은 있으나 post_time이 없다면 그래프에는 사이클이 존재한다.

위 방법을 코드로 나타내면 아래와 같다.

from time import time
from sys import stdin


def dfs():
    for i in range(n):
        if not pre_time[i]:
            result = is_cyclic(i)
            if result:
                return True
    return False


def is_cyclic(v):
    pre_time[v] = time()

    for adj_v in adjacent_list[v]:
        if pre_time[adj_v]:  # pre_time은 기록되어 있으나
            if not post_time[adj_v]: # post_time이 기록되어 있지 않으면
                return True  # 사이클이 존재한다.
        else:
            result = is_cyclic(adj_v)
            if result:
                return True

    post_time[v] = time()
    return False


if __name__ == '__main__':
    n, m = list(map(int, stdin.readline().split(' ')))
    pre_time = [None for _ in range(n)]
    post_time = [None for _ in range(n)]
    adjacent_list = [list() for _ in range(n)]

    for _ in range(m):
        v1, v2 = list(map(int, stdin.readline().split(' ')))
        adjacent_list[v1-1].append(v2 - 1)

    print(1) if dfs() else print(0)

재귀호출 없이 스택으로 구현: leetcode - 207. Course Schedule