题解：P5191 [COCI 2009/2010 #6] HOLMES

Left_i_Forever · 2025-08-19 16:25:12 · 题解

模拟赛时看第三个样例（和本题一样）想到的，比较神秘……

从一个点往回走走到头，可能会有很多个结束的点。反过来，这些点都是拓扑的起点（入度为 0），并且都能走到这个点。例如第三个样例中的点都会走到 1 这个点。

令第 i 个点往回走到的终点的集合为 s_i，那么 s_i 中必然有至少一个点是发生了的。由于没有其他条件，所以我们无法确定具体是谁发生了，但是可以推理。

对于每一个发生了的 i，枚举所有 j，若 s_i 是 s_j 的子集，那么 j 一定发生了。注意到只有 10^3 个点，所以 \Omicron(n^2) 是可以接受的。

预处理 s 可以在拓扑排序的时候使用 bitset 优化 DP。

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
bitset <N> b[N];
vector <int> v[N], v2[N];
int in[N];
int n, m, d;
bool ans[N];

void topsort()
{
    queue <int> q;
    for (int i = 1; i <= n; i++)
        if (!in[i]) b[i][i] = true, q.push (i);
    while (q.size ())
    {
        int u = q.front ();
        q.pop ();
        for (int j : v[u])
        {
            in[j]--;
            if (!in[j]) q.push (j);
            b[j] |= b[u];
        }
    }
}

int main()
{
//  freopen ("detect.in", "r", stdin);
//  freopen ("detect.out", "w", stdout);
    cin >> n >> m >> d;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        v[x].push_back (y);
        v2[y].push_back (x);
        in[y]++;
    }
    topsort ();
    for (int i = 1; i <= d; i++)
    {
        int x;
        cin >> x;
        for (int j = 1; j <= n; j++)
        {
            bitset <N> tep = b[x] & b[j];
            if (tep == b[x]) ans[j] = true;
        }
    }
    for (int i = 1; i <= n; i++)
        if (ans[i]) cout << i << " ";
    puts ("");
    return 0;
}