[ baekjoon ] 9470. Strahler 순서

---

문제 링크

---

## 9470. Strachler 순서

import sys
from collections import deque

input = sys.stdin.readline

t = int(input())

for _ in range(t):
  k, m, p = map(int, input().split())

  graph = [[] for _ in range(m + 1)]
  indegree = [0] * (m + 1)

  order = [0] * (m + 1)
  order_max = [[0, 0] for _ in range(m + 1)]

  for _ in range(p):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1

  q = deque()
  for i in range(1, m + 1):
    if indegree[i] == 0:
      q.append(i)

  while q:
    num = q.popleft()
    if order_max[num][1] == 1:
      order[num] = order_max[num][0]
    else:
      order[num] = order_max[num][0] + 1
    
    for i in graph[num]:
      indegree[i] -= 1
      if indegree[i] == 0:
        q.append(i)
      
      if order_max[i][0] < order[num]:
        order_max[i][0] = order[num]
        order_max[i][1] = 1
      elif order_max[i][0] == order[num]:
        order_max[i][1] += 1

  print(k, order[m])

• 위상 정렬 응용 문제
• 그래프 이론

위상 정렬을 진행하면서 진입 노드의 최댓값과 개수에 따라 노드의 순서(order)가 갱신된다.
진입 노드(A)에서 연결된 노드(B)로 order_max 배열 갱신

알고리즘 분류에서 위상 정렬 보고 푼 문제
복습할 때 위상 정렬 떠올려라

---

21.04.08 복습

## 9470.

import sys
import heapq

input = sys.stdin.readline
t = int(input())
for _ in range(t):
  k, m, p = map(int, input().split())
  parent = [0] * (m + 1)
  arr = [0] * (m + 1)
  graph = [[] for _ in range(m + 1)]
  dp = [[0] * 1001 for _ in range(1001)]

  for _ in range(p):
    a, b = map(int, input().split())
    graph[a].append(b)
    parent[b] += 1

  q = []

  for i in range(1, len(parent)):
    if parent[i] == 0: 
      heapq.heappush(q, (1, i))
      arr[i] = 1
  
  while q:
    cnt, now = heapq.heappop(q)
    for i in graph[now]:
      parent[i] -= 1

      if dp[i][1] != cnt:
        dp[i][1] = max(dp[i][1], cnt)
      elif dp[i][1] == cnt:
        dp[i][2] = max(dp[i][2], cnt)

      if parent[i] == 0: 
        arr[i] = max(dp[i][2] + 1, dp[i][1])
        heapq.heappush(q, (arr[i], i))

  print(k, arr[m])

위상정렬 떠올렸다!
이번엔 deque가 아니라 heapq를 이용했네