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"); } }