그래프의 싱크

• 문제에서 말하는 '그래프의 싱크'는, 주어진 그래프의 SCC들로부터 condensation graph를 만들었을때 outdegree가 0인 scc들에 포함된 노드들과 동일하다.
• condensation graph 를 만든 뒤에, outdegree가 0인 scc를 찾기만 하면 되므로, 시간복잡도는 O(V+E)

"""Solution code for "BOJ 6543. 그래프의 싱크".

- Problem link: https://www.acmicpc.net/problem/6543
- Solution link: http://www.teferi.net/ps/problems/boj/6543

Tags: [SCC]
"""

from teflib import graph as tgraph


def main():
    while (line := input()) != '0':
        n, m = [int(x) for x in line.split()]  # pylint: disable=unused-variable
        graph = [[] for _ in range(n)]
        edges = [int(x) for x in input().split()]
        for v, w in zip(edges[::2], edges[1::2]):
            graph[v - 1].append(w - 1)

        con_graph, scc = tgraph.condensation_graph(graph)
        answer = []
        for successor_u, scc_u in zip(con_graph, scc):
            if not successor_u:
                answer.extend(scc_u)
        print(*(u + 1 for u in sorted(answer)))


if __name__ == '__main__':
    main()

• Dependency: teflib.graph.condensation_graph