自动搬运

查看原文

来自洛谷，原作者为

	251Sec 祈祷着今后的你的人生，永远都有幸福的“魔法”相伴。

搬运于2025-08-24 23:01:06，当前版本为作者最后更新于2024-07-13 20:20:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

你可以在 P10075 的题解区或者 ix35 的集训队论文看到本题的正常做法。但是作为经过 SCOI D2T2 洗礼的成熟 OIer，我们要学会直接从输入里搞到答案。

注意到每行输入的第一个数是本行接下来输入的数的个数异或上一问的答案，而我们实际上知道本行接下来输入的数的个数，所以我们可以直接由此推出上一问的答案。因此除了最后一组询问以外，所有询问的答案都是可以由下一个询问的输入直接推出的。最后一组询问直接暴力即可。

代码写的有点丑。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, q;
struct Edge {
	int u, v;
} e[500005];
char s[100005];
int k, p[18], pC;
int fa[100005], las;
int F(int u) { return fa[u] == u ? u : fa[u] = F(fa[u]); }
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &e[i].u, &e[i].v);
	}
	scanf("%d", &q);
	cin.ignore();
	for (int i = 1; i <= q; i++) {
		cin.getline(s, 100000);
		stringstream ss(s);
		ss >> k;
		pC = 1;
		while (ss >> p[pC]) {
			pC++;
		}
		pC--;
		int x = k ^ pC;
		for (int j = 1; j <= pC; j++) p[j] ^= x;
		if (i > 1) {
			puts(x == las ? "Disconnected" : "Connected");
			las = x;
		}
	}
	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1; i <= m; i++) {
		bool flg = true;
		for (int j = 1; j <= pC; j++) if (i == p[j]) flg = false;
		if (flg) fa[F(e[i].u)] = F(e[i].v);
	}
	for (int i = 1; i <= m; i++) if (F(i) != F(1)) return puts("Disconnected"), 0;
	puts("Connected");
	return 0;
}