トポロジカルソート(DFS)

2022年12月18日

説明

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