BZOJ 3569 DZY Loves Chinese II

发表于 | 分类于

Description

有一个\(n\)个点\(m\)条边的简单无向联通图，\(q\)组询问。每组询问给定一个\(k\)，再给\(k\)条边，输出假设这\(k\)条边不存在，那么图是否联通（询问互相独立）。并且强制在线。

\(n\leq 10^5, m\leq 5\times 10^5, q\leq 5\times 10^4, k\leq 15\)。

Solution

好像做了整整五个月罢……真的事大脑满级人罢，，，

考虑构造随便构造一个DFS树，然后给所有非树边随出来一个权值，树边的权值定义为覆盖它的所有非树边权的异或和。然后我们发现如果给定\(k\)条边可以凑出来一个子集使得其异或和为\(0\)，那么就事不联通的。

至于如何判断是否有异或和为\(0\)的子集。注意到如果把二进制数搞成一个向量，那么这个条件等价于这些向量线性相关。线性相关的话就等价于线性基数小于总数，所以用线性基判一下。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <climits>
#include <utility>
#include <cmath>
#include <algorithm>
#include <vector>
#include <tr1/random>
const int maxn = 100005;
const int maxm = 1000005;
int first[maxn];
int next[maxm], to[maxm], rev[maxm];
int gcnt = 0;
int add_edge(int u, int v) {
  gcnt ++;
  next[gcnt] = first[u];
  first[u] = gcnt;
  to[gcnt] = v;
  return gcnt;
}
void ins_edge(int u, int v) {
  int e1 = add_edge(u, v);
  int e2 = add_edge(v, u);
  rev[e1] = e2; rev[e2] = e1;
}
 
typedef unsigned long long ull;
ull xs[maxm], d[maxm];
bool vis[maxn], used[maxm];
bool no_tree[maxm];
int anc[maxn][18], dep[maxn];
typedef std::pair<int, int> pii;
#define mp std::make_pair
std::vector<pii> V;

std::tr1::mt19937 gen;
inline ull rand64() {
  static std::tr1::uniform_int<ull> dist(0, (1ULL << 41) - 1ULL);
  return gen();
}

void dfs_1(int x, int fa = -1) {
  vis[x] = true;
  anc[x][0] = fa;
  for(int i = first[x]; i; i = next[i]) {
    if(used[i]) continue;
    used[i] = used[rev[i]] = true;
    int v = to[i];
    if(vis[v]) {
      xs[rev[i]] = rand64();
      xs[i] = xs[rev[i]];
      V.push_back(mp(x, i));
    } else {
      dep[v] = dep[x] + 1;
      dfs_1(v, x);
    }
  }
}
int n, m;
void process_1() {
  gen.seed(192608);
  dfs_1(1);
  for(int i = 0; i < V.size(); i ++) {
    int u = V[i].first, id = V[i].second;
    int v = to[id];
    d[u] ^= xs[id]; d[v] ^= xs[id];
  }
  memset(vis, 0, sizeof(vis));
}
void dfs_2(int x) {
  vis[x] = true;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v]) {
      dfs_2(v);
      d[x] ^= d[v];
      xs[i] = xs[rev[i]] = d[v];
    }
  }
}
 
const int bs = 32;
ull A[bs];
int insert(ull x) {
  for(int i = bs - 1; i >= 0; i --) {
    if(!x) break;
    if(!((1ULL << i) & x)) continue;
    if(A[i]) {
      x ^= A[i];
    } else {
      for(int j = i - 1; j >= 0; j --) if((1ULL << j) & x) x ^= A[j];
      for(int j = i + 1; j < bs; j ++) if((1ULL << i) & A[j]) A[j] ^= x;
      A[i] = x; return i; 
    }
  }
  return 0;
}
 
void getint(int &x) {
  char c = getchar();
  x = 0;
  while(!isdigit(c)) c = getchar();
  while(isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
}
int main() {
  getint(n); getint(m);
  V.resize(m);
  for(int i = 1; i <= m; i ++) {
    int u, v; getint(u); getint(v);
    ins_edge(u, v);
  }
  process_1(); dfs_2(1);
  int q; int tot = 0;
  getint(q); if(q <= 0) return 0;
  while(q --) {
    memset(A, 0, sizeof(A));
    int cnt = 0;
    int k; getint(k);
    int rec[20];
    for(int i = 1; i <= k; i ++) {
      int c; getint(c);
      c ^= tot;
      rec[i] = insert(xs[c * 2 - 1]);
      if(rec[i]) cnt ++;
    }
    if(cnt == k) {
      tot ++;
      puts("Connected");
    } else {
      puts("Disconnected");
    }
  }
  return 0;
}