题目地址：BZOJ：Problem 3563. — DZY Loves Chinese

题目描述

神校XJ之学霸兮，Dzy皇考曰JC。
摄提贞于孟陬兮，惟庚寅Dzy以降。
纷Dzy既有此内美兮，又重之以修能。
遂降临于OI界，欲以神力而凌♂辱众生。

今Dzy有一魞歄图，其上有N座祭坛，又有M条膴蠁边。
时而Dzy狂WA而怒发冲冠，神力外溢，遂有K条膴蠁边灰飞烟灭。
而后俟其日A50题则又令其复原。（可视为立即复原）
然若有祭坛无法相互到达，Dzy之神力便会大减，于是欲知其是否连通。

题意简述

有一个无向图，每次询问删去若干条边，问图是否连通。强制在线（仮）。

输入输出格式

输入格式：
第一行N,M
接下来M行x,y：表示M条膴蠁边，依次编号
接下来一行Q
接下来Q行：
每行第一个数K而后K个编号c1~cK：表示K条边，编号为c1~cK
为了体现在线，K以及c1~cK均需异或之前回答为连通的个数

输出格式：
对于每个询问输出：连通则为‘Connected’，不连通则为‘Disconnected’（不加引号）

输入输出样例

输入样例#1：

5 10
2 1
3 2
4 2
5 1
5 3
4 1
4 3
5 2
3 1
5 4
5
1 1
2 7 0 3
6 0 7 4 6
1 2 7
0 5 0 2 13

输出样例#1：

Connected
Connected
Connected
Connected
Disconnected

说明

N≤100000 M≤500000 Q≤50000 1≤K≤15
数据保证没有重边与自环
Tip：请学会使用搜索引擎

题解

强制在线个鬼！逗比题一个。
K都异或了，反着异或真实的K，不就得到了这个询问之前有多少询问是连通的嘛，然后反着推一遍，就得到了除了最后一个询问以外的其他询问的答案。
最后一个询问就用并查集随便搞一搞就行。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>

#include <algorithm>

inline bool isendl(char c) {
    return c == '\r' || c == '\n';
}

const int MAXN = 500005;

int n, m, q;

int fa[MAXN];

inline int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

struct Edge {
    int u, v;
} edges[MAXN];

int k, qur[MAXN], ans[MAXN];
bool del[MAXN];

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) fa[i] = i;
    for(int i = 1; i <= m; i++) {
        scanf("%d%d", &edges[i].u, &edges[i].v);
    }
    scanf("%d", &q);
    for(int i = 1; i <= q; i++) {
        int cnt = 0;
        scanf("%d", &k);
        while(!isendl(getchar())) {
            scanf("%d", &qur[++cnt]);
        }
        ans[i] = k ^ cnt; k = cnt;
    }
    for(int i = 1; i < q; i++) {
        if(ans[i + 1] - ans[i]) puts("Connected");
        else puts("Disconnected");
    }
    for(int i = 1; i <= k; i++) {
        qur[i] ^= ans[q]; del[qur[i]] = true;
    }
    for(int i = 1; i <= m; i++) {
        if(del[i]) continue;
        int u = edges[i].u, v = edges[i].v, fu = find(u), fv = find(v);
        if(fu == fv) continue;
        fa[fu] = fv;
    }
    int f1 = find(1);
    for(int i = 2; i <= n; i++) {
        if(find(i) != f1) {
            puts("Disconnected");
            return 0;
        }
    }
    puts("Connected");
    return 0;
}