[BZOJ]3569 线性基+随机化

kgxw0430 2019-02-24 原文

果然我还是菜鸡

看完题目之后，？？？（这尼玛你告诉我这是线性基？图的连通性和线性基有屁关系啊我呸）
（after reading solution）哦原来是线性基判断连通性啊，对的对的，线性基通过某种操作是可以判断连通性的。
这是道比较玄学、有意思、nb的题啊（词穷莫怪），为何它可以用线性基来写呢？因为你发现k很小。
具体原理来说一下吧。删除若干条边，怎样可以使图不连通？一种情况是这些边里面有割边，一种情况是环上的边同时被删除掉。考虑怎样判断哪些边构成了一个环。我们把边分为树边和非树边，每一条非树边我们随机一个数，然后对于树边，让它异或上所有覆盖到它的非树边。这样的话，形成一个环的边异或之后应该为0。
具体我们怎样把环上的那条树边路径快速异或上值呢？画图发现无向图dfs树上只有返祖边，显然我们可以做树上差分。（zbl当时没想到差分）。当我们找到一条非树边的时候，把它的权值分别用a【x】和a【y】异或，然后下次dfs的时候传递一下就好了。
当询问的时候，只需要做一次线性基，如果存在插不进线性基的情况，那么说明图已经不连通了。

Coding

#include<bits/stdc++.h>
using namespace std;
const int M=1e6+10;
const int N=1e5+10;
const int inf=2333333333;
int n,m,q,tot,ver[M],Next[M],lin[N],a[N],b[M],v[N],c[50];bool flag;
void add(int x,int y){ver[++tot]=y;Next[tot]=lin[x];lin[x]=tot;}
void dfs1(int x){
    v[x]=1;
    for(int i=lin[x];i;i=Next[i]){
        int y=ver[i];
        if(!v[y]){
            dfs1(y);
        }else{
            b[i]=rand()%inf;
            a[x]^=b[i];
            a[y]^=b[i];
        }
    }
}
void dfs2(int x){
    v[x]=1;
    for(int i=lin[x];i;i=Next[i]){
        int y=ver[i];
        if(v[y]) continue;
        dfs2(y);
        b[i]^=a[y];
        a[x]^=a[y];
    }
}
void insert(int v){
    for(int i=30;i>=0;--i) if((v>>i)&1){
        if(c[i]) v^=c[i];
        else{
            for(int j=i-1;j>=0;--j)
                if((v>>j)&1) v^=c[j];
            for(int j=i+1;j<=30;++j)
                if((c[j]>>i)&1) c[j]^=v;
            c[i]=v;
            break;
        }
    }
    if(!v) flag=1;
}
int main(){
    srand(time(0));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int x,y;scanf("%d%d",&x,&y);
        add(min(x,y),max(x,y));
    }
    dfs1(1);memset(v,0,sizeof(v));
    dfs2(1);
    scanf("%d",&q);
    int ans=0,k;
    while(q--){
        memset(c,0,sizeof(c));
        flag=0;
        scanf("%d",&k);int x;
        for(int i=1;i<=k;++i){
            scanf("%d",&x);x^=ans;
            insert(b[x]);
        }
        if(flag){
            printf("Disconnected\n");
        }else printf("Connected\n");
        ans+=(!flag);
    }
    return 0;
}