トポロジカルソート(DFS)
説明
DFSしながら帰りがけ順に頂点を記録することでトポロジカルソートする
def dfs(u, graph, visited, order):
visited[u] = True
for v in graph[u]:
if visited[v]:
continue
dfs(v, graph, visited, order)
order.append(u)
return
def solve(n,m,graph):
visited = [False for _ in range(n)]
order = []
for i in range(n):
if not visited[i]:
dfs(i, graph, visited, order)
order.reverse()
return order
Python
関連記事
マンハッタン距離
説明 マンハッタン距離で DD 移動することは z=x+yz=x+y、$ ...
セグメント木
説明 セグメント木 class SegTree: def __init__(se ...
多次元配列を多重ループを回してアクセスするときの注意事項(戒め)
説明 多次元配列を多重ループを回してアクセスするとき多次元配列の定義とループを回 ...
defaultdict
説明 defaultdict は dict のサブクラスで1つめの引数にdefa ...
編集距離
説明 文字列 SS と文字列 TT との編集距離の遷移の考え方は図の通り。$ ...
ディスカッション
コメント一覧
まだ、コメントがありません