[파이썬, 자바] 백준 4196 : 도미노 (플레4)

[파이썬, 자바] 백준 4196 : 도미노 (플레4)

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

---

풀이

방향성 생각

• 타잔 알고리즘으로 얻은 SCC는 위상정렬의 역순으로 나온다.
• 얻은 SCC에서 각 scc를 하나의 노드로 인식하게 만들어준다.
• 새로운 노드간 그래프를 읽어서 진입차수를 계산해주기.

 

---

파이썬

from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = lambda : sys.stdin.readline().strip()

TC = int(input())
for tc in range(TC):

    # 타잔
    N,M = map(int,input().split())

    # 방문, 그룹관리, 카운팅, 스택 관리
    V = [-1]*(N+1)
    P = [-1]*(N+1)
    count = [0]
    stack = deque()
    on_stack = [False]*(N+1)

    # 그래프
    G = [[] for _ in range(N+1)]
    for _ in range(M):
        a,b = map(int,input().split())
        G[a].append(b)

    # 타잔 알고리즘
    SCC = []
    def dfs(x):

        # 방문처리
        V[x] = count[0]
        P[x] = count[0]
        count[0] += 1
        stack.append(x)
        on_stack[x] = True

        # 탐색
        for nx in G[x]:
            if V[nx] == -1:
                dfs(nx)
                P[x] = min(P[x],P[nx])
            elif on_stack[nx]:
                P[x] = min(P[x],V[nx])

        # SCC 추출하기
        if V[x] == P[x]:
            scc = []
            while stack:
                w = stack.pop()
                on_stack[w] =  False
                scc.append(w)
                if w==x:
                    break
            SCC.append(scc)

    # 모든 노드에 대해서 DFS
    for i in range(1,N+1):
        if V[i] == -1:
            dfs(i)

    # 노드에 그룹 번호 번호 매기기
    group = [-1]*(N+1)
    for idx,scc in enumerate(SCC,start=1):
        for x in scc:
            group[x] = idx

    # 진입차수 계산
    rank = [0]*(len(SCC)+1)
    for x in range(1,N+1):
        for nx in G[x]:
            if group[x] != group[nx]:
                rank[group[nx]] += 1
    print(rank[1:].count(0))

---

코멘트

• 쉽지않음