9470번: Strahler 순서

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


$O(tn)$

dfs를 통해 말단 노드에서 거슬러 올라가며 dp를 해준다.

#include<cstdio>
#include<vector>
using namespace std;
int t, k, m, p, dp[1001];
vector<int> adj[1001];
int f(int h) {
        if (dp[h]) return dp[h];
        int ck = 1;
        for (auto it : adj[h]) {
                if (f(it) == dp[h]) ck = 1;
                if (f(it) > dp[h]) {
                        dp[h] = f(it);
                        ck = 0;
                }
        }
        return dp[h] += ck;
}
int main() {
        for (scanf("%d", &t); t--;) {
                scanf("%d%d%d", &k, &m, &p);
                for (int i = 1; i <= m; i++) adj[i].clear(), dp[i] = 0;
                for (int i = 0, x, y; i < p; i++) {
                        scanf("%d%d", &x, &y);
                        adj[y].push_back(x);
                }
                printf("%d %d\n", k, f(m));
        }
        return 0;
}