DFS（深さ優先探索）でサイクル検出を考える【python実装】

## 有効サイクルとは

有効サイクルとは、下の図のように、例えばノード 0 から開始し、0 → 1 → 2 → 1 → 2 → 1 … というように 1 と 2 を何度も繰り返し周回するような有向グラフの形です。
<img width="300px" alt="s1" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2727397/92ee571f-13c3-0301-6b25-868191682a93.png">

## サイクル検出 - 発想１

サイクルを検出するために、次のような手順を踏むことができます。

1. グラフをDFS（深さ優先探索）で探索（ノードのスタート地点は、`for`文を使って、`0`から`n`までを全探索する）
2. 訪れたノードを記録する（`visited[crr] = True`などとしておく）
3. 次の行き先ノードで、すでに訪れていれば（`visited[nxt] = True`）、サイクルと判定します。

この手順を踏めば、大体うまく行きそうです。

**コードのざっくりとしたイメージ**

```python
cycle = False
def dfs(g, crr, visited):
    visited[crr] = True 
    for nxt in g[crr]:
        if not visited[nxt]:
            dfs(g, nxt, visited)
        else:
			global cycle
            cycle = True 

for crr in range(n):
    if not visited[crr]:
        dfs(g, crr, visited)
```
ちなみに無向グラフのときは、この考え方でほぼうまく行きます。

### 発想１で具体例を見る

発想１の方法で、例えば以下の「ケース１」を見ると、ノード０からスタートして
０→１→２→１(２回目なのでサイクル)

<img width="300px" alt="s2" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2727397/c57c24ae-2acb-0c05-ede9-e943272b4f48.png">


といった具合にサイクルを判定できます。
サイクルなしの「ケース２」でも、
０→１→２

<img width="300px" alt="s3" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2727397/55cb57b4-7b11-b636-339d-3170bfb60d86.png">

という流れになります。
しかし「ケース３」ではうまく行きません。
「ケース２」と似ていますが、ノード番号の順番が違います。
０→ ２、1 → 0（２回目なのでサイクル？？？）

<img width="300px" alt="s4" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2727397/004c0a6e-bcfa-54c1-a9ba-cad5f6d34ee7.png">


まず、ノード０からの探索をします。0→２で一度探索を終え、次はfor文により、ノード１から再び探索を始めます。しかし、1→０で２度目のノード０へ来るので、サイクルありの判定になってしまいます。

すでに探索済みのノードに到達した場合、それ以降のノードは探索しないとしたいですが、「探索済みのノードへ行こうとしたらサイクルあり」という条件を設定しているため、「ケース3」のように探索順序によって問題が発生する可能性があります。

### 問題点

この発想１の問題点は、(訪れた or 訪れていない)のフラグだけでは

- サイクル時の２回目の訪れ
- 探索順序による２回目の訪れ

を区別できないことです。


<img width="100%" alt="s5" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2727397/dd823a89-0873-5077-4636-d9d866426685.png">

なので

- 成功例の「ケース１」ではON
- 失敗例の「ケース３」ではOFF

になるようなフラグが必要です。
そうすれば、２つのケースを区別できます。

## サイクル検出 - 発想２

発想１に、次の新たな要素を加えます。

1. グラフをDFS（深さ優先探索）で探索（ノードのスタート地点は、`for`文を使って、`0`から`n`までを全探索する）
2. 行き掛け順に、訪れたノードを記録する（`visited[crr] = True`とかしておく）
3. 帰り掛け順に、訪れたノードを記録する（`finished[crr] = True`とかしておく）**new**
4. 次の行き先ノードの内、`visited[nxt] = True` かつ `finished[nxt] = False`となるようなノードがあれば、サイクルと判定

DFS（深さ優先探索）は、探索の行きと帰りがあります。それぞれについて、行きには`visited`という配列、帰りには`finished`という配列で、ノードに訪れたことを記録します。

行き掛け順、帰り掛け順という言葉がよくわからない人は、[ここ](https://www.momoyama-usagi.com/entry/info-algo-tree-traverse#__preorder)など参考にしてみてください。

```python
cycle = True
def dfs(g, crr, visited):
    visited[crr] = True # 行き掛け順の記録
    for nxt in g[crr]:
        if not visited[nxt]:
            dfs(g, nxt, visited)
        elif not finished[nxt]: # new
			global cycle
            cycle = True
    finished[crr] = True # new　帰り掛け順の記録

for crr in range(n):
    if not visited[crr]:
        dfs(g, crr, visited)
```
### 発想２で具体例を見る

「ケース１」を発想２で考えます。

<img width="300px" alt="s5" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2727397/d6a23cb2-b78e-c949-c10d-78cde429c018.png">

まず、行き掛け順に0→1→2→1(2回目）と探索します。２回目のノード１へ来たとき、`visited[1] = True` 、`finished[1] = False`なので、サイクルありの判定になります。
行き掛け順の後は、帰り掛け順に`finished`を1→2→1→0の順にTrueにします。

「ケース３」も考えてみましょう。

<img width="300px" alt="s5" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2727397/636738dd-eeb9-ba72-58cd-caeeafe9b359.png">

まず、ノード０からスタートして、行き掛け順に０→２と探索します。このとき、`visited[0]`, `visited[2]`を順に`True`にします。それから、帰りがけ順に２→０と戻り、`finished[2]`, `finished[0]`を順に`True`にします。
これで一旦探索を終え、今度はノード１からスタート。
１→０の順に探索をします。このとき、ノード０は一度訪れているので`visited[0] = True`ですが、`finishd[0] = True`（もうすでに探索済み）なので、サイクルありの判定を無視します。

結果としてサイクルなしと判定し、うまく行きます。

## 全コード

アルゴ式の問題「[Q8. サイクル検出 (D)](https://algo-method.com/tasks/970)」対応したコードです。

```python
import sys
sys.setrecursionlimit(10**4)

n, m = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    g[u].append(v)

cycle = False
def dfs(g, crr, visited, finished):
    visited[crr] = True
    for nxt in g[crr]:
        if not visited[nxt]:
            dfs(g, nxt, visited, finished)
        elif not finished[nxt]:
            global cycle
            cycle = True
    finished[crr] = True

visited = [False] * n
finished = [False] * n
for crr in range(n):
    if not visited[crr]:
        dfs(g, crr, visited, finished)

print("Yes" if cycle else "No")

```