//这两题有蛋区别啊，不就差一个要不要把k异或一下么，没看到还害我re了两发
我错了，套路太深……
异或随机化也算是套路了吧……但是还是没想到
瞎jb做一个生成树，给所有非树边随机一个权值，树边的权值等于覆盖他的非树边的权值的异或和
那么如果有一组边的异或和为0的话，基本就可以判断他们是一个树边和覆盖了这个树边的所有非树边
而出现这种情况就说明变得不连通了
也就是说对于输入的每组边判一下是否线性无关即可
707185547最高！
欢迎大家加上面那个QQ，萌汉子哦
#include<iostream> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #include<cstdlib> #include<cstdio> #include<map> #include<bitset> #include<set> #include<stack> #include<vector> #include<queue> using namespace std; #define MAXN 100010 #define MAXM 500010 #define ull unsigned long long #define eps 1e-8 #define MOD 1000000007 #define INF 1000000000 struct vec{ int to; int fro; int v; }; vec mp[MAXM*2]; int tai[MAXN],cnt; int n,m; int v1[MAXM],v2[MAXM],v[MAXM]; int c[MAXN]; bool te[MAXM]; int fa[MAXN]; bool vis[MAXN]; int pa; ull b[64]; ull RD(){ return (rand()<<15)+rand(); } ull rd(){ return (RD()<<30)+RD(); } inline void be(int x,int y,int z){ mp[++cnt].to=y; mp[cnt].fro=tai[x]; tai[x]=cnt; mp[cnt].v=z; } inline void bde(int x,int y,int z){ be(x,y,z); be(y,x,z); } void pre(int x){ int i,y; vis[x]=1; for(i=tai[x];i;i=mp[i].fro){ y=mp[i].to; if(!vis[y]){ fa[y]=x; te[mp[i].v]=1; pre(y); } } } void dfs(int x){ int i,y; for(i=tai[x];i;i=mp[i].fro){ y=mp[i].to; if(fa[y]==x){ dfs(y); v[mp[i].v]=c[y]; c[x]^=c[y]; } } } void clr(){ memset(b,0,sizeof(b)); } bool ins(ull x){ int i; for(i=63;~i;i--){ if(x&(1ull<<i)){ if(b[i]){ x^=b[i]; }else{ b[i]=x; return 1; } } } return 0; } int main(){ srand(707185547); int i,x,y; scanf("%d%d",&n,&m); for(i=1;i<=m;i++){ scanf("%d%d",&v1[i],&v2[i]); bde(v1[i],v2[i],i); } pre(1); for(i=1;i<=m;i++){ if(!te[i]){ v[i]=rd(); c[v1[i]]^=v[i]; c[v2[i]]^=v[i]; } } dfs(1); scanf("%d",&m); while(m--){ clr(); scanf("%d",&n); bool flag=1; for(i=1;i<=n;i++){ scanf("%d",&x); x^=pa; flag&=ins(v[x]); } pa+=flag; printf(flag?"Connected\n":"Disconnected\n"); } return 0; } /* 5 10 2 1 3 2 4 2 5 1 5 3 4 1 4 3 5 2 3 1 5 4 5 1 1 3 7 0 3 4 0 7 4 6 2 2 7 4 5 0 2 13 */
