题解：P10778 BZOJ3569 DZY Loves Chinese II

· · 题解

先考虑建出 DFS 生成树，考虑这棵树何时不连通，只有在一条树边和所有经过它的非树边都被删除的情况下，树才不连通，由于需要判断抵消的情况，考虑异或哈希，给每条非树边赋一个随机权值，每条树边的权值定义为所有经过它的非树边的异或和，权值可以用树上差分维护，由于异或的性质，把每一条树边和所有所有经过它的非树边的权值异或起来，一定为 0，问题转化为在边集中判断是否有异或和为 0 的子集，线性基即可。

#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 5e5 + 5;
vector<pair<int, int> > v[kMaxN];
int a[kMaxN];  // 边权
int p[kMaxN];
int b[kMaxN];  // 是否访问
int e[kMaxN];
int siz = 0;
mt19937 rnd(27426169);
void dfs(int x, int y, int z) {
  b[x] = ++siz;
  for (int i = 0; i < v[x].size(); i++) {
    if (v[x][i].first != y) {
      if (b[v[x][i].first] == 0) {
        dfs(v[x][i].first, x, v[x][i].second);
      } else {
        if (b[v[x][i].first] < b[x]) {
          a[v[x][i].second] = abs((int)rnd());
        }
      }
      a[z] ^= a[v[x][i].second];
    }
  }
}
int w[31];
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int x, y, z = i;
    cin >> x >> y;
    v[x].push_back(make_pair(y, i));
    v[y].push_back(make_pair(x, i));
  }
  dfs(1, 0, 0);
  int sum = 0;
  int q;
  cin >> q;
  while (q--) {
    int k;
    cin >> k;
    bool bb = 1;
    fill(p, p + 32, 0);
    for (int i = 1; i <= k; i++) {
      cin >> e[i];
      e[i] ^= sum;
      e[i] = a[e[i]];
      bool b = 0;
      for (int j = 31; j >= 0; j--) {
        if ((e[i] & (1 << j)) != 0) {
          if (p[j] == 0) {
            p[j] = e[i];
            b = 1;
            break;
          }
          e[i] ^= p[j];
        }
      }
      if (b == 0) bb = 0;
    }
    sum += bb;
    cout << (bb ? "Connected" : "Disconnected") << '\n';
  }
  return 0;
}