백준 9470 c++ "Strahler 순서" -[PlusUltraCode]

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

9470번: Strahler 순서

[필자 사고]

이 문제는 위상정렬 알고리즘을 사용하여 해결해야 하는 문제이다.

 

이 문제만의 특이한 점은 몇개의 노드가 nextIdx에 가리키고 있는지, 동시에 그중 가장 큰값이 무엇인지를 어떻게 저장하고 관리하는지가 핵심인 문제같다.

 

필자는 vector안에 우선순위큐를 넣어 최댓값을 바로 바로 찾을 수 있도록 문제를 해결했다. 

 

[소스 코드]

 

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

vector<vector<int>> Arr;
vector<priority_queue<int, vector<int>>> pathLoad;
vector<int> dist;
int N, M;
int ResultNum = -1;
void Input() {
	ResultNum = -1;
	cin >> N >> M;
	vector<vector<int>> Arr2;
	vector<priority_queue<int, vector<int>>> pathLoad2;
	vector<int> dist2;

	Arr2.resize(N + 1);
	pathLoad2.resize(N + 1);
	dist2.resize(N + 1, 0);
	for (int i = 0; i < M; i++) {
		int s, e;
		cin >> s >> e;
		Arr2[s].push_back(e);
		dist2[e]++;

	}
	Arr = Arr2;
	pathLoad = pathLoad2;
	dist = dist2;
}

void Topological_Sort() {
	queue<int> myQueue;
	for (int i = 1; i <= N; i++) {
		if (dist[i] == 0) {
			myQueue.push(i);
			pathLoad[i].push(1);
			ResultNum = 1;
		}
	}
	while (!myQueue.empty()) {
		int nowIdx = myQueue.front();
		ResultNum = max(ResultNum, pathLoad[nowIdx].top());
		myQueue.pop();
		for (int nextIdx : Arr[nowIdx]) {
			dist[nextIdx]--;
			pathLoad[nextIdx].push(pathLoad[nowIdx].top());
			if (dist[nextIdx] == 0) {
				if (pathLoad[nextIdx].size() >= 2) {
					int maxNum = pathLoad[nextIdx].top();
					pathLoad[nextIdx].pop();
					int maxNum2 = pathLoad[nextIdx].top();
					if (maxNum == maxNum2) {
						pathLoad[nextIdx].push(maxNum + 1);
					}
					else {
						pathLoad[nextIdx].push(maxNum);
					}
				}
				else {
					int maxNum = pathLoad[nextIdx].top();
					pathLoad[nextIdx].pop();
					pathLoad[nextIdx].push(maxNum);
				}
				myQueue.push(nextIdx);
			}
		}
	}
}


int main(void) {
	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int K;
		cin >> K;
		Input();
		Topological_Sort();
		cout << K << " ";
		cout << ResultNum << '\n';
	}
}