求条
查看原帖
求条
743014
_H17_楼主2025/7/2 20:28
#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e5+1;
int n,m,q,tot,root,fa[N],siz[N];
pair<int,int>edge[N<<1];
vector<int>erased[N<<1],ans;
struct SegmentTreeNode{
	int l,r,ls,rs;
	vector<int>edge;
	SegmentTreeNode(int l=0,int r=0):l(l),r(r),ls(0),rs(0),edge(vector<int>(0)){}
}f[N<<1];
stack<tuple<int,int,int> >st;
void build(int l,int r,int&cur){
	f[cur=(++tot)]=SegmentTreeNode(l,r);
	if(l==r)
		return;
	int mid=(l+r)>>1;
	build(l,mid,f[cur].ls),build(mid+1,r,f[cur].rs);
	return;
}
void modify(int l,int r,int id,int cur){
	if(l<=f[cur].l&&f[cur].r<=r){
		f[cur].edge.push_back(id);
		return;
	}
	int mid=(f[cur].l+f[cur].r)>>1;
	if(l<=mid)
		modify(l,r,id,f[cur].ls);
	if(mid<r)
		modify(l,r,id,f[cur].rs);
	return;
}
int findfa(int x){
	while(fa[x]!=x)
		x=fa[x];
	return x;
}
void merge(int x,int y){
	x=findfa(x),y=findfa(y);
	if(x==y)
		st.push(make_tuple(0,0,0));
	if(siz[x]<siz[y])
		swap(x,y);
	fa[y]=x,siz[x]+=siz[y];
	st.push(make_tuple(x,y,siz[y]));
}
void back(){
	int x=get<0>(st.top()),y=get<1>(st.top()),val=get<2>(st.top());
	if(!x&&!y&&!val){
		st.pop();
		return;
	}
	fa[y]=y,siz[x]-=val;
	st.pop();
	return;
}
void add_edge(int i){
	merge(edge[i].first,edge[i].second);
	return;
}
void dfs(int cur){
	for(auto p:f[cur].edge)
		add_edge(p);
	if(f[cur].l==f[cur].r){
		ans.push_back(siz[findfa(1)]==n);
		for(int i=1;i<=f[cur].edge.size();i++)
			back();
		return;
	}
	if(f[cur].ls)
		dfs(f[cur].ls);
	if(f[cur].rs)
		dfs(f[cur].rs);
	for(int i=1;i<=f[cur].edge.size();i++)
		back();
	return;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cin>>n>>m;
	for(int i=0;i<N;i++)
		fa[i]=i,siz[i]=1;
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		edge[i]=make_pair(u,v);
	}
	cin>>q;
	build(1,q,root);
	for(int i=1,siz;i<=q;i++){
		cin>>siz;
		for(int id;siz;--siz){
			cin>>id;
			erased[id].push_back(i);
		}
	}
	for(int i=1;i<=m;i++){
		for(int lst=1,j=0;j<=erased[i].size();j++){
			if(j==erased[i].size()){
				if(lst<=q)
					modify(lst,q,i,root);
				break;
			}
			if(lst<erased[i][j])
				modify(lst,erased[i][j]-1,i,root);
			lst=max(lst,erased[i][j]+1);
		}
	}
	dfs(root);
	for(auto p:ans){
		if(p)
			cout<<"Connected\n";
		else
			cout<<"Disconnected\n";
	}
	return 0;
}
2025/7/2 20:28
加载中...