BOJ)2056 작업

문제: icpc.me/2056

a번 작업을 실행할 때 선행되야 되는 작업 b의 셋이 주어질 때 모든 작업을 완료하는데 걸리는 시간을 출력하는 문제이다.

문제에서 선행관계는 항상 번호가 증가하는 순서로 이루어진다고 하였으므로 사이클이 존재하지 않는 DAG임을 알 수 있다.

따라서 우리는 위상정렬을 해준 뒤 위상정렬의 순서대로 일을 처리해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, in[10002], c[10002], x, y, r;
vector<vector<int>> vt;
int main() {
    scanf("%d", &n);
    vt.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &c[i], &x);
        for (int j = 0; j < x; j++) {
            scanf("%d", &y);
            vt[y].push_back(i);
            in[i]++;
        }
    }
    vector<int> q;
    for (int i = 1; i <= n; i++) {
        if (!in[i])
            q.push_back(i);
    }
    while (q.size() != n) {
        vector<int> v;
        for (int h : q) {
            if (!(--c[h]))
                v.push_back(h);
        }
        r++;
        for (int h : v) {
            for (int g : vt[h]) {
                if (!(--in[g]))
                    q.push_back(g);
            }
        }
    }
    x = 0;
    for (int h : q)
        x = max(x, c[h]);
    printf("%d\n", r + x);
    return 0;
}