BZOJ 3569: DZY Loves Chinese II [高斯消元XOR 神题]

时间：2021-08-22 02:45:54

http://www.lydsy.com/JudgeOnline/problem.php?id=3569

题意：多次询问一个无向连通图当图中某k条边消失时这个图是否联通 强制在线

太神啦啦啦啦啦啦啦啦啦拉拉啦啦啦啦

求一棵生成树，给所有的非树边随机分配一个权值，树边的权值为所有覆盖它的非树边的权值的异或和

这样做之后，去掉k条边后原图不连通，当且仅当k条边的一个子集权值异或和为0

只有树边和覆盖它的非树边都消失了或者根本没有非树边才会造成非联通

因为权值是随机的，冲突的可能性很小....

求线性基就好了

如何计算树边的权值？

首先一个点异或上所有与他相连的非树边，然后一条树边u--->v的权值就是v子树点值异或和

注意：

1.分配非树边要记录$fa$因为有可能把与$fa$相连的边给分配了

2.我一直纠结于邻接表边从$1$开始编号然后正向边和反向边$>>1$结果不同，然后发现只要邻接表从$2$开始就好了

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <bitset>

using namespace std;

typedef long long ll;

const int N=1e5+,M=5e5+,INF=1e9;

inline int read(){

    char c=getchar();int x=;

    while(c<''||c>''){c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x;

}

int n,m,u,v,Q,cntans;

int a[],p,bin[];

void ini(){

    for(int i=;i<=;i++) bin[i]=<<i;

}

struct edge{

    int v,ne;

}e[M<<];

int h[N],cnt=;//magic

inline void ins(int u,int v){

    cnt++;

    e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;

    cnt++;

    e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;

}

bool vis[N];

int w[M],d[N];

void dfs(int u,int fa){

    vis[u]=;

    for(int i=h[u];i;i=e[i].ne){

        int v=e[i].v;

        if(v==fa) continue;

        if(!vis[v]) dfs(v,u);

        else if(!w[i>>]){

            w[i>>]=rand();

            d[u]^=w[i>>];

            d[v]^=w[i>>];

        }

    }

}

void dfs2(int u){

    vis[u]=;

    for(int i=h[u];i;i=e[i].ne){

        int v=e[i].v;

        if(vis[v]) continue;

        dfs2(v);

        d[u]^=d[v];

        w[i>>]=d[v];

    }

}

int now;

void Gauss(int n){

    now=;

    for(int i=;i>=;i--){

        int j=now;

        while(j<=n&&!(a[j]&bin[i])) j++;

        if(j==n+) continue;

        if(j!=now) swap(a[now],a[j]);

        for(int k=;k<=n;k++)

            if(k!=now&&(a[k]&bin[i])) a[k]^=a[now];

        now++;

    }

    now--;

}

int main(){

    freopen("in","r",stdin);

    srand();

    ini();

    n=read();m=read();

    for(int i=;i<=m;i++) u=read(),v=read(),ins(u,v);

    dfs(,);

    //for(int i=1;i<=m;i++) printf("w %d %d\n",i,w[i]);

    memset(vis,,sizeof(vis));

    dfs2();

    //for(int i=1;i<=m;i++) printf("w %d %d\n",i,w[i]);

    Q=read();

    while(Q--){

        int k=read();p=;int x;

        while(k--) x=read(),a[++p]=w[x^cntans];//,printf("x %d %d %d\n",x,cntans,x^cntans);

        //for(int i=1;i<=p;i++) printf("a %d %d\n",i,a[i]);

        Gauss(p);

        //printf("now %d %d\n",now,p);

        if(now<p) puts("Disconnected");

        else cntans++,puts("Connected");

    }

}

相关文章