题目概述

给出 $n$ 个点 $m$ 条无向边，有 $Q$ 个询问每次删除 $k_i$ 条边（之后还原），问图是否连通。

解题报告

先特判掉没删边就不连通，然后我们建出一棵DFS树，那么图不连通说明一条边以及跨越这条边的非树边全都被删除了。这怎么处理？我们可以给每条非树边随机一个权值，每条树边的权值为跨越的非树边权值的异或和。然后只需要判断删除的边中是否能够异或出 $0$ ，用线性基解决。

示例程序

#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
using namespace std;
typedef unsigned long long ULL;
const int maxn=100000,maxm=500000,maxk=15,Log=64;

int n,m,te,a[maxk+5];ULL sum[maxn+5],ha[maxm+5],M[Log+5];bool con,vis[maxn+5],us[maxm+5];
int E,lnk[maxn+5],nxt[(maxm<<1)+5],son[(maxm<<1)+5],w[(maxm<<1)+5];int lst;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
#define Add(x,y,z) (son[E]=(y),w[E]=(z),nxt[E]=lnk[x],lnk[x]=E++)
#define Rand() (((ULL)rand()<<48)+((ULL)rand()<<32)+((ULL)rand()<<16)+rand())
void Dfs(int x){
    for (int j=lnk[x];~j;j=nxt[j])
        if (!us[j>>1]) if (us[j>>1]=true,!vis[son[j]]) vis[son[j]]=true,Dfs(son[j]);
            else if (us[j>>1]=true,vis[son[j]]) ha[w[j]]=Rand(),sum[x]^=ha[w[j]],sum[son[j]]^=ha[w[j]];
}
void Sum(int x){
    for (int j=lnk[x];~j;j=nxt[j])
        if (!vis[son[j]]) vis[son[j]]=true,Sum(son[j]),sum[x]^=(ha[w[j]]=sum[son[j]]);
}
inline bool Insert(ULL x) {for (int j=Log;~j;j--) if (x>>j&1) if (M[j]) x^=M[j]; else return M[j]=x,true;return false;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);readi(m);memset(lnk,255,sizeof(lnk));
    for (int i=1,x,y;i<=m;i++) readi(x),readi(y),Add(x,y,i),Add(y,x,i);
    srand(19260817);vis[1]=true;Dfs(1);memset(vis,0,sizeof(vis));vis[1]=true;Sum(1);
    for (int i=1;i<=n;i++) if (!vis[i]) {con=true;break;}
    for (readi(te);te;te--){
        if (con) {puts("Disconnected");continue;}
        int K;readi(K);for (int i=1;i<=K;i++) readi(a[i]);memset(M,0,sizeof(M));
        for (int i=1;i<=K;i++) if (!Insert(ha[a[i]^lst])) goto END;
        lst++;puts("Connected");continue;END:puts("Disconnected");
    }
    return 0;
}