题目描述
给定一个无向连通图和若干个小集合，每个小集合包含一些边，对于每个集合，你需要确定将集合中的边删掉后改图是否保持联通。集合间的询问相互独立
定义一个图为联通的当且仅当对于任意的两个顶点，都存在一条路径连接它们
输入格式
第一行为两个整数 (n,m)，代表无向图的点数和边数
下面 (m) 行，包含两个整数 (u,v)，代表该边连接点 (u,v)。第 (i + 1) 行的边的编号为 (i)。保证不存在重边和自环
下面一行包含一个整数 (k)，表示集合个数
下面 (k) 行每行描述一个集合，每行的第一个数为集合中边的个数 (c)，后面 (c) 个数代表集合内的边
输出格式
对于每个集合，输出一行代表去掉该集合中的边后图是否联通，如果联通输出 Connected，否则输出 Disconnected
#include<stack>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+5,M=2*N;
inline int read(){
int x=0; char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
return x;
}
struct cnm{
int *x,y,*u,v;
};
stack<cnm>Q;
int fa[N],rnk[N],now;
int get(int x){
while(x^fa[x])x=fa[x];
return x;
}
void merge(int x,int y){
x=get(x),y=get(y);
if(x==y)return;
now--;
if(rnk[x]>rnk[y])swap(x,y);
Q.push((cnm){fa+x,fa[x],rnk+y,rnk[y]});
fa[x]=y; rnk[y]+=(rnk[x]==rnk[y]);
}
void undo(){
*Q.top().x=Q.top().y;
*Q.top().u=Q.top().v;
Q.pop(); now++;
}
int n,m,k;
struct node{
int u,v;
}e[N];
vector<int>can[N];
vector<node>vec[N<<1];
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
void update(int p,int l,int r,int L,int R,node d){
if(L<=l&&r<=R){ vec[p].push_back(d); return; }
if(L<=mid)update(ls,l,mid,L,R,d);
if(R>mid)update(rs,mid+1,r,L,R,d);
}
void query(int p,int l,int r){
for(int i=0;i<vec[p].size();i++)merge(vec[p][i].u,vec[p][i].v);
if(l==r){ now==1?puts("Connected"):puts("Disconnected"); return; }
int sum=Q.size();
query(ls,l,mid);
while(Q.size()>sum)undo();
query(rs,mid+1,r);
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;i++)fa[i]=i; now=n;
for(int i=1;i<=m;i++)e[i].u=read(),e[i].v=read(),can[i].push_back(0);
k=read();
for(int i=1,x,y;i<=k;i++){
x=read();
while(x--){
y=read();
can[y].push_back(i);
}
}
for(int i=1;i<=m;i++)can[i].push_back(k+1);
for(int i=1;i<=m;i++)
for(int j=0;j<can[i].size()-1;j++){
if(can[i][j]+1<=can[i][j+1]-1)
update(1,1,k,can[i][j]+1,can[i][j+1]-1,e[i]);
}
query(1,1,k);
}