목차

Strongly Connected Component

ps
링크acmicpc.net/…
출처BOJ
문제 번호2150
문제명Strongly Connected Component
레벨플래티넘 5
분류

SCC

시간복잡도O(E+VlogV)
인풋사이즈E<=100,000
사용한 언어Python
제출기록36116KB / 228ms
최고기록180ms
해결날짜2022/10/20

풀이

코드

"""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()

,