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