P5191

Solution

首先图是一个 DAG，入度为 $0$ 的点就是不可能被别的点影响的点，所以可以跑拓扑排序。用 bitset 来存点集会快一些。

然后发现，对于每个 $s_i$ 都确定的事件就是它们能被到达的点集的或，而一定能发生就是它们的并，以此跑两遍拓扑排序即可维护。

至于判断是不是答案只需要确定它的点集并之后不变就行。

Code

#include <bits/stdc++.h>
using LL = long long;
const LL N = 1000;
vector<LL> g[N + 5];
LL deg[N + 5], x, v[N], a, b;
bitset<N + 5> f[N + 5];
vector<LL> res;

int main() {
    cin >> a >> b >> x;
    for (LL i = 1; i <= b; ++i) {
        LL u, w;
        cin >> u >> w;
        g[u].push_back(w);
        ++deg[w];
    }

    queue<LL> q;
    for (LL i = 1; i <= a; ++i)
        if (deg[i] == 0) q.push(i), f[i][i] = 1;

    while (!q.empty()) {
        LL u = q.front(); q.pop();
        for (auto w : g[u]) {
            --deg[w];
            f[w] |= f[u];
            if (deg[w] == 0) q.push(w);
        }
    }

    queue<LL> q2;
    for (LL i = 1; i <= x; ++i) {
        cin >> v[i];
        v[v[i]] = true;
        q2.push(v[i]);
    }

    while (!q2.empty()) {
        LL u = q2.front(); q2.pop();
        res.push_back(u);
        for (LL i = 1; i <= a; ++i) {
            if (v[i] != 0) continue;
            if ((f[i] & f[u]) == f[u]) {
                v[i] = true;
                q2.push(i);
            }
        }
        v[u] = -1;
    }

    sort(res.begin(), res.end());
    for (auto x : res) cout << x << " ";
    return 0;
}