백준 2637번 : 장난감 조립 - 위상정렬 dp C++

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

2637번: 장난감 조립

#include <bits/stdc++.h>

using namespace std;

int n , m;
vector<pair<int,int> > adj[101]; // Node, Cnt
int degree[101];
int need[101][101];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;

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

		adj[b].push_back({ a,c });
		degree[a] += c;

    }

    queue<int> Q;
    vector<int> basic;

    for (int i = 1; i <= n; i++) {
        if (degree[i] == 0) {
            Q.push(i);
            basic.push_back(i);
            need[i][i] = 1;
        }
    }

    while (!Q.empty()) {
        int x = Q.front(); Q.pop();

        for (auto i : adj[x]) {
            int nx = i.first;
            int cnt = i.second;

            for (auto b : basic) {
                need[nx][b] += need[x][b] * cnt;
            }
            degree[nx] -= cnt;

            if (degree[nx] == 0) {
                Q.push(nx);
            }
        }      
    }


    for (auto x : basic) {
        cout << x << ' ' << need[n][x] << '\n';
    }

    return 0;
}

백준 2637번