테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 그래프의 싱크 ======

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


===== 코드 =====
<dkpr py>
"""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()
</dkpr>
  * Dependency: [[:ps:teflib:graph#condensation_graph|teflib.graph.condensation_graph]]

{{tag>BOJ ps:problems:boj:플래티넘_4}}