각 테스트 케이스의 첫째 줄에는 K, M, P가 주어진다. K는 테스트 케이스 번호, M은 노드의 수, P는 간선의 수이다. (2 ≤ M ≤ 1000) 다음 P개 줄에는 간선의 정보를 나타내는 A, B가 주어지며, A에서 B로 물이 흐른다는 뜻이다. (1 ≤ A, B ≤ M) M은 항상 바다와 만나는 노드이며, 밖으로 향하는 간선은 존재하지 않는다.
출력
각 테스트 케이스마다 테스트 케이스 번호와 입력으로 주어진 하천계의 Strahler 순서를 한 줄에 하나씩 출력한다.
입력 예시
1
1 7 8
1 3
2 3
6 4
3 4
3 5
6 7
5 7
4 7
출력 예시
1 3
풀이
위상 정렬 문제. 간단히 복습을 위해 위상 정렬 방식을 정리하면...
엣지 방향을 통해 각 노드의 진입 차수를 구하고
진입 차수가 0인 노드들을 초기화 후 큐에 삽입하여
BFS를 수행하되, 현재 시점의 노드와 연결된 다음 노드의 진입 차수를 1씩 줄이고
만약 진입 차수가 0이 된 노드가 존재한다면 큐에 삽입한다.
이렇게 하면 위상에 따라 순차적으로 접근할 수 있다.
이 문제는 여기에 Strahler 순서 개념을 도입했다. Strahler 순서가 2 이상인 노드의 경우, 진입 차수가 0이 될 때까지 큐에 삽입되지 않음이 보장된다. 즉 이 노드들에 대해 직전의 Strahler 순서를 모두 업데이트할 수 있으므로, 다음 노드 접근시마다 strahler 순서의 최댓값을 업데이트하는 방식을 채용하도록 한다.
그렇다면 현재 노드에 접근할 때 Strahler 순서가 최댓값임이 보장되며, 최댓값의 경우의 수가 2 이상이라면 최댓값에 +1을 갱신 후 탐색을 이어나갈 수 있다. 모든 탐색이 종료된 후, 바다라고 확정된 M번째 노드의 Strahler 순서를 출력하면 된다.
풀이 코드
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
def solve() :
K, M, P = map(int, input().split())
edge_dict = defaultdict(list)
indegree_list = [0]*M
visited = [False]*M
strahler_list = [[0]*2 for _ in range(M)]
q = deque()
for _ in range(P) :
a, b = map(int, input().split())
edge_dict[a-1].append(b-1)
indegree_list[b-1] += 1
for i in range(M) :
if indegree_list[i] == 0 :
q.append(i)
visited[i] = True
strahler_list[i] = [1, 1]
while q :
node = q.popleft()
if strahler_list[node][1] > 1 :
strahler_list[node][0] += 1
for nxt in edge_dict[node] :
indegree_list[nxt] -= 1
if strahler_list[nxt][0] < strahler_list[node][0] :
strahler_list[nxt] = [strahler_list[node][0], 1]
elif strahler_list[nxt][0] == strahler_list[node][0] :
strahler_list[nxt][1] += 1
if not indegree_list[nxt] :
q.append(nxt)
print(K, strahler_list[-1][0])
T = int(input())
for _ in range(T) :
solve()
