백준 9470번 Strahler 순서

사용한 알고리즘 : 위상정렬

​

각 점 간의 연결 관계를 arr 라는 벡터 행렬에 만들어 주었습니다.

예를 들어 a 점에서 b 점으로 가는 edge가 존재하면 , arr[a].push_back(b)를 해준 후,

degree 행렬을 만들어, degree[b]++ 해주었습니다.

​

이후 queue를 하나 만들어, degree가 0인 점들을 넣어주고,

이들의 순서를 pair로 저장해 주었습니다.

pair을 쓴 이유는, 문제에서 어떠한 점에 들어오는 (최대의) 순서가 2개 이상이면 +1을 해준다 하였기에,

pair(순서, 개수) 식으로 저장해 주었습니다.

​

이후 queue에서 하나씩 꺼내보며, 그들의 arr에 연결 된 다른 점들(자식들)을 업데이트 해주고,

이때 다른 점들의 degree가 0이되면 queue에 넣어 주는 식으로 위상정렬을 실시했습니다.

​

마지막에 저장해둔 pair 들을 보며, 가장 큰 순서를 출력해주었습니다.

	#include <bits/stdc++.h>
	using namespace std;
	#define pii pair<int, int>
	int T, K, M, P, cor;
	int degree[1111];
	vector<int> arr[1111];
	pii ans[1111];
	queue<int> Q;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> T;
	while(T--){
	cor = 0;
	cin >> K >> M >> P;
	for (int i = 0; i <= M; ++i){
	arr[i].clear();
	degree[i] = 0;
	ans[i] = pii(0,0);
	}
	while(!Q.empty()) Q.pop();
	for (int i = 0; i < P; ++i){
	int a, b;
	cin >> a >> b;
	arr[a].push_back(b);
	degree[b]++;
	}
	for (int i = 1; i <= M; ++i){
	if(degree[i]==0){
	Q.push(i);
	ans[i] = pii(1,1);
	}
	}
	for (int i = 1; i <= M; ++i){
	int curr = Q.front();
	Q.pop();
	for (int next: arr[curr]){
	if(ans[next].first < ans[curr].first)
	ans[next] = pii(ans[curr].first,1);
	else if(ans[next].first == ans[curr].first)
	ans[next].second++;
	degree[next]--;
	if(degree[next]==0){
	if(ans[next].second>1) ans[next] = pii(ans[next].first+1,1);
	Q.push(next);
	}
	}
	}
	for (int i = 1; i <= M; ++i)
	cor = max(cor, ans[i].first);
	cout << K << ' ' << cor << '\n';
	}
	return 0;
	}

view raw BOJ 9470.cpp hosted with ❤ by GitHub