> For the complete documentation index, see [llms.txt](https://kde6260.gitbook.io/dev/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kde6260.gitbook.io/dev/algorithm-quiz/graph-cycle.md).

# 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](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-Lxjeea-QoqGhWvjq7yU%2F-LxjjWBLwlpx03m46HHu%2F47815.jpg?alt=media\&token=72368104-5657-4588-b8bb-fb4cee758da0)

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

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

![Directed Cyclic Graph에서의 DFS](https://1792721125-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lo8iAG2zHsS2e9mIAqX%2F-Lxjeea-QoqGhWvjq7yU%2F-Lxjk53GpY11WgvyS8eD%2Fcycle_dfs.jpg?alt=media\&token=6c712d51-f1d2-42e2-b709-6b52b9a1693e)

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

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

```python
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](https://github.com/dev-daeun/algo-quiz/blob/master/leetcode/207.py)