KOI(한국정보올림피아드) 2000년 중등부 1번 장난감조립

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

#include <stdio.h>
#define MAX_N 100
using namespace std;

int N, M;
int a[MAX_N+1][MAX_N+1]; //인접 행렬 형태
int n[MAX_N+1]; //n[i] = 완제품 N을 만들기 위해 필요한 부품 i의 개수
bool not_leaf[MAX_N+1] = {false}; //not_leaf[i] = i가 기본부품이면 false, 아니면 true

void solve(int i, int v) {
    n[i] += v;
    for(int j=1; j<=N; j++) {
        if(a[i][j] > 0) // 부품 i가 j를 필요로 하면
            solve(j,v*a[i][j]);
    }
}
int main()
{
    scanf("%d %d", &N, &M);
    for(int m=0; m<M; m++) {
        int t1, t2, t3;
        scanf("%d %d %d", &t1, &t2, &t3);
        a[t1][t2] = t3;
        not_leaf[t1] = true; //여기에 안걸리면 기본부품이므로 false
    }
    solve(N,1);

    for(int i=1; i<=N; i++) {
        if(!not_leaf[i]) //부품 i가 기본부품이면
            printf("%d %d\n", i, n[i]);
    }
    return 0;
}