[백준 9470] Strahler 순서 (python)

9470번: Strahler 순서

---

 

위상정렬을 이용하여 푼다.

 

1. [진입차수, 최대레벨, 최대레벨개수]를 나타내는 indegree 배열을 생성한다.
2. 간선들은 ndict에 저장한다.
3. 진입차수(indegree[i][0])가 0인 정점들을 queue 에 넣고 최대레벨(indegree[i][1])을 1로 설정해준다.
4. queue에서 뽑아 해당 정점과 연결되어있는 정점들의 진입차수들을 1씩 낮춰주면서 최대레벨과 최대레벨개수를 갱신해준다.
5. 만약 차수가 0이 된다면 최대레벨 개수가 2이상이라면 최대레벨을 1 올려준다.
6. 마지막 indegree[M]의 레벨을 출력해준다.

 

import sys
from collections import deque, defaultdict
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    K, M, P = map(int, input().split())
    indegree = [[0, 0, 0] for _ in range(M+1)]
    ndict = defaultdict(list)
    for _ in range(P):
        s, e = map(int, input().split())
        ndict[s].append(e)
        indegree[e][0] += 1

    order = [0]*(M+1)
    queue = deque()
    for i in range(1, M+1):
        if indegree[i][0] == 0:
            queue.append(i)
            indegree[i][1] = 1

    while queue:
        x = queue.popleft()
        for i in ndict[x]:
            indegree[i][0] -= 1
            if indegree[i][1] < indegree[x][1]:
                indegree[i][1] = indegree[x][1]
                indegree[i][2] = 1
            elif indegree[i][1] == indegree[x][1]:
                indegree[i][2] += 1
            if indegree[i][0] == 0:
                if indegree[i][2] > 1:
                    indegree[i][1] += 1
                queue.append(i)

    print(K, indegree[M][1])