「解题记录」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;
}