P10778 [BZOJ3569] DZY Loves Chinese II 题解

· · 题解

直接做是动态图连通性，不是很好做的。

我们在图上随机找出一棵生成树，对于非树边我们随机一个权值，对于树边我们令它的权值为经过它的非树边的权值的异或和。那么如果输入进的边的权值集合存在一个子集使得异或和为 0，就可以说明有一条树边和经过它的所有非树边都被断开，或者说有若干条非树边它们把贡献都删掉了。即图不连通。

判断是否有子集异或和为 0 是线性基的基本应用，于是做完。时间复杂度为 O(n+m+qk\log 2^{31})

Code：

#include<bits/stdc++.h>
#define within :
#define LJY main
using namespace std;
typedef long long ll;
const int N=5e5+5;
mt19937 rnd(27426169); // LJY
uniform_int_distribution<int>p(1,2e9);
inline int read(){
  char ch=getchar();int x=0;
  while(ch<'0'||ch>'9') ch=getchar();
  while(ch>='0'&&ch<='9')
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
  return x;
}
int n,m;
bool vis[N];
int val[N],f[N];
vector<pair<int,int> >G[N],T[N];
void dfs(int u,int fa){
  vis[u]=1;
  for(auto [v,id] within G[u]){
    if(v==fa) continue;
    if(vis[v]&&!val[id]){
      val[id]=p(rnd);
      // 对于非树边随机权值
      f[v]^=val[id];
      f[u]^=val[id];
      // 差分
    }else if(!vis[v]){
      T[u].emplace_back(v,id);
      dfs(v,u);
    }
  }
}
void dfs2(int u){
  for(auto [v,id] within T[u]){
    dfs2(v);val[id]=f[v];
    f[u]^=f[v];
    // 将树边权值赋为非树边权值的异或和
  }
}
int b[32];
bool insert(int x){
  for(int i=31;i>=0;i--)
    if(x&(1<<i)){
      if(!b[i]){b[i]=x;return 1;}
      x^=b[i];
    }return 0;
}// 用线性基能否插入判断是否存在子集异或和为 0
signed LJY(){
  n=read();m=read();int u,v;
  for(int i=1;i<=m;i++){
    u=read(),v=read();
    G[u].emplace_back(v,i);
    G[v].emplace_back(u,i);
  }dfs(1,0);dfs2(1);int cnt=0;
  int q=read();while(q--){
    int k=read();bool flg=1;memset(b,0,sizeof(b));
    while(k--) flg&=insert(val[(read()^cnt)]);
    cnt+=flg;puts(flg?"Connected":"Disconnected");
  }
  return 0;
}