2637.cpp

// Authored by : scsc3204
// Co-authored by : -
// http://boj.kr/75874968f2df40deb138395b97610bb3
#include <bits/stdc++.h>
using namespace std;

const int MX = 100;

vector<pair<int, int>> req[MX + 2]; // req[cur] = {nxt, c};
int cnt[MX + 2], ind[MX + 2];
bool isbase[MX + 2];

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

  fill(isbase, isbase + MX + 1, 1);

  int n, m; cin >> n >> m;
  while(m--) {
    int x, y, k;
    cin >> x >> y >> k;
    isbase[x] = 0;
    req[x].push_back({y, k});
    ind[y]++;
  }

  queue<int> q;
  q.push(n);
  cnt[n] = 1;

  while(!q.empty()) {
    int cur = q.front(); q.pop();
    for(auto [nxt, c] : req[cur]) {
      cnt[nxt] += c * cnt[cur];
      ind[nxt]--;
      if(ind[nxt] == 0) q.push(nxt);
    }
  }

  for(int i = 1; i <= n; i++)
    if(isbase[i]) cout << i << ' ' << cnt[i] << '\n';
}
/*
먼저 용어를 정의하겠습니다.
완제품을 최상위 부품, 기본 부품을 최하위 부품이라 부르겠습니다.
그리고 부품 y를 만드는 데 부품 x가 필요하다면 y를 상위 부품, x를 하위 부품이라 부르겠습니다.

20-26번째 줄에서 문제 입력 설명 상의 x, y, k를 받습니다.
즉, "중간 부품이나 완제품 X를 만드는데 중간 부품 혹은 기본 부품 Y가 K개 필요하다"는 의미라서
x는 최하위 부품이 아닙니다.
이에 따라 isbase[x]를 false로 설정하여 답 출력 시 활용합니다.
그리고 해당 정보는 req[x] = {y, k} 형태로 저장해 인접 리스트로써 활용합니다.

위상정렬을 적용하기 위해 상위 부품 y들의 indegree를 셉니다.
여기서 indegree는 곧 상위 부품 y를 필요로 하는 하위 부품 x들의 수가 됩니다.
즉, indegree가 0이 되는 때에는 상위 부품 y를 필요로 하는 하위 부품이 더이상 없다는 의미입니다.

이제 위상정렬을 적용합니다.
완제품은 1개 필요하기 때문에 cnt를 1로 설정합니다.(30번째 줄)
완제품의 indegree는 0입니다. 이는 완제품은 최상위 부품이며, 이를 필요로 하는 부품은 없기 때문입니다.

완제품의 req를 확인하면 완제품을 만드는 데 필요한 하위 부품들과 그 개수를 확인할 수 있습니다.
cnt 배열에 하위 부품들과 그 개수를 기록하는데,
완제품의 경우 1개만 필요하기 때문에 필요한 하위 부품 개수에 1을 곱한 값을 cnt 배열에 기록합니다.

예제의 경우 완제품 7을 만들기 위해 부품 6이 3개, 부품 4가 5개 필요하기 떄문에
이를 위해 필요한 부품 6의 개수는 1*3이 추가되고, 필요한 부품 4의 개수도 1*5만큼 추가됩니다.

이제 indegree가 0이 된 부품 6은 자신을 필요로 하는 부품이 없습니다.
이에 따라 완제품을 만들기 위해 필요한 부품 6의 개수가 확정됩니다.
예제에서는 부품 6이 4만큼 필요하기 때문에
이 개수만큼 부품 6을 만들기 위해 필요한 부품의 개수는 req[6]에 기록된 k들의 4배가 됩니다.
즉 부품 5가 4*2개, 부품 3이 4*3개, 부품 4가 4*4개 필요합니다.

이러한 방식으로 req를 통해 접근한 하위 부품의 indegree를 감소시키고, 
indegree가 0이 된 하위 부품들을 다시 큐에 넣으면 모든 부품의 indegree가 0이 될 때까지 정렬이 이루어집니다.

정리하자면, 위상정렬을 활용하면 어떤 부품을 필요로 하는 하위 부품이 없게 되는 시점을 알 수 있고,
그때 필요한 상위 부품 개수를 확정합니다.
그 상위 부품 개수는 그 부품을 만들기 위해 필요한 추가 하위 부품 개수를 산정할 때 반영됩니다.
그리고 최종적으로는 완제품을 만들기 위해 필요한 최하위 부품 수를 구할 수 있습니다.
*/