bzoj3569 DZY Loves Chinese II

本文主要是介绍bzoj3569 DZY Loves Chinese II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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个编号c1~cK：表示K条边，编号为c1~cK
为了体现在线，c1~cK均需异或之前回答为连通的个数 Output
对于每个询问输出：连通则为‘Connected’，不连通则为‘Disconnected’ （不加引号）

神题。
在dfs树上，给非树边随机权值，树边的权值是所有覆盖它的非树边权值异或和。图不连通，当且仅当某条树边和覆盖它的所有非树边都被切断，当且仅当存在异或和为零的若干权值。求一下线性基就好了。
具体做法，预处理小心不要写成 $O(nm)$ ，非树边首尾打标记再dfs一遍即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int rd()
{int x=0;char c=getchar();while (c<'0'||c>'9') c=getchar();while (c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x;
}
int n,m,fir[100010],ne[1000010],to[1000010],dep[100010],w[500010],f[100010],g[35],a[20];
void add(int num,int u,int v)
{ne[num]=fir[u];fir[u]=num;to[num]=v;
}
void dfs1(int u,int fa)
{int i,v;for (i=fir[u];i;i=ne[i])if (!dep[v=to[i]]){dep[v]=dep[u]+1;dfs1(v,u);}else if (v!=fa&&!w[i>>1]){w[i>>1]=rand();f[u]^=w[i>>1];f[v]^=w[i>>1];}
}
void dfs2(int u,int fa)
{int i,v;for (i=fir[u];i;i=ne[i])if ((v=to[i])!=fa&&!w[i>>1]){dfs2(v,u);w[i>>1]=f[v];f[u]^=f[v];}
}
bool solve(int n)
{int i,j,flag;memset(g,0,sizeof(g));for (i=1;i<=n;i++){flag=0;for (j=30;j>=0;j--)if ((a[i]>>j)&1){if (!g[j]){g[j]=a[i];flag=1;break;}else a[i]^=g[j];}if (!flag) return 0;}return 1;
}
int main()
{int i,u,v,q,cnt=0,num;srand(918);n=rd(),m=rd();for (i=1;i<=m;i++){u=rd(),v=rd();add(i*2,u,v),add(i*2+1,v,u);}dep[1]=1;dfs1(1,0);dfs2(1,0);q=rd();while (q--){num=rd();for (i=1;i<=num;i++)a[i]=w[rd()^cnt];if (solve(num)){cnt++;printf("Connected\n");}else printf("Disconnected\n");}
}