[백준] 9470 - Strahler 순서

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

9470번: Strahler 순서

 

정점, 유향 간선이 주어져있고 정점들의 순서를 구하는 문제이다.

딱 봐도 위상 정렬을 이용하는 문제인데, 정렬의 조건이 약간 다르다.

 

• 나머지 노드는 그 노드로 들어오는 강의 순서 중 가장 큰 값을 i라고 했을 때, 들어오는 모든 강 중에서 Strahler 순서가 i인 강이 1개이면 순서는 i, 2개 이상이면 순서는 i+1이다.

 

처음에 이 문제를 풀었을 때 단순히 정점의 정보에 순서만 저장하였다.

그래서 다음과 같은 구문을 구현했다.

 

a는 현재 정점이고, i는 a와 연결된 정점이다.

 

if (info[i] < info[a]) {
	info[i] = info[a];
}
else if (info[i] == info[a]) {
	info[i] = info[a] + 1;
}

 

이렇게 구현하면 다음과 같은 케이스에서 오답이 나온다.

 

1
1 14 13
1 9
2 9
3 10
4 10
5 11
6 11
7 12
8 12
11 13
12 13
9 14
10 14
13 14

 

마지막 노드에서 최대 순서는 1개인데, 답은 최대 순서 + 1이 나오게 된다.

그래서 info 구조를 pair<int, int>로 바꿔주었다(최대 순서, 최대 순서의 개수).

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
	int t; cin >> t;
	while (t--) {
		int k, m, p;
		cin >> k >> m >> p;

		int inp[1001] = { 0, };
		int info[1001] = {};
		vector<vector<int>> v(m + 1);

		for (int i = 0; i < p; i++) {
			int a, b; cin >> a >> b;
			v[a].push_back(b);
			inp[b]++;
		}

		queue<int> q;

		for (int i = 1; i <= m; i++) {
			if (inp[i] == 0) {
				info[i] = 1;
				q.push(i);
			}
		}

		while (!q.empty()) {
			int a = q.front();
			q.pop();

			for (auto& i : v[a]) {
				inp[i]--;
				if (info[i] < info[a]) {
					info[i] = info[a];
				}
				else if (info[i] == info[a]) {
					info[i] = info[a] + 1;
				}
				if (inp[i] == 0)q.push(i);
			}
		}

		cout << k << ' ' << info[m] << '\n';
	}


}