Description：

给定一个连通的无向图和若干边集，判断将集合中的边从图中删去后图还是否连通。

$1\leqslant n\leqslant10^5,1\leqslant m\leqslant2\times 10^5$ ，边集大小 $|S|\leqslant 4$

Solution：

问题非常不好做，正解是神仙分治，先考虑有两个集合怎么做，可以先把不在两个集合中的边加进去，然后把在 $B$ 但不在 $A$ 的边加进去，求出 $A$ 的答案，然后把第二步中加的边删掉，把在 $A$ 但不在 $B$ 的边加进去，就能求出 $B$ 的答案，把这个方法推广到多个集合，可以分治，先把不在任何一个集合中的边加入，然后把在不左区间的集合中在右区间集合中的边加进去，分治左边，然后撤销加这些边，把在左区间集合不在右区间集合的边加进去，分治右边，这样到每个区间加入的边都是不在这个区间中的，于是递归到叶子时就是正好这个集合中的边没有被加入的情况，直接统计答案即可，统计答案可以只枚举这个集合中删掉的边的两个点看是不是还连通，时间复杂度 $O(n\log n\times |S|)$ ，因为此题 $|S|$ 极小所以可以枚举集合暴力标记边。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<vector>

#include<cstring>

using namespace std;

int n,m,q;

#define MAXN 100010

#define MAXM 200010

struct edge

{

	int u,v;

}e[MAXM];

vector<int> g[MAXM];

struct UFS

{

	int f[MAXN],rank[MAXN];

	int s[MAXN << 1],top;

	void init()

	{

		top = 0;

		for(int i = 1;i <= n;++i)

		{

			f[i] = i;rank[i] = 1;

		}

		return;

	}

	int find(int x){return (x == f[x] ? x : find(f[x]));}

	void merge(int x,int y)

	{

		x = find(x);y = find(y);

		if(x == y)return;

		if(rank[x] > rank[y])swap(x,y);

		if(rank[x] == rank[y])

		{

			++rank[y];

			s[++top] = -y;

		}

		f[x] = y;s[++top] = x;

		return;

	}

	void reset(int tp)

	{

		while(top != tp)

		{

			if(s[top] < 0)--rank[-s[top]];

			else f[s[top]] = s[top];

			--top;

		}

		return;

	}

}s;

bool connect(int k)

{

	for(vector<int>::iterator i = g[k].begin();i != g[k].end();++i)

	{

		if(s.find(e[*i].u) != s.find(e[*i].v))return false;

	}

	return true;

}

int tag[MAXM];

void mark(int l,int r,int w)

{

	for(int k = l;k <= r;++k)

		for(vector<int>::iterator i = g[k].begin();i != g[k].end();++i)

			tag[*i] = w;

	return;

}

void add(int l,int r)

{

	for(int k = l;k <= r;++k)

		for(vector<int>::iterator i = g[k].begin();i != g[k].end();++i)

			if(!tag[*i])s.merge(e[*i].v,e[*i].u);

	return;

}

int ans[MAXM];

void solve(int l,int r)

{

	if(l == r)

	{

		ans[l] = connect(l);

		return;

	}

	int top = s.top;

	int mid = ((l + r) >> 1);

	mark(l,mid,1);add(mid + 1,r);mark(l,mid,0);

	solve(l,mid);

	s.reset(top);

	mark(mid + 1,r,1);add(l,mid);mark(mid + 1,r,0);

	solve(mid + 1,r);

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&e[i].u,&e[i].v);

	}

	scanf("%d",&q);

	int x,y;

	for(int i = 1;i <= q;++i)

	{

		scanf("%d",&x);

		for(int j = 1;j <= x;++j)

		{

			scanf("%d",&y);

			g[i].push_back(y);

		}

	}

	s.init();

	mark(1,q,1);

	for(int i = 1;i <= m;++i)

		if(!tag[i])s.merge(e[i].u,e[i].v);

	memset(tag,false,sizeof(tag));

	mark(1,q,0);

	solve(1,q);

	for(int i = 1;i <= q;++i)

	{

		if(ans[i])puts("Connected");

		else puts("Disconnected");

	}

	return 0;

}