Description
神校XJ之学霸兮，Dzy皇考曰JC。
摄提贞于孟陬兮，惟庚寅Dzy以降。
纷Dzy既有此内美兮，又重之以修能。
遂降临于OI界，欲以神力而凌♂辱众生。
今Dzy有一魞歄图，其上有\(N\)座祭坛，又有\(M\)条膴蠁边。
时而Dzy狂WA而怒发冲冠，神力外溢，遂有\(K\)条膴蠁边灰飞烟灭。
而后俟其日A50题则又令其复原。（可视为立即复原）
然若有祭坛无法相互到达，Dzy之神力便会大减，于是欲知其是否连通。
Input
第一行\(N,M\)。
接下来\(M\)行\(x,y\)：表示\(M\)条膴蠁边，依次编号。
接下来一行\(Q\)。
接下来\(Q\)行：
每行第一个数\(K\)，而后\(K\)个编号\(c_{1} \sim c_{K}\)：表示\(K\)条边，编号为\(c_{1} \sim c_{K}\)。
为了体现在线，\(c_{1} \sim c_{K}\)均需异或之前回答为连通的个数
Output
对于每个询问输出：连通则为‘Connected’，不连通则为‘Disconnected’（不加引号）
Sample Input
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
3 7 0 3
4 0 7 4 6
2 2 7
4 5 0 2 13
Sample Output
Connected
Connected
Connected
Connected
Disconnected
HINT
\(N \le 100000,M \le 500000,Q \le 50000,1 \le K \le 15\)
数据保证没有重边与自环
这题有个很屌的做法。对于此图，我们给抽出一颗生成树，给每条非树边都rand一个权值，每条树边的权值为所有覆盖它的权值的异或值。对于删掉的边，我们只要寻找删掉的边中权值是否能异或出\(0\)来，高斯消元即可。
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
#define maxn (100010)
#define maxm (1000010)
int K,n,m,father[maxn],bit[maxn],dep[maxn],ans;
int side[maxn],next[maxm*2],toit[maxm*2],num = 1,up[maxn];
bool exist[maxm],sign; vector <int> ch[maxn];
inline int getint()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void add(int a,int b) { next[++num] = side[a]; side[a] = num; toit[num] = b; }
inline void ins(int a,int b) { add(a,b); add(b,a); }
struct node
{
int u,v,w;
inline void read() { u = getint(),v = getint(); ins(u,v); }
}edge[maxm];
inline int find(int a) { if (father[a] != a) father[a] = find(father[a]); return father[a]; }
inline void dfs(int now,int fa)
{
for (int i = side[now];i;i = next[i])
{
if (toit[i] == fa||!exist[i>>1]) continue;
up[toit[i]] = i,ch[now].push_back(toit[i]),dep[toit[i]] = dep[now]+1,dfs(toit[i],now);
}
}
inline void deal(int a,int b,int w)
{
if (dep[a] < dep[b]) swap(a,b);
while (dep[a] != dep[b])
{
edge[up[a]>>1].w ^= w;
a = toit[up[a]^1];
}
if (a == b) return;
while (a != b)
{
edge[up[a]>>1].w ^= w;
a = toit[up[a]^1];
edge[up[b]>>1].w ^= w;
b = toit[up[b]^1];
}
}
inline void ready()
{
for (int i = 1;i <= n;++i) father[i] = i;
int cnt = 0;
for (int i = 1;i <= m;++i)
{
int r1 = find(edge[i].u),r2 = find(edge[i].v);
if (r1 != r2) ++cnt,father[r1] = r2,exist[i] = true;
if (cnt == n-1) break;
}
dfs(1,0);
for (int i = 1;i <= m;++i) if (!exist[i]) edge[i].w = rand()%(1<<30),deal(edge[i].u,edge[i].v,edge[i].w);
}
inline bool connect()
{
int now = 1;
for (int i = 29;i >= 0&&now <= K;--i)
{
for (int j = now;j <= K;++j)
if (bit[j] & (1<<i))
{
swap(bit[now],bit[j]);
break;
}
if (bit[now]&(1<<i))
{
for (int j = 1;j <= K;++j)
if (j != now&&(bit[j]&(1<<i))) bit[j] ^= bit[now];
++now;
}
}
for (int i = 1;i <= K;++i) if (!bit[i]) return false;
return true;
}
int main()
{
freopen("3569.in","r",stdin);
freopen("3569.out","w",stdout);
srand(19980402);
n = getint(),m = getint();
for (int i = 1;i <= m;++i) edge[i].read();
ready();
int Q = getint();
while (Q--)
{
K = getint();
for (int i = 1;i <= K;++i)
{
int a = getint(); a ^= ans;
bit[i] = edge[a].w;
}
sign = connect();
if (sign) puts("Connected");
else puts("Disconnected");
ans += sign;
}
return 0;
}