[백준/BOJ] 백준 9470번 : Strahler 순서

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

9470번: Strahler 순서

위상 정렬을 이용하여 들어오는 강 중에서 순서가 큰 값을 찾았을 때, 기존 큰 값과 같은 값일 때를 고려하였고 큐에 들어갈 때 가장 큰 값이 두 개 이상인 경우도 고려하여 문제를 해결했다.

 

코드

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

int tc;
int k, m, p;
vector<int> adj[1001];
vector<int> indegree(1001);
vector<int> order(1001);
vector<int> order_cnt(1001);

void Pre()
{
	for (int i = 0; i < 1001; i++)
	{
		adj[i].clear();
		indegree[i] = 0;
		order[i] = 0;
		order_cnt[i] = 0;
	}
}

int Solve()
{
	queue<int> q;
	int ret = -1;

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

	while (!q.empty())
	{
		int here = q.front();
		ret = max(ret, order[here]);
		q.pop();

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i];

			indegree[there]--;

			//들어오는 강중에서 큰 값을 찾았을때
			if (order[there] < order[here])
			{
				order[there] = order[here];
				order_cnt[there] = 1;
			}

			//기존의 큰값과 같은 크기일때
			else if (order[there] == order[here])
			{
				order_cnt[there]++;
			}

			if (indegree[there] == 0)
			{
				if (order_cnt[there] >= 2)
					order[there]++;

				q.push(there);
			}
		}
	}

	return ret;
}

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

	cin >> tc;

	for (int t = 0; t < tc; t++)
	{
		Pre();

		cin >> k >> m >> p;

		for (int i = 0; i < p; i++)
		{
			int a, b;
			cin >> a >> b;

			adj[a].push_back(b);
			indegree[b]++;
		}

		int result = Solve();

		cout << k << " " << result << "\n";
	}

	return 0;
}