백준) 9470 Strahler 순서

Strahler 순서

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

위상정렬의 변형문제.

strachler 순서가 정해지는 데 일련의 규칙이 있고, 따라서 간선을 지울 때 다른 작업을 추가로 해줘야 한다.

먼저 진입차수가 0인 노드들의 strachler 순서는 0이다. 이제 이 노드들이 큐에서 꺼내질 때, 노드의 진출 간선들을 지우면서

규칙에 따른 작업을 한다.

규칙은 다음과 같다.

• 나머지 노드는 그 노드로 들어오는 강의 순서 중 가장 큰 값을 i라고 했을 때, 들어오는 모든 강 중에서 Strahler 순서가 i인 강이 1개이면 순서는 i, 2개 이상이면 순서는 i+1이다.

그래서 각 노드는 순서값, 들어오는 강의 순서들, 가장 큰 값을 기억해야 한다.

이후에는 규칙대로 풀면 된다.

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
struct Strahler {
    int max, order_cnt[1001], order;
};
 
int in[1001];
int k, kk, m, p, a, b;
 
int main() {
    scanf("%d", &k);
    while (k--) {
        scanf("%d %d %d", &kk, &m, &p);
        for (int i = 1; i <= m; ++i)
            in[i] = 0;
 
        vector<vector<int>> vec(m + 1);
        for (int i = 0; i < p; ++i) {
            scanf("%d %d", &a, &b);
            vec[a].push_back(b);
            in[b]++;
        }
 
        vector<Strahler> st(m + 1);
        queue<int> q;
        for (int i = 1; i <= m; ++i) {
            if (!in[i]) {
                q.push(i);
                st[i].order = 1;
            }
        }
 
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
 
            for (auto next : vec[cur]) {
                if (st[next].max < st[cur].order)
                    st[next].max = st[cur].order;
 
                st[next].order_cnt[st[cur].order]++;
 
                in[next]--;
                if (!in[next]) {
                    if (st[next].order_cnt[st[next].max] == 1)
                        st[next].order = st[next].max;
                    else if (st[next].order_cnt[st[next].max] > 1)
                        st[next].order = st[next].max + 1;
                    q.push(next);
                }
            }
        }
        printf("%d %d\n", kk, st[m].order);
    }
    return 0;
}