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’

（不加引号）

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≤100000 M≤500000 Q≤50000 1≤K≤15
数据保证没有重边与自环
Tip：请学会使用搜索引擎

Solution

这个随机做法很巧妙啊……

首先我们$DFS$出一棵树，对于非树边赋随机值，树边为所有在树上覆盖它的非树边的异或和。

可以发现，对于给定边集，如果有子集异或和为$0$，那么图就被砍成不连通的了。

因为对于一条树边，如果想砍它让图不连通，就必须砍掉其他所有覆盖它的非树边。

所以每次询问用线性基维护一下就好了。

Code

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 #define N (100009)

 #define M (500009)

 #define MOD (1000000007)

 using namespace std;

 struct Edge{int to,next;}edge[M<<];

 int n,m,q,k,ans,val[M],XOR[N],DFN[N],d[],dfs_num;

 int head[N],num_edge;

 inline int read()

 {

     int x=,w=; char c=getchar();

     while (c<'' || c>'') {if (c=='-') w=-; c=getchar();}

     while (c>='' && c<='') x=x*+c-'', c=getchar();

     return x*w;

 }

 void add(int u,int v)

 {

     edge[++num_edge].to=v;

     edge[num_edge].next=head[u];

     head[u]=num_edge;

 }

 void DFS(int x,int fa)

 {

     DFN[x]=++dfs_num;

     for (int i=head[x]; i; i=edge[i].next)

         if (!DFN[edge[i].to])

         {

             DFS(edge[i].to,x);

             val[(i+)>>]=XOR[edge[i].to];

             XOR[x]^=XOR[edge[i].to];

         }

         else if (DFN[edge[i].to]<DFN[x] && edge[i].to!=fa)

         {

             val[(i+)>>]=rand();

             XOR[x]^=val[(i+)>>];

             XOR[edge[i].to]^=val[(i+)>>];

         }

 }

 int main()

 {

     srand();

     n=read(); m=read();

     for (int i=; i<=m; ++i)

     {

         int u=read(),v=read();

         add(u,v); add(v,u);

     }

     DFS(,);

     q=read();

     while (q--)

     {

         memset(d,,sizeof(d));

         k=read(); int flag=;

         for (int i=; i<=k; ++i)

         {

             int x=val[read()^ans];

             for (int i=; i>=; --i)

                 if (x&(<<i))

                 {

                     if (!d[i]) {d[i]=x; break;}

                     x^=d[i];

                 }

             if (!x) flag=;

         }

         ans+=flag;

         if (flag) puts("Connected");

         else puts("Disconnected");

     }

 }

巴特西