ALDS1_11_B: Depth First Search(続き2)

スタック使う版
ややこしい

ところでPythonのリストはスタックとして使うのに不足ないだけの
関数はそろってるんですけど
名前がそれっぽくないので今ひとつピンとこないですね
appendがpushだっけ？とかなってしまって毎回REPLで試してから使ったりとか
スタックとして使うならスタックっぽい名前がいいですね
push、pop、top、isEmptyくらい

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

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

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

    def next(u):
        for v in range(nodes[u].nt, n + 1):
            nodes[u].nt += 1
            if adj_mat[u][v] == 1:
                return v
        return - 1

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

        S = []
        S.append(id)
        nodes[id].u = Node.GRAY
        nodes[id].d = timestamp
        while S != []:
            u = S[-1]
            v = next(u)
            if v != -1:
                if nodes[v].u == Node.WHITE:
                    nodes[v].u = Node.GRAY
                    timestamp += 1
                    nodes[v].d = timestamp
                    S.append(v)
            else:
                S.pop()
                nodes[u].u = Node.BLACK
                timestamp += 1
                nodes[u].f = timestamp

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

    return nodes