条件

题目链接：nowcoder 213813

到主站看：https://blog.csdn.net/weixin_43346722/article/details/112742917

题目大意

在一个图中，有一些边一定存在，有一些边可能存在。
有一些询问，问你两个点之间是否一定有路径，是否可能有路径。

思路

这道题很明显可以看到，问你一定有路径，就是可能存在的路径都不存在，看看能否连通。而问你可能有路径，就是肯能存在的路径都存在，看看能否连通。

但是可以发现可能存在的边很多，而且还是有向图。不可以用并查集来做，用别的跑图又会因为边太大而超时。

由于没有边权，只是判断是否连通，那我们可以用 bitset 来做。
其实就是 Floyed 算法，我们枚举中间的点 和起点 ，本来要枚举到哪里 的，但是因为我们只是求是否连通，而且我们有 bitset，我们就可以直接 a[i] |= a[k]。（当然你要先保证 可以到 ）

那我们就把一定的图和可能的图都跑一遍，然后就按题目要求输出即可。

代码

#include<queue>
#include<cstdio>
#include<bitset>

using namespace std;

int n, m1, m2, q, x, y;
bool cant[1001][1001];
bitset <1001> a[2][1001];

int main() {
    scanf("%d %d %d %d", &n, &m1, &m2, &q);

    for (int i = 1; i <= n; i++) a[0][i][i] = 1;

    for (int i = 1; i <= m1; i++) {
        scanf("%d %d", &x, &y);
        a[0][x][y] = 1;
    }

    for (int j = 1; j <= m2; j++) {
        scanf("%d %d", &x, &y);
        cant[x][y] = 1;
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (!cant[i][j]) {
                a[1][i][j] = 1;
            }

    //通过bitset得出两点之间是否连通（Floyed的思路）
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (a[0][j][i]) a[0][j] |= a[0][i];
            if (a[1][j][i]) a[1][j] |= a[1][i];
        }

    for (int i = 1; i <= q; i++) {
        scanf("%d %d", &x, &y);

        if (a[0][x][y]) printf("Yes ");
            else printf("No ");
        if (a[1][x][y]) printf("Yes\n");
            else printf("No\n");
    }

    return 0;
}