【BZOJ3237】[AHOI2013] 连通图（线性基）

点此看题面

大致题意： 给定一个无向图，每次删去其中若干条边，询问连通性。（询问独立）

双倍经验

题解可见此题强制在线版本：【BZOJ3569】DZY Loves Chinese II。

这里就直接放代码了。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define M 200000
#define add(p,x,y) (e[++ee].id=p,e[ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
#define ull unsigned long long
using namespace std;
int n,m,ee,lnk[N+5],f[N+5];struct edge {int id,to,nxt;}e[2*N+5];
struct line {int x,y;ull v;}s[M+5];
class FastIO
{
	private:
		#define FS 100000
		#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
		#define D isdigit(c=tc())
		char c,*A,*B,FI[FS];
	public:
		I FastIO() {A=B=FI;}
		Tp I void read(Ty& x) {x=0;W(!D);W(x=(x<<3)+(x<<1)+(c&15),D);}
		Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
}F;
class LinearBasis//线性基
{
	private:
		int fg;ull v[65];
	public:
		I void Clear() {fg=0;for(RI i=64;~i;--i) v[i]=0;}
		I void Ins(ull x)
		{
			for(RI i=64;~i;--i) if((x>>i)&1)
				{if(!v[i]) return (void)(v[i]=x);x^=v[i];}fg=1;//fg记录是否有0
		}
		I int Qry() {return fg;}
}B;
ull v[N+5];I void dfs(CI x,CI lst=0)//遍历树
{
	for(RI i=lnk[x];i;i=e[i].nxt) e[i].to^lst&&
		(dfs(e[i].to,x),v[x]^=(s[e[i].id].v=v[e[i].to]));//统计子树权值异或和
}
I int fa(CI x) {return f[x]?f[x]=fa(f[x]):x;}//并查集
int main()
{
	RI i,x,y;for(F.read(n,m),i=1;i<=m;++i) F.read(s[i].x,s[i].y),
		(x=fa(s[i].x))^(y=fa(s[i].y))?(f[y]=x,add(i,s[i].x,s[i].y),add(i,s[i].y,s[i].x))//树边连边
		:(v[s[i].x]^=(s[i].v=1ull*rand()*rand()*rand()*rand()*rand()),v[s[i].y]^=s[i].v);//非树边随机权值，修改点权
	RI Qt,k;dfs(1),F.read(Qt);W(Qt--)
	{
		for(B.Clear(),F.read(k),i=1;i<=k;++i) F.read(x),B.Ins(s[x].v);//插入线性基
		puts(B.Qry()?"Disconnected":"Connected");//判断输出
	}return 0;
}