laekov

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");

}