CDQ重构图。听上去比CDQ还高档的样子。
就是每层重新标号，把没有询问到的边拿来跑并查集。
最初是分开考虑然后可修复的并查集就T傻了。
#include <cstdio>
#include <cstring>
#include <cctype>
#include <set>
#include <algorithm>
using namespace std;
int _d_;
#define readInt(_x_) { \
int& _s_ = _x_; \
while (!isdigit(_d_ = getchar())); \
_s_ = 0; \
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \
}
const int maxn = 100009;
const int maxm = 200009;
const int maxl = 19;
struct edge {
int a, b, i;
};
struct dset {
int r[maxn], hp[maxn * 5], hv[maxn * 5], cnt;
void init(int n) {
for (int i = 1; i <= n; ++ i)
r[i] = i;
cnt = 0;
}
int getRoot(int x) {
int p = x, q;
for (; r[p] ^ p; p = r[p]);
for (; x ^ p; x = q) {
/*hp[cnt] = x;
hv[cnt] = r[x];
++ cnt;*/
q = r[x];
r[x] = p;
}
return p;
}
bool connected(int x, int y) {
return getRoot(x) == getRoot(y);
}
bool merge(int x, int y) {
int a = getRoot(x), b = getRoot(y);
if (a ^ b) {
/*hp[cnt] = a;
hv[cnt] = a;
++ cnt;*/
r[a] = b;
return 1;
}
else
return 0;
}
void recover(int y) {
while (cnt > y) {
-- cnt;
r[hp[cnt]] = hv[cnt];
}
}
};
struct query {
int t, a[5];
void read() {
readInt(t);
for (int i = 0; i < t; ++ i)
readInt(a[i]);
}
};
struct parr {
int t, v[maxn];
void init() {
memset(v, 0, sizeof(v));
t = 0;
}
inline void next() {
++ t;
}
inline void ins(const int& x) {
v[x] = t;
}
inline bool query(const int& x) {
return v[x] == t;
}
};
int n, m, tq, ans[maxn], nn[maxn];
edge e[maxl][maxm];
dset s[maxl];
parr vis;
query q[maxn];
void cdq(int l, int r, int c, int d, int n, int m) {
if (c == 1) {
for (int i = l; i < r; ++ i)
ans[i] = 1;
return;
}
s[d]. init(n);
int mid = (l + r) >> 1;
vis. next();
for (int i = l; i < r; ++ i)
for (int j = 0; j < q[i]. t; ++ j)
vis. ins(q[i]. a[j]);
int cc = c, tn = 0, te = 0;
for (int i = 0; i < m; ++ i)
if (!vis. query(e[d][i]. i))
cc -= s[d]. merge(e[d][i]. a, e[d][i]. b);
for (int i = 1; i <= n; ++ i)
if (s[d]. getRoot(i) == i)
nn[i] = ++ tn;
for (int i = 0; i < m; ++ i)
if (!s[d]. connected(e[d][i]. a, e[d][i]. b)) {
e[d + 1][te]. a = nn[s[d]. getRoot(e[d][i]. a)];
e[d + 1][te]. b = nn[s[d]. getRoot(e[d][i]. b)];
e[d + 1][te]. i = e[d][i]. i;
++ te;
}
if (l + 1 == r) {
ans[l] = (cc == 1);
}
else {
cdq(l, mid, cc, d + 1, tn, te);
cdq(mid, r, cc, d + 1, tn, te);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
readInt(n);
readInt(m);
for (int i = 0; i < m; ++ i) {
readInt(e[0][i]. a);
readInt(e[0][i]. b);
e[0][i]. i = i + 1;
}
readInt(tq);
for (int i = 0; i < tq; ++ i)
q[i]. read();
vis. init();
cdq(0, tq, n, 0, n, m);
for (int i = 0; i < tq; ++ i)
puts(ans[i] ? "Connected" : "Disconnected");
}