BZOJ 3569: DZY Loves Chinese II

链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3569

很经典的一个题
今天被问到，发现不是很会。。
我真是太菜了

首先，套路地，我们应当先建立dfs树
然后考虑有什么情况图会变得不连通
1.有两条树边，覆盖他们的非树边一样，但是这两条树边都被割掉了
2.存在一个点，他和父亲的树边被割掉，并且从他子树中所有可以返到他祖仙的边都被割掉了

考虑怎么来做这个问题

我们可以对于每一个非树边随机一个权值
然后让树边为所有经过他的权值的异或和
那么对于第一种情况，我们发现，如果两条树边覆盖的值是一样的，那么他们的值也是一样的，因此两条边的异或和为0
对于第二种情况，我们可以发现，断掉的边和树边的权值异或和也是0
统一一下，就是可以找出一个非空边集使得他们异或为0

线性基即可

随机的话冲突的概率还是很小的（雾

CODE:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;
const int M=500005;
const int N=500005;
int n,m;
struct qq
{
    int x,y,last;
}e[M*2];int num,last[N];
void init (int x,int y)
{
    num++;e[num].x=x;e[num].y=y;e[num].last=last[x];last[x]=num;
}
bool vis[N];
int a[N],b[N];//这条边的权值 这个点的权值 
void dfs1 (int x)
{
    vis[x]=true;for (int u=last[x];u!=-1;u=e[u].last){
    int y=e[u].y;if (vis[y]==false)  dfs1(y);else{
    a[u]=rand();b[x]^=a[u];b[y]^=a[u];}}
}
void dfs2 (int x)
{
    vis[x]=true;for (int u=last[x];u!=-1;u=e[u].last){
    int y=e[u].y;if (vis[y]==false)  {
    dfs2(y);a[u]^=b[y];b[x]^=b[y];}}
}
int k;
int p[33];
int c[N];
bool ins (int x)
{
    for (int u=30;u>=1;u--){
    if ((x>>u)&1){
    if (p[u]==-1){
    p[u]=x;return true;}x^=p[u];}}return false;
}
bool check ()
{
    memset(p,-1,sizeof(p));for (int u=1;u<=k;u++)if (ins(c[u])==false)return true;return false;
}
int main()
{
    srand(200815147);num=0;memset(last,-1,sizeof(last));scanf("%d%d",&n,&m);for (int  u=1;u<=m;u++){
    int x,y;scanf("%d%d",&x,&y);if (x>y) swap(x,y);  init(x,y);  }memset(vis,false,sizeof(vis));dfs1(1);memset(vis,false,sizeof(vis));dfs2(1);int q;scanf("%d",&q);int ans=0;while (q--){
    scanf("%d",&k);for (int u=1;u<=k;u++){
    int x;scanf("%d",&x);x^=ans;c[u]=a[x];}if (check()) printf("Disconnected\n");else {
    ans++;printf("Connected\n");}}return 0;
}
?