「解题记录」AtCoder Beginner Contest 304 E – Good Graph

题目传送门

题目简述

给定一张无向图和数列 X, Y。

有 K 次询问，每次询问需要判断在询问的 u, v 之间建边之后，判断「对于所有 X_i 和 Y_i 之间都不存在路径」是否成立。

保证原图不存在 X_i, Y_i 之间有路径。

思路分析

容易发现，在同一个连通块中的所有点都存在相互可达的路径。如果新加入的边连接了两个连通块，那么这两个连通块之间的所有点就都存在路径相互可达。

因此，对于每一对 X_i, Y_i，只需判断「新加入的边是否连通了这两个点所在的连通块」。

可以用 map 来实现。

Code:

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int u, v;
int n, m, k;
int q;

vector<int> G[200005];

// ltk = 连通块id
int ltcnt = 0, ltk[200005];
int ys_x[200005], ys_y[200005];

map<pair<int, int>, int> mp;

void dfs(int x)
{
    ltk[x] = ltcnt;
    for (auto y : G[x]) {
        if (!ltk[y]) dfs(y);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        if (!ltk[i]) ltcnt++, dfs(i);
    }
    scanf("%d", &k);
    for (int i = 1; i <= k; i++) {
        scanf("%d%d", &u, &v);
        // 这里类似双向建边
        mp[{ltk[u], ltk[v]}] = 1;
        mp[{ltk[v], ltk[u]}] = 1;
    }
    scanf("%d", &q);
    while (q--) {
        scanf("%d%d", &u, &v);
        if (mp.find({ltk[u], ltk[v]}) == mp.end()) {
            puts("Yes");
        } else {
            puts("No");
        }
    }
    return 0;
}