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

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

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

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

코드

#include #include #include #include #include using namespace std; int tc; int k, m, p; vector adj[1001]; vector indegree(1001); vector order(1001); vector 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 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 << "

"; } return 0; }

from http://geniusjo-story.tistory.com/517 by ccl(A) rewrite - 2021-09-03 02:26:49