백준 4196 <도미노> Python

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

4196번: 도미노

---

 

백준 2150 <Strongly Connected Component>

바로 전에 포스팅했던 SCC 의 응용 문제입니다. SCC 를 구분한 뒤 각 SCC 들을 위상정렬해 풀 수 있는 문제였습니다. 각 진입차수가 0 인 SCC 는 무조건 손으로 넘어뜨려야 하는 그룹이므로 그 수를 세면 풀 수 있습니다.

---

from collections import defaultdict, deque

import sys

input = sys.stdin.readline

sys.setrecursionlimit(100000)

def solution(V, E, edge_list):

    # 그래프 / graph[i] = [i 의 자식들]

    global graph

    graph = [[] for _ in range(V+1)]

    for parent, child in edge_list:

        graph[parent].append(child)

    # 스택

    global stack

    stack = []

    # scc 리스트

    global scc_list

    scc_list = [0 for _ in range(V+1)]

    # 방문 기록

    global visited

    visited = [0 for _ in range(V+1)]

    # 방문 순서

    global visit_num

    visit_num = 0

    # 순서대로 노드 방문

    for node in range(1, V+1):

        # 방문한 적 없으면 방문

        if not visited[node]:

            tarjan(node)

    # scc 목록

    scc_keys = list(set(scc_list[1:]))

    # 외부 scc 진입차수 사전 / topol_list[i] = i 의 진입 차수

    topol_dict = defaultdict(int)

    for parent, child in edge_list:

        # 부모와 자식의 scc 가 다르면 진입차수 + 1

        if scc_list[parent] != scc_list[child]:

            topol_dict[scc_list[child]] += 1

    # 진입차수가 0 인 scc 카운트

    count_manual = 0

    for num in scc_keys:

        if not topol_dict[num]:

            count_manual += 1

    print(count_manual)

    return

# 타잔 알고리즘

def tarjan(now_node):

    # 방문 순서 + 1

    global visit_num

    visit_num += 1

    # 자신이 순환 시작 노드라고 가정

    lowest_node = visit_num

    # 방문 순서 기록

    visited[now_node] = visit_num

    # 스택에 추가

    stack.append(now_node)

    # 자식 순회

    for node in graph[now_node]:

        # 아직 방문하지 않은 자식이면

        if not visited[node]:

            # 순환 찾기 / 순환 중 시작 노드 찾기

            lowest_node = min(lowest_node, tarjan(node))

        # 방문 했지만 scc 가 결정이 안된 노드면

        elif not scc_list[node]:

            # 순환 끝에 순환 시작 노드 찾음

            lowest_node = min(lowest_node, visited[node])

    # 자신이 순환 시작 노드면

    if lowest_node == visited[now_node]:

        # 스택에서 자신이 나올때 까지 팝하면서 scc 기록

        while True:

            # 마지막 노드

            last_node = stack.pop()

            # scc 기록

            scc_list[last_node] = now_node

            # 스택의 마지막이 자신이면 끝

            if last_node == now_node:

                break

    return lowest_node

T = int(input())

for __ in range(T):

    V, E = map(int, input().split())

    edge_list = [list(map(int, input().strip().split())) for _ in range(E)]

    solution(V, E, edge_list)