ALDS1_11_B: Depth First Search(続き)

解説を読む
スタックとループを使った解を説明してから、再帰でもできるよと書いてある
どっちかというと、再帰を使ったアルゴリズムをスタックとループに翻訳している
感じがしなくもないけど
自分のコードも半分再帰、半分ループだから半端だけど
すっかり再帰にしようとすると、イミュータブルな世界では、ってなっちゃうような

あと、隣接行列を使って書いてあるな

隣接行列を用いた深さ優先探索は、・・・大きなグラフに対しては適当ではありません。後の章で、隣接リストを使ったより高速な実装方法を学習します。

隣接リストのほうが自然だろうと思ってそっち使ったんだけど
隣接行列を使いなさいとか書いてあったっけ？

あと、状態をBLACK、WHITE、GRAYで管理してるけどどうしてこれが必要なんだ？
ていうか自分はなぜ使わずに済んでたんだろう？
たぶんdを見て訪問済みかどうか判定してたところと対応するんだろうけど
なんか考慮漏れでもあるかなあ？

再帰のまま隣接行列に書き換え（テキストそのままではない
BLACK、WHITE、GRAYは使っていない

class Node():
    def __init__(self):
        self.d = 0
        self.f = 0

def read_adj():
    n = int(input())
    adj_mat = [[0] * (n + 1) for _ in range(n + 1)]

    for _ in range(n):
        id, _, *v = [int(x) for x in input().split()]
        for adj_id in v:
            adj_mat[id][adj_id] = 1

    return n, adj_mat

def depth_first_search(n, adj_mat):
    nodes = [Node() for _ in range(n + 1)]
    timestamp = 1

    def dfs(id):
        nonlocal adj_mat, n, nodes, timestamp

        nodes[id].d = timestamp
        for adj_id in range(1, n + 1):
            if adj_mat[id][adj_id] == 1 and \
                    nodes[adj_id].d == 0:
                timestamp += 1
                dfs(adj_id)
        timestamp += 1
        nodes[id].f = timestamp

    for id in range(1, n + 1):
        if nodes[id].d == 0:
            dfs(id)
            timestamp += 1

    return nodes

def print_result(n, nodes):
    for id in range(1, n + 1):
        print(id, nodes[id].d, nodes[id].f)

def main():
    n, adj_mat = read_adj()
    nodes = depth_first_search(n, adj_mat)
    print_result(n, nodes)

if __name__ == '__main__':
    main()

やっぱりこれでもジャッジ通るなあ
BLACK、WHITE、GRAY入れてみたけど、必要性はわからなかった
この問題では使わないけど、やりたいことによっては使うようなものなのかな？

class Node():
    WHITE = 0
    GRAY = 1
    BLACK = 2

    def __init__(self):
        self.u = Node.WHITE
        self.d = 0
        self.f = 0

def depth_first_search(n, adj_mat):
    nodes = [Node() for _ in range(n + 1)]
    timestamp = 1

    def dfs(id):
        nonlocal adj_mat, n, nodes, timestamp

        nodes[id].u = Node.GRAY
        nodes[id].d = timestamp
        for adj_id in range(1, n + 1):
            if adj_mat[id][adj_id] == 1 and \
                    nodes[adj_id].u == Node.WHITE:
                timestamp += 1
                dfs(adj_id)
        nodes[id].u = Node.BLACK
        timestamp += 1
        nodes[id].f = timestamp

    for id in range(1, n + 1):
        if nodes[id].u == Node.WHITE:
            dfs(id)
            timestamp += 1

    return nodes