[백준] 9470 Strahler 순서 c++

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

9470번: Strahler 순서

 

풀이과정

문제를 잘 읽지 않고 풀어서 고생했던 문제이다...

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

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

int T, K, M, P, A, B;
int indegree[1001];
int res[1001];

queue <int> q;
vector <int> v[1001];

void topologySort() {
	for (int i = 1; i <= M; i++) {
		if (indegree[i] == 0) {
			q.push(i);
			res[i] = 1; // 진입차수가 0이면 순서는 1
		}
	}

	vector <int> num[1001];

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

		for (int i = 0; i < v[now].size(); i++) {
			int next = v[now][i];
			indegree[next]--;
			num[next].push_back(res[now]); // 현재 노드의 순서 push

			int mnum = 0;
			if (indegree[next] == 0) {
				q.push(next);

				for (int i = 0; i < num[next].size(); i++) {
					mnum = max(mnum, num[next][i]);
				}
				int cnt = 0;
				for (int i = 0; i < num[next].size(); i++) {
					if (mnum == num[next][i]) cnt++;
				}
				// 순서가 i인 강이 1개이면 순서는 i
				if (cnt == 1) res[next] = res[now];
				// 순서가 i인 강이 2개 이상이면 순서는 i + 1
				else if (cnt > 1) res[next] = mnum + 1;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> T;
	while (T--) {
		cin >> K >> M >> P;
		for (int i = 0; i < P; i++) {
			cin >> A >> B;
			v[A].push_back(B);
			indegree[B]++;
		}
		topologySort();

		cout << K << " ";
		int ans = 0;
		for (int i = 1; i <= M; i++) {
			ans = max(ans, res[i]);
		}
		cout << ans << "\n";

		//testcase 수행을 위한 초기화
		memset(indegree, 0, sizeof(indegree));
		memset(v, 0, sizeof(v));
		memset(res, 0, sizeof(res));
	}
}