강한 연결 요소를 공부하면 알게 되는, 본격적인 SCC 문제의 시작이라 할 수 있는 도미노 문제를 풀이해보겠다.

BOJ 4196 - 도미노 링크
(2022.09.20 기준 P4)
(치팅하지 마세요)

문제

x번 블록이 넘어지면 y번 블록도 넘어짐을 뜻하는 관계 M개가 주어져 있는 도미노 N개가 있을 때, 손으로 넘어뜨려야 하는 최소 도미노 블록 개수

알고리즘

두 정점 간 순서가 정해져 있는데, 사이클이 있을 수 있는 방향 그래프이다.
그래서 도미노 블록이 사이클에 들어가면 사이클 안 블록들만 쓰러뜨리고 끝나기 때문에 다시 손으로 남은 블록을 넘어뜨려야 한다. 이 사이클 안 블록들은 SCC를 이루고 있다. 그러므로 SCC를 구하여 다시 구해진 SCC들을 위상 정렬에서 사용하는 진입차수를 응용해야 한다. 자세한 풀이는 후술.

풀이

알고리즘 부분에서 설명했듯이 블록이 사이클 안으로 들어가면 그 사이클 내에서 끝나버린다.
그 사이클을 이루고 있는 블록들은 SCC이다.
그러면 하나의 SCC를 하나의 정점으로 보면 SCC들의 그래프는 사이클이 없는 DAG가 된다.
그렇다면 진입차수가 0인 정점이 무조건 생긴다. 그 정점은 그래프의 시작 부분이라고 생각할 수 있고, 도미노 블록으로 생각해보면 도미노가 시작되는 부분이자 다른 어떤 도미노를 넘어뜨려도 시작되는 부분인 도미노 블록을 쓰러뜨리지 못한다. 그러므로 이 문제에서 구하는 답인 손으로 넘어뜨리는 최소 도미노 블록의 개수이므로 진입차수가 0인 SCC의 개수가 답이 된다.

진입차수를 구할 땐 이렇게 하자.
먼저 코사리주나 타잔 알고리즘을 통해 SCC를 구하면 각 정점마다 SCC의 번호가 부여된다. 그러면 모든 정점에 대해 이어진 정점을 검사하면 되는데, 만약 두 정점의 SCC 번호가 다를 경우에는 SCC가 다른. 즉, 한 사이클에 포함되어 있지 않은 두 정점이므로, 이어진 정점이 포함된 SCC의 진입차수를 증가시키면 된다.
그리고 모든 정점에 대해 검사가 끝나면 진입차수가 0인 SCC의 개수를 구해 출력하면 된다.

코드

# 코사리주
import sys; input = sys.stdin.readline
sys.setrecursionlimit(1000000)

def dfs(here):
    visited[here] = True
    for there in graph[here]:
        if not visited[there]:
            dfs(there)
    queue.append(here)

def reverse_dfs(here):
    visited[here] = True
    ids[here] = idx
    # SCC를 따로 찾지 않아도 되므로 밑줄 생략
    # scc.append(here)
    for there in reverse_graph[here]:
        if not visited[there]:
            reverse_dfs(there)

for _ in range(int(input())):
    N, M = map(int, input().split())
    graph = [[] for __ in range(N + 1)] # 그래프
    reverse_graph = [[] for __ in range(N + 1)] # 역방향 그래프
    for __ in range(M):
        x, y = map(int, input().split())
        graph[x].append(y)
        reverse_graph[y].append(x)

    # 정방향 탐색으로 정점 쌓기
    queue = []
    visited = [False] * (N + 1)
    for here in range(1, N + 1):
        if not visited[here]:
            dfs(here)
    # 역방향 탐색으로 SCC 찾기
    visited = [False] * (N + 1)
    ids = [-1] * (N + 1)
    idx = 0
    while queue:
        here = queue.pop()
        if not visited[here]:
            reverse_dfs(here)
            idx += 1

    # SCC들의 진입차수 구하기
    ind = [0] * idx # 진입차수 배열을 SCC 개수만큼 만들고
    for here in range(1, N + 1): # 모든 정점에 대해
        for there in graph[here]: # 이어진 정점을 검사 (정방향 그래프)
            if ids[here] != ids[there]: # 만약 두 정점의 SCC 번호가 다르면
                ind[ids[there]] += 1 # 이어진 정점의 SCC의 진입차수를 증가시킨다.
    # 진입차수가 0인 SCC의 개수가 정답이 된다.
    answer = 0
    for i in range(idx):
        if not ind[i]:
            answer += 1
    print(answer)

여담

풀이는 되게 간단하고, 또 코드보면 쉽다고 느껴진다. 하지만 제대로 풀기 전엔 정말 어려웠던 문제.
맞왜틀한다 싶으면 이 반례를 한번 보자.

[input]
1
5 6
1 2
2 3
3 1
1 4
4 5
5 1

[output]
0

[answer]
1

이 문제의 질문 게시판과 어느 한 블로그에 있던 반례인데, 난 틀리는 이유를 바로 알게 되었다.