1203. 项目管理

发表于 分类于 ， 阅读次数： 本文字数： 73 阅读时长 ≈ 1 分钟

双重拓扑排序: 组内 & 组间

拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> topSort(vector<int>& deg, vector<vector<int>>& graph, vector<int>& items) {
    queue<int> Q;
    for (auto& item: items) {
        if (deg[item] == 0) {
            Q.push(item);
        }
    }
    vector<int> res;
    while (!Q.empty()) {
        int u = Q.front(); 
        Q.pop();
        res.emplace_back(u);
        for (auto& v: graph[u]) {
            if (--deg[v] == 0) {
                Q.push(v);
            }
        }
    }
    return res.size() == items.size() ? res : vector<int>{};
}

官方题解