并行课程 III

给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n 。同时给你一个二维整数数组 relations记录每门课程的先修课程
请你根据以下规则算出完成所有课程所需要的最少月份数：
如果一门课的所有先修课都已经完成，你可以在任意时间开始这门课程。
你可以同时上任意门课程，请你返回完成所有课程所需要的最少月份数。

1. 拓扑排序

class Solution {
public:
    int minimumTime(int n, vector<vector<int>> &relations, vector<int> &time) {
        vector<int> edges[n];//邻接表
        vector<int> indege(n);//记录点的入度
        for (auto &x: relations) {//建图
            edges[x[0] - 1].push_back(x[1] - 1);//课程号转换成0~n-1
            indege[x[1] - 1]++;
        }
        queue<int> q;
        int res = 0;
        vector<int> reach(n);//记录节点结束时间
        for (int i = 0; i < n; i++)//初始化度入度为0节点
            if (!indege[i]){ 
                q.push(i);     
                reach[i] = time[i];
                res = max(res,reach[i]);
            }
       
        while (!q.empty()) {//拓扑排序
            auto x = q.front();//取出无前驱节点
            q.pop();
            for (auto j: edges[x]) {
                reach[j] = max(reach[j], reach[x] + time[j]);//通过前驱节点的结束时间，更新当前节点结束时间
                res = max(res,reach[j]);
                if (--indege[j] == 0)
                    q.push(j);
            }
        }
        return res;
    }
};