判连通图 / 连通图
题目链接:ybt金牌导航6-5-2 / luogu P5227
题目大意
给你一个无向连通图,然后每次询问删掉几条边,问你是否还是连通的。
思路
首先考虑反过来,就是在原来没有边的情况下加上一些边,问图是否会连通。
然后看连通不难想到要用并查集,然后多组询问我们考虑用 CDQ 分治来搞。
首先那肯定是要将所有询问都要加的边给加了嘛。
然后考虑分治,对于一边,我们就把那一边要都要加,而且另一边不是都要加的边给加了,另一边也一样。
然后判断是否连通其实可以这样看,由于你原来的图是连通的,你拆了那几条边,那如果出现了不连通,你拆的边两边的点一定会出现不连通。所以判断方面也可以了。
然后由于 CDQ 分治要撤回操作,所以要支持并查集合并操作的撤销,不过你撤的是后面的连续一段,所以还好,你搞个按秩合并,然后记录一下合并的数据到时还原回去就可以了。
(还原是处理好左边之后要还原再处理右边)
代码
#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, x, y, xx[200001], yy[200001], cnt;
int fa[100001], sz[100001], k, qq[100001][5];
int rm[200001], jn[200001], ty[200001];
bool in[200001], ans[200001];
int find(int now) {
if (fa[now] == now) return now;
return find(fa[now]);
}
void connect(int x, int y) {//按秩合并
int X = find(x), Y = find(y);
if (X != Y) {
if (sz[X] > sz[Y]) swap(x, y), swap(X, Y);
cnt++; rm[cnt] = X; ty[cnt] = Y;
fa[X] = Y;
if (sz[X] == sz[Y]) sz[Y]++, jn[cnt] = 1;
else jn[cnt] = 0;
}
}
void turnb(int tm) {//撤销并查集操作
while (cnt > tm) {
fa[rm[cnt]] = rm[cnt];
sz[ty[cnt]] -= jn[cnt];
cnt--;
}
}
void mk(int x, int y, bool op) {
for (int i = x; i <= y; i++) {
for (int j = 1; j <= qq[i][0]; j++) {
in[qq[i][j]] = op;
}
}
}
void ad(int x, int y) {
for (int i = x; i <= y; i++)
for (int j = 1; j <= qq[i][0]; j++)
if (!in[qq[i][j]]) connect(xx[qq[i][j]], yy[qq[i][j]]);
}
bool ck(int x) {
for (int i = 1; i <= qq[x][0]; i++)
if (find(xx[qq[x][i]]) != find(yy[qq[x][i]])) return 0;
return 1;
}
void work(int l, int r) {
if (l == r) {
ans[l] = ck(l);
return ;
}
int mid = (l + r) >> 1;
int befcnt = cnt;
mk(l, mid, 1); ad(mid + 1, r); mk(l, mid, 0);//处理出 A 没有而且 B 有的
work(l, mid);
turnb(befcnt);
mk(mid + 1, r, 1); ad(l, mid); mk(mid + 1, r, 0);//处理出 A 有而且 B 没有的
work(mid + 1, r);
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d %d", &xx[i], &yy[i]);
}
for (int i = 1; i <= n; i++)
fa[i] = i, sz[i] = 1;
scanf("%d", &k);
for (int i = 1; i <= k; i++) {
scanf("%d", &qq[i][0]);
for (int j = 1; j <= qq[i][0]; j++)
scanf("%d", &qq[i][j]);
}
mk(1, k, 1);//处理出所有都没有的
for (int i = 1; i <= m; i++)
if (!in[i]) connect(xx[i], yy[i]);
mk(1, k, 0); cnt = 0;
work(1, k);
for (int i = 1; i <= k; i++)
if (ans[i]) printf("Connected\n");
else printf("Disconnected\n");
return 0;
}