BOJ9470/ C++

 

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

9470번: Strahler 순서

백준 온라인저지 9470번 문제입니다. 

위상정렬을 이용해서 풀었습니다.

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define MAX 1001

using namespace std;

int indegree[MAX];
vector<int> adj[MAX];
pair<int,int> strahler[MAX];
int t, k, m, p,sol;


int main(void) {

	cin >> t;
	while (t--) {
		cin >> k >> m >> p;
		sol = 0;
		for (int i = 0; i <= m; i++) {
			adj[i].clear();
			strahler[i] = { 0,0 };
			indegree[i] = 0;
		}

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



		queue<int>q;

		for (int i = 1; i <= m; i++) {
			if (indegree[i] == 0) {
				q.push(i);
				strahler[i] = { 1,1 };
			}
		}
		for (int i = 1; i <= m; ++i) {
			int current = q.front();
			q.pop();

			for (auto next : adj[current]) {

				if (strahler[next].first < strahler[current].first)
					strahler[next] = { strahler[current].first,1 };


				else if (strahler[next].first == strahler[current].first)
					strahler[next].second++;

				if (--indegree[next] == 0) {
					q.push(next);
					if (strahler[next].second > 1)
						strahler[next] = { strahler[next].first + 1,1 };
				}

			}
		}

		cout << k << " " << strahler[m].first << "\n";
	}

	return 0;
}

아이디어

이 문제는 한 노드로 들어오는 노드의 보유 숫자가 같은게 2개 이상이 있을때 해당 숫자에 +1을 하거나 같은 숫자가 없으면 가장 큰 수를 가진 전입 노드의 숫자를 따르게 되어있음 여기서 신경써야하는 부분은 1 2 3 노드가 각각 2 2 3의 숫자를 가지고 4의 전입 노드라고 하면 노드1, 2가 들어가면 노드 4는 3을 가지고 그 후 노드 3이 들어오게되면 노드 4는 4를 가지게 될 수 있는 케이스를 처리하면 되는 문제임

해당 케이스를 처리하기 위해 strahler의 first를 해당노드가 가진 수, second를 중복숫자의 전입여부를 저장하여 위상정렬을 이용