Codeforces 909E(拓扑排序)

Codeforces 909E
题意：给你一堆任务，有些要用主处理器处理，有些要用副处理器处理，副处理器可以一次处理很多个任务，一个任务能被执行的条件为前继任务已经被执行过了或者前继任务和自己同时被放进副处理器处理，现在给你这些前继任务的关系和每个任务处理要用的处理器，求副处理器最少运行了几次，保证关系是一张有向无环图 (主处理器与副处理器之间没有任何关系，随意顺序处理)

DAG图就能想到DP和拓扑排序，这题明显可以拓扑排序。先把最外面能被拓扑的一堆0点处理(不一定就一层)，然后再处理里面的能被拓扑的一堆1点，并且使答案加一。以此类推

Codeforces Submission

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
LL n, m, ino[100000 + 5], ei[100000 + 5];
vector<int> G[100000 + 5];
queue<int> q[2];
inline void ins(int x, int y) {
    G[x].push_back(y), ino[y]++;
}
void clean() {
    ms(ino, 0);
}
int solve() {
    clean();
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> ei[i];
    for (int x, y, i = 1; i <= m; i++) cin >> x >> y, ins(y + 1, x + 1);
    for (int i = 1; i <= n; i++) if (!ino[i]) {
        if (ei[i] == 0) q[0].push(i); else q[1].push(i);
    }
    int cur = 0, tot = 0, ans = 0;
    while (tot < n) {
        while (!q[cur].empty()) {
            int u = q[cur].front(); q[cur].pop(); tot++;
            for (int i = 0; i < (int)G[u].size(); i++) {
                int v = G[u][i];
                ino[v]--; 
                if (!ino[v]) {
                    if (ei[v] == cur) q[cur].push(v); else q[cur ^ 1].push(v);
                }
            }
        }
        if (cur == 1) ans++;
        cur ^= 1;
    }
    cout << ans;
    return 0; 
}
int main() {
    solve();
    return 0;
}