Pythonでスタックを利用した深さ優先探索

# はじめに
最近競技プログラミングを始め、その奥深さにハマっている筆者です。
でも、競技プログラミングって普通の人はアルゴリズムを知ってないとある一定のレベルからまったく歯が立たなくなりますよね :disappointed_relieved:

なので、[レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】](https://qiita.com/e869120/items/eb50fdaece12be418faa)の「[分野別　初中級者が解くべき過去問精選 100 問](https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7%B4%9A%E8%80%85%E3%81%8C%E8%A7%A3%E3%81%8F%E3%81%B9%E3%81%8D%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-100-%E5%95%8F)」をちょっとずつ解いている今日この頃です！

# 深さ優先探索
今回気になったのは、深さ優先探索です。今までは再帰で実装していたのですが、調べてみるとスタックを使う方法もあるということなので、スタックを使って実装していこうと思います。

# 例題
過去問精製 100 問の深さ優先探索、基本問題と書かれている、[ALDS1_11_B](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B&lang=ja) を解きます。
この問題の難しかったポイントは発見時刻と、探索の完了時刻を出力するところでした。（まだまだ初心者なので . . . )

## 1. 入力
最初の行に頂点数 $n$ 、続く $n$ 行に、
頂点の番号 $u$ 、隣接する頂点の数 $k$ 、隣接する頂点の番号 $v_1 \ v_2 \ ... \ v_k$ が与えられる。

```python
n = int(input())
ukv = [[0, 0, 0]] + [list(map(int, input().split())) for _ in range(n)]
```
頂点番号と index 番号をそろえるため、0 のリストを最初に付けています。（絶対に必要という訳ではありません。）

## 2. 必要な変数
```python
stack = []
visited = []
time = 0
d = [0] * (n + 1)
f = [0] * (n + 1)
```
スタックの役割を果たす `stack` ( `collections` の `deque` を使ってもいいようです。今回はリストで実装しています。）
すでに訪れた頂点を記録しておく `visited`
時刻を表す `time`
頂点の発見時刻のリスト `d`
頂点の完了時刻のリスト `f`
（ `d` と `f` も index 番号をそろえるため、`n+1` 個分にしています。）

## 3. 探索部分
```python
while stack:
    s = stack[-1]             # (1) 探索する頂点
    k = ukv[s][1]             # (2) s から隣接する頂点の数
    if k == 0:                # (6) s から隣接する頂点がなくなったので、
        stack.pop()           #     stack から s を取り除く
        time += 1
        f[s] = time           # (7) s の探索を完了した時刻
    else:
        v = ukv[s].pop(2)     # (3) s から隣接する番号が一番小さい頂点
        ukv[s][1] -= 1        # (4) s から隣接する頂点の数を減らす
        if v not in visited:
            stack.append(v)
            visited.append(v)
            time += 1
            d[v] = time       # (5) v を発見した時刻

```
ポイントは変数 `s` を定義する際、`stack` から `pop()` しないことです。
私ははじめ発見時刻と完了時刻を別のリストで管理しようとしてわからなくなってしまいました。
`stack` から `s` を取り除くのは、上の (6) に来た時です。`s` の探索が完了した時というのは、`s` から到達可能なすべての頂点を発見し、`s` に戻ってきた時です。なので、(4) で隣接する頂点の数を減らしています。

これで `stack` や `visited` に `1` を入れてやれば入力例はクリアできました。
ですが、このまま提出するとテストケース 1 から <font color="Red">WA</font> してしまいます :scream:
> 探索は元の始点から到達可能なすべての頂点を発見するまで続き、未発見の頂点が残っていれば、その中の番号が一番小さい１つを新たな始点として探索を続けます。

見落としていました。

## 4. 未発見の頂点部分
この問題では $1\leq n \leq 100$ 程度なので、1 から n+1 のループで対処しました。

```python
for i in range(1, n + 1):
    if i not in visited:
        stack.append(i)
        visited.append(i)
        time += 1
        d[i] = time
```
`i` が `visited` に入っていなければ、未発見の頂点なので、探索を続けます。

## 5. 回答例
```python
n = int(input())
ukv = [[0, 0, 0]] + [list(map(int, input().split())) for _ in range(n)]

stack = []
visited = []
time = 0
d = [0] * (n + 1)
f = [0] * (n + 1)
for i in range(1, n + 1):
    if i not in visited:
        stack.append(i)
        visited.append(i)
        time += 1
        d[i] = time

        while stack:
            s = stack[-1]
            k = ukv[s][1]
            if k == 0:
                stack.pop()
                time += 1
                f[s] = time
            else:
                ukv[s][1] -= 1
                v = ukv[s].pop(2)
                if v not in visited:
                    stack.append(v)
                    visited.append(v)
                    time += 1
                    d[v] = time

for i in range(1, n + 1):
    print(i, d[i], f[i])
```
問題なく <font color="green">AC</font> することができました。
無駄の多いコードかもしれませんが、個人的にはわかりやすく解くことができたのではないかと思っています :thumbsup:
コードの改良などありましたら、どんどんコメントください！！

# おわりに
この問題は題名に Depth First Search とあるように深さ優先探索を練習するためのものでした。基本中の基本ですね！

個人的には深さ優先探索は、スタックを使った実装がわかりやすいような気がします。もちろん問題によって再帰と使い分ける必要があると思いますが。

競技プログラミングは一つの問題に様々なアプローチがあるため、引き出しを増やすのは必須です。これからもちょっとずつ増やしていけたらなぁ . . .

ちなみに私はコンテストに参加し始めたばかりのひよっこです :hatched_chick:
https://atcoder.jp/users/ajim