문제 링크

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

문제 설명

• M번 노드의 Strahler 순서를 출력
• 현재 노드의 Strahler 순서
  • 진입 노드의 Strahler 순서의 최댓값을 X라 할 때
  • X가 1개이면 X
  • X가 2개 이상이면 X+1

풀이

• 위상 정렬을 진행하면서
• 현재 노드에 대해 Strahler 순서를 계산
  • 현재 노드의 Strahler 순서를 계산할 때는 이미 진입 노드들의 Strahler 순서가 계산되어 있음
• 다음 노드에 대해 진입 노드의 순서의 최댓값, count 저장

코드

import sys
from collections import deque


def init():
    k, m, p = map(int, ipt().split())
    indegree = [0] * (m+1)
    adj_list = [[] for _ in range(m+1)]
    for _ in range(p):
        a, b = map(int, ipt().split())
        adj_list[a].append(b)
        indegree[b] += 1
    strahler_order = [0] * (m+1)
    max_count_list = [[0, 0] for _ in range(m+1)]
    return k, m, p, indegree, adj_list, strahler_order, max_count_list


ipt = sys.stdin.readline
opt = sys.stdout.write
t = int(ipt())
for _ in range(t):
    k, m, p, indegree, adj_list, strahler_order, max_count_list = init()
    q = deque()
    for i in range(1, m+1):
        if indegree[i] == 0:
            q.append(i)
    while q:
        cn = q.popleft()
        # 현재 노드 order 계산
        if max_count_list[cn][1] == 1:
            strahler_order[cn] = max_count_list[cn][0]
        else:
            strahler_order[cn] = max_count_list[cn][0] + 1
        for nn in adj_list[cn]:
            indegree[nn] -= 1
            if not indegree[nn]:
                q.append(nn)
            # max count 계산
            if max_count_list[nn][0] < strahler_order[cn]:
                max_count_list[nn][0] = strahler_order[cn]
                max_count_list[nn][1] = 1
            elif max_count_list[nn][0] == strahler_order[cn]:
                max_count_list[nn][1] += 1
    opt(f'{k} {strahler_order[m]}\n')