有向グラフで到達可能な頂点すべてに辺を張るやつ

[kemuniku]

N回DFSなら

proc make_can_move_graph(G:UnWeightedDirectedGraph):UnWeightedDirectedGraph=
    var newG = initUnWeightedDirectedGraph(len(G))
    for i in range(len(G)):
        var alr = initHashSet[int]()
        proc dfs(x:int)=
            for y in G[x]:
                if y notin alr:
                    alr.incl(y)
                    newG.add_edge(i,y)
                    if y != i:
                        dfs(y)
        dfs(i)
    return newG