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

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cstdio>
 5 #define N (100009)
 6 #define M (500009)
 7 #define MOD (1000000007)
 8 using namespace std;
 9 
10 struct Edge{int to,next;}edge[M<<1];
11 int n,m,q,k,ans,val[M],XOR[N],DFN[N],d[32],dfs_num;
12 int head[N],num_edge;
13 
14 inline int read()
15 {
16     int x=0,w=1; char c=getchar();
17     while (c<'0' || c>'9') {if (c=='-') w=-1; c=getchar();}
18     while (c>='0' && c<='9') x=x*10+c-'0', c=getchar();
19     return x*w;
20 }
21 
22 void add(int u,int v)
23 {
24     edge[++num_edge].to=v;
25     edge[num_edge].next=head[u];
26     head[u]=num_edge;
27 }
28 
29 void DFS(int x,int fa)
30 {
31     DFN[x]=++dfs_num;
32     for (int i=head[x]; i; i=edge[i].next)
33         if (!DFN[edge[i].to])
34         {
35             DFS(edge[i].to,x);
36             val[(i+1)>>1]=XOR[edge[i].to];
37             XOR[x]^=XOR[edge[i].to];
38         }
39         else if (DFN[edge[i].to]<DFN[x] && edge[i].to!=fa)
40         {
41             val[(i+1)>>1]=rand();
42             XOR[x]^=val[(i+1)>>1];
43             XOR[edge[i].to]^=val[(i+1)>>1];
44         }
45 }
46 
47 int main()
48 {
49     srand(20020627);
50     n=read(); m=read();
51     for (int i=1; i<=m; ++i)
52     {
53         int u=read(),v=read();
54         add(u,v); add(v,u);
55     }
56     DFS(1,0);
57     q=read();
58     while (q--)
59     {
60         memset(d,0,sizeof(d));
61         k=read(); int flag=1;
62         for (int i=1; i<=k; ++i)
63         {
64             int x=val[read()^ans];
65             for (int i=30; i>=0; --i)
66                 if (x&(1<<i))
67                 {
68                     if (!d[i]) {d[i]=x; break;}
69                     x^=d[i];
70                 }
71             if (!x) flag=0;
72         }
73         ans+=flag;
74         if (flag) puts("Connected");
75         else puts("Disconnected");
76     }
77 }