【ybt金牌導航6-5-2】【luogu P5227】判連通圖 / 連通圖（CDQ分治）（并查集）

判連通圖 / 連通圖

題目連結：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;
}