Input
Output
Sample Input
4 5
1 2
2 3
3 4
4 1
2 4
3
1 5
2 2 3
2 1 2
Sample Output
Connected
Disconnected
Connected
Hint
N<=100000 M<=200000 K<=100000
题目大意 给出一个有n个节点和m条边的图，然后有k个询问，每个询问是删掉一些边，然后判断图是否连通，询问之间互相独立。
连通性问题通常的做法是并查集，然而并查集不支持删边，但是可以撤销上次操作，所以只能考虑把一条一条边加入并查集，为了高效的确定边是否存在，可以用一个时间戳(其实就是确定某条边在询问时是否存在)。因为存在的时间段是连续的，所以呢就用一个线段树，每个点开一个vector，记录恰好存在时间段为当前区间的的边有哪些。
接着开始遍历整棵树，每到一个点就把它存的边一一塞进并查集
1)如果不是叶节点，然后访问左右子树，访问完后O(1)撤销这个点加入的所有边
2)如果是叶节点，就随便找个点的*father(就是f[father] = father)看下它的size是否为n(然后一个操作就"水"完了)
因为并查集要支持撤销，所以不能压缩路径了，只能按秩合并(把小的合并到大的中)。
注意题目输入中的数据范围是错的(然后我就RE了一次)
Code
/**
* bzoj
* Problem#3237
* Accepted
* Time:19508ms
* Memory:72656k
*/
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cmath>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <stack>
#ifndef WIN32
#define Auto "%lld"
#else
#define Auto "%I64d"
#endif
using namespace std;
typedef bool boolean;
const signed int inf = (signed)((1u << ) - );
const signed long long llf = (signed long long)((1ull << ) - );
const double eps = 1e-;
const int binary_limit = ;
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
template<typename T>
inline boolean readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-' && x != -);
if(x == -) {
ungetc(x, stdin);
return false;
}
if(x == '-'){
x = getchar();
aFlag = -;
}
for(u = x - ''; isdigit((x = getchar())); u = (u * ) + x - '');
ungetc(x, stdin);
u *= aFlag;
return true;
} typedef class SegTreeNode {
public:
vector< pair<int, int> > e;
SegTreeNode *l, *r; SegTreeNode() { }
SegTreeNode(SegTreeNode* l, SegTreeNode* r):l(l), r(r) { }
}SegTreeNode; SegTreeNode pool[];
SegTreeNode *top = pool;
SegTreeNode null = SegTreeNode(&null, &null); inline SegTreeNode* newnode() {
*top = SegTreeNode(&null, &null);
return top++;
} typedef class union_found {
public:
int n;
SegTreeNode* root;
int* f;
int* s;
stack< pair<int, int> > trace;
stack< pair<int, int> > ss;
union_found():root(NULL) { }
union_found(int n):root(&null), n(n) {
f = new int[(n + )];
s = new int[(n + )];
fill(s, s + n + , );
for(int i = ; i <= n; i++)
f[i] = i;
} int find(int x) {
return (f[x] == x) ? (x) : (find(f[x]));
} inline void unit(int fa, int so) {
int ffa = find(fa);
int fso = find(so);
if(ffa == fso) trace.push(pair<int, int>(, ));
else {
if(s[ffa] < s[fso])
swap(ffa, fso);
trace.push(pair<int, int>(fso, f[fso]));
ss.push(pair<int, int>(ffa, s[ffa]));
s[ffa] += s[fso];
f[fso] = ffa;
}
} inline void undo() {
pair<int, int> p = trace.top();
pair<int, int> sp = ss.top();
trace.pop();
if(p.first == ) return;
f[p.first] = p.second;
s[sp.first] = sp.second;
ss.pop();
} void update(SegTreeNode*& node, int l, int r, int ql, int qr, pair<int, int> &val) {
if(node == &null) node = newnode();
if(l == ql && r == qr) {
// printf("Update at segment [%d, %d] with the edge (%d, %d)\n", l, r, val.first, val.second);
node->e.push_back(val);
return;
}
int mid = (l + r) >> ;
if(qr <= mid) update(node->l, l, mid, ql, qr, val);
else if(ql > mid) update(node->r, mid + , r, ql, qr, val);
else {
update(node->l, l, mid, ql, mid, val);
update(node->r, mid + , r, mid + , qr, val);
}
} void query(SegTreeNode* node, int l, int r, boolean *res) {
pair<int, int> p;
for(int i = ; i < (signed)node->e.size(); i++) {
p = node->e[i];
unit(p.first, p.second);
// printf("Connect %d and %d\n", p.first, p.second);
}
if(l == r) {
res[l] = (s[find()] == n);
} else {
int mid = (l + r) >> ;
query(node->l, l, mid, res);
query(node->r, mid + , r, res);
}
for(int i = ; i < (signed)node->e.size(); i++)
undo();
}
}union_found; int n, m, q;
pair<int, int> *es;
vector<int> *exists;
union_found uf; inline void init() {
readInteger(n);
readInteger(m);
es = new pair<int, int>[(m + )];
for(int i = ; i <= m; i++) {
readInteger(es[i].first);
readInteger(es[i].second);
}
exists = new vector<int>[(m + )];
readInteger(q);
for(int i = , c, x; i <= q; i++) {
readInteger(c);
while(c--) {
readInteger(x);
exists[x].push_back(i);
}
}
} inline void mktree() {
uf = union_found(n);
for(int i = ; i <= m; i++) {
exists[i].push_back(q + );
for(int j = , last = ; j < (signed)exists[i].size(); j++) {
if(last == exists[i][j])
last++;
else {
// cout << exists[i][j] << endl;
uf.update(uf.root, , q, last, exists[i][j] - , es[i]);
last = exists[i][j] + ;
}
}
}
} boolean *res;
inline void solve() {
res = new boolean[(q + )];
uf.query(uf.root, , q, res);
for(int i = ; i <= q; i++)
puts((res[i]) ? ("Connected") : ("Disconnected"));
} int main() {
init();
mktree();
solve();
return ;
}