RT

写的是第一篇题解的做法

#include<bits/stdc++.h>
#include<random>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MAXN=5e5+5,lim=1ll<<30;
ll n,m,q;
ll c,x,y;
struct edge{
	ll u,v,nxt,id;
}e[MAXN];
ll head[MAXN],edge_num;
void add_edge(ll From,ll To,ll e_id){
	edge_num++;
	e[edge_num]=(edge){From,To,head[From],e_id};
	head[From]=edge_num;
	return;
}
ull val[MAXN];
ll dsu[MAXN];
ll Find(ll num){
	return dsu[num]==num?num:dsu[num]=Find(dsu[num]);
}
ull val_p[MAXN];
mt19937 rnd(114514);
void pre(ll now,ll father){
	for(int i=head[now];i;i=e[i].nxt){
		if(e[i].v==father)continue;
		pre(e[i].v,now);
		val_p[now]^=val_p[e[i].v];
		val[e[i].id]=val_p[e[i].v];
	}
	return;
}
ull base[35];
bool insert(ull num){
	ull i=32;
	for(;~i;i--){
		if(!((num>>i)&1))continue;
		if(!base[i]){
			base[i]=num;
			break;
		}
		num^=base[i];
		if(num==0)return 0;
	}
	return 1;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)dsu[i]=i;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		if(Find(x)==Find(y))val_p[x]^=(val[i]=(unsigned long long)rnd()%lim),val_p[y]^=val[i];
		else{
			add_edge(x,y,i);
			add_edge(y,x,i);
			dsu[Find(x)]=Find(y);
		} 
	}
	pre(1,0);
//	for(int i=1;i<=m;i++)cout<<val[i]<<" ";
//	cout<<'\n';
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>c;
		for(int j=0;j<=32;j++)base[j]=0;
		bool fl=1;
		for(int j=1;j<=c;j++){
			cin>>x;
			fl&=insert(val[x]);
		}
		cout<<(fl?"Connected":"Disconnected")<<'\n';
	}
	return 0;
}