• 강한 연결 요소 (Strongly Connected Component / SCC)의 기본 문제. 주어진 그래프에서 SCC들을 추출하기만 하면 된다.
• 사실 추출하기만 하면 된다고 하기엔, 사소하지만 출력할때 SCC들을 정점번호순으로 정렬해야 하는 요구사항이 하나 더 있긴 하다. 그래서 시간복잡도에도 SCC를 구하는 O(V+E)에, SCC들을 정렬하는 O(VlogV)까지 추가해서 적었다.

"""Solution code for "BOJ 2150. Strongly Connected Component".

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

Tags: [SCC]
"""

import sys
from teflib import graph as tgraph


def main():
    V, E = [int(x) for x in sys.stdin.readline().split()]
    graph = [[] for _ in range(V)]
    for _ in range(E):
        A, B = [int(x) for x in sys.stdin.readline().split()]
        graph[A - 1].append(B - 1)

    sccs, _ = tgraph.strongly_connected_component(graph)
    for scc in sccs:
        scc.sort()
    print(len(sccs))
    for scc in sorted(sccs):
        print(*(u + 1 for u in scc), '-1')


if __name__ == '__main__':
    main()

• Dependency: teflib.graph.strongly_conencted_component