[Python] 4196 - 도미노 (플래티넘4)

1. 문제 설명

https://www.acmicpc.net/problem/4196

4196번: 도미노

메모리 실화냐

---

2. 아이디어

[Python] 2150 - Strongly Connected Component (플래티넘5)

SCC에 위상정렬까지 곁들어서 풀었다. (지금 생각해보면 위상정렬이랄 것도 없다.)

정점과 간선 정보가 100,000개 이므로 SCC에서 불필요한 내용들은 전부 제외시켜버려야

시간초과 걸려서 고생하지 않는다.

 

SSC의 실속만 쪽쪽 빨아먹은 위상정렬(이었던) 알고리즘

SCC로 사이클의 개수를 세어준다. 그렇다고 SCC 만들고 있으면 바보 신세 못 면한다.

대신에 정점마다 속해있는 사이클의 번호를 매겨준다.

작업이 끝나면 매겨빈 정점을 차례대로 훑다보면 사이클 번호가 안 맞는 접점이 있을 텐데

그곳이 Cycle이 끊긴 지점이다.

 

(1, 4, 5)는 1번, (6)은 2번, (2, 3, 7)은 3번 사이클에 속해있다. 그러면 인덱스가 4개인 새로운 리스트로

SSC 기준의 indegree 리스트를 하다 더 만들고,

사이클 넘버가 다른 구간이 나오면 indegree를 추가해준다.

이게 무슨 의미냐면 내 앞에 선행조건이 있다는 건, 즉 앞에 다른 사이클에서 날 밀어줄 여지가 있음을

의미하기 때문에 최종적으로 선행 조건이 없는 0의 개수를 찾아서 출력하면 된다.

 

---

3. 코드

import sys

sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

def dfs(node, graph, visited, queue:list):
    visited[node] = 1

    for next_node in graph[node]:
        if visited[next_node] == 0:
            dfs(next_node, graph, visited, queue)
    queue.append(node)

def make_queue(v, graph, visited):
    queue = []

    for node in range(1, v+1):
        if visited[node] == 0:
            dfs(node, graph, visited, queue)
    return queue

def reverse_dfs(node, graph, visited, graph_indegree, cnt):
    visited[node] = 1
    graph_indegree[node] = cnt

    for next_node in graph[node]:
        if visited[next_node] == 0:
            reverse_dfs(next_node, graph, visited, graph_indegree, cnt)

def check_ssc(queue:list, graph, visited, graph_indegree):
    cnt = 0

    while queue:
        node = queue.pop()
        if visited[node] == 0:
            cnt += 1
            reverse_dfs(node, graph, visited, graph_indegree, cnt)
    return cnt

def solution():  
    v, e = map(int, input().split())
    graph = [[] for _ in range(v+1)]
    rev_graph = [[] for _ in range(v+1)]
    visited = [0] * (v+1)

    for _ in range(e):
        a, b = map(int, input().split())
        graph[a].append(b)
        rev_graph[b].append(a)

    queue = make_queue(v, graph, visited)
    visited = [0] * (v+1) # visited reset
    graph_indegree = [0] * (v + 1)

    cnt = check_ssc(queue, rev_graph, visited, graph_indegree)
    scc_indegree = [0] * (cnt + 1) # scc 위상정렬

    for idx in range(1, v+1):
        for parent in graph[idx]:
            if not (graph_indegree[idx] == graph_indegree[parent]):
                scc_indegree[graph_indegree[parent]] += 1
    answer = 0
    for node in range(1, len(scc_indegree)):
        if scc_indegree[node] == 0:
            answer += 1
    print(answer)
        
t = int(input())
for _ in range(t):
    solution()