[도미노/P4/Python3]

4196번 도미노 P4

 

문제
도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어 세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러뜨릴 수 있다. 그러나, 가끔씩 도미노가 다른 블록을 넘어뜨리지 못하게 배치되어 있다면, 우리는 다음 블록을 수동으로 넘어뜨려야 한다. 이제 각 도미노 블록의 배치가 주어졌을 때, 모든 블록을 넘어뜨리기 위해 손으로 넘어뜨려야 하는 블록 개수의 최솟값을 구하자.

입력
첫 번째 줄에 테스트 케이스의 개수가 주어진다.각 테스트 케이스의 첫 번째 줄에는 두 정수 N, M이 주어지며 두 수는 100,000을 넘지 않는다. N은 도미노의 개수를, M은 관계의 개수를 나타낸다. 도미노 블록의 번호는 1과 N 사이의 정수다. 다음 M개의 줄에는 각각 두 정수 x, y가 주어지는데, 이는 x번 블록이 넘어지면 y번 블록도 넘어짐을 뜻한다.

출력
각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 정답은 손으로 넘어뜨려야 하는 최소의 도미노 블록 개수이다.

 

그래프 이론, 위상 정렬, 방향 비순환 그래프, 강한 연결 요소

 

코사라주의 알고리즘의 일부 아이디어를 참고해서 풀이하였다.

 

진입차수가 낮은 정점이 스택의 뒤에 쌓이도록 방문하지 않은 모든 정점에 대해 dfs를 돌린다.

스택에서 뽑은 정점에서 다시 dfs를 하여 이동 가능한 정점을 방문 처리를 한다.

이때 뽑아서 dfs를 시작한 정점의 개수가 무너뜨려야 하는 도미노의 개수로 찾았다.

 

 

import sys
sys.setrecursionlimit(10**6)

for t in range(int(sys.stdin.readline())):
    v, e = map(int, sys.stdin.readline().split())
    routes = [[] for _ in range(v+1)]
    visit = [False] * (v+1)
    
    for _ in range(e):
        sv, ev = map(int, sys.stdin.readline().split())
        routes[sv].append(ev)
    stk = []
    def dfs(v):
        visit[v] = True
        for vv in routes[v]:
            if not visit[vv]:
                dfs(vv)
        stk.append(v)
    
    result = 0
    
    def r_dfs(v):
        visit[v] = True
        for vv in routes[v]:
            if visit[vv]: continue
            visit[vv] = True
            r_dfs(vv)
    
    for i in range(1, v+1):
        if visit[i]: continue
        dfs(i)
    visit = [False] * (v+1)
        
    while stk:
        v = stk.pop()
        if visit[v]: continue
        r_dfs(v)
        result += 1
    print(result)

 

 

 

---