BZOJ 3237: [Ahoi2013]连通图

3237: [Ahoi2013]连通图

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 1161  Solved: 399
[Submit][Status][Discuss]

Description

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

Source

[Submit][Status][Discuss]

很有意思的一道题。乍一看就是LCT，后来听说可以CDQ水过，一想确实哎，写写就1A了。

对于一张图的连通性，我们可以用并查集维护，简单方便，可是不支持删边操作（这里指的是随机的删边）。但发现可以通过记录father数组的更改，得到一个回溯栈，方便地进行顺序删边。

利用CDQ分治的想法，在一个solve(l,r)时，考虑把(mid,r]内的边补回到图中，维护并查集并记录改变（用来回溯），然后递归solve(l,mid)，最后回溯；再把[l,mid]的边补回，递归右侧，回溯。这样到底层solve(l,r)，即l==r时，并查集维护的刚好不包含当前这组询问中的边，此时记录下答案即可。

 #include <bits/stdc++.h>

 inline int getC(void) {
     static const int siz = ;

     static char buf[siz];
     static char *hd = buf + siz;
     static char *tl = buf + siz;

     if (hd == tl)
         fread(hd = buf, , siz, stdin);

     return int(*hd++);
 }

 inline int getI(void) {
     register int ret = ;
     register int neg = false;
     register int bit = getC();

     for (; bit < ; bit = getC())
         if (bit == '-')neg ^= true;

     for (; bit > ; bit = getC())
         ret = ret *  + bit - '';

     return neg ? -ret : ret;
 }

 const int maxn = ;

 int n, m, p;

 struct edge {
     int x, y;
 }e[maxn];

 struct query {
     int k, s[];
     bool connect;
 }q[maxn];

 int fa[maxn];
 int sz[maxn];

 int cnt[maxn];

 inline int find(int u) {
     while (fa[u] != u)
         u = fa[u];
     return u;
 }

 int stk[maxn], tot;

 void solve(int l, int r) {
     if (l == r) {
         q[l].connect = sz[find()] == n;
         return;
     }

     int mid = (l + r) >> , top = tot;

     for (int i = l; i <= mid; ++i)
         for (int j = ; j <= q[i].k; ++j)
             if (--cnt[q[i].s[j]] == ) {
                 int x = find(e[q[i].s[j]].x);
                 int y = find(e[q[i].s[j]].y);
                 if (x != y) {
                     if (sz[x] < sz[y])
                         fa[x] = y, sz[y] += sz[x], stk[++tot] = x;
                     else
                         fa[y] = x, sz[x] += sz[y], stk[++tot] = y;
                 }
             }

     solve(mid + , r);

     while (tot > top) {
         int t = stk[tot--];
         sz[fa[t]] -= sz[t];
         fa[t] = t;
     }

     for (int i = l; i <= mid; ++i)
         for (int j = ; j <= q[i].k; ++j)
             ++cnt[q[i].s[j]];

     for (int i = mid + ; i <= r; ++i)
         for (int j = ; j <= q[i].k; ++j)
             if (--cnt[q[i].s[j]] == ) {
                 int x = find(e[q[i].s[j]].x);
                 int y = find(e[q[i].s[j]].y);
                 if (x != y) {
                     if (sz[x] < sz[y])
                         fa[x] = y, sz[y] += sz[x], stk[++tot] = x;
                     else
                         fa[y] = x, sz[x] += sz[y], stk[++tot] = y;
                 }
             }

     solve(l, mid);

     while (tot > top) {
         int t = stk[tot--];
         sz[fa[t]] -= sz[t];
         fa[t] = t;
     }

     for (int i = mid + ; i <= r; ++i)
         for (int j = ; j <= q[i].k; ++j)
             ++cnt[q[i].s[j]];
 }

 signed main(void) {
     n = getI();
     m = getI();

     for (int i = ; i <= n; ++i)
         fa[i] = i, sz[i] = ;

     for (int i = ; i <= m; ++i)
         e[i].x = getI(),
         e[i].y = getI();

     p = getI();

     for (int i = ; i <= p; ++i) {
         q[i].k = getI();
         for (int j = ; j <= q[i].k; ++j)
             ++cnt[q[i].s[j] = getI()];
     }

     for (int i = ; i <= m; ++i)
         if (!cnt[i]) {
             int x = find(e[i].x);
             int y = find(e[i].y);
             if (x != y) {
                 if (sz[x] < sz[y])
                     fa[x] = y, sz[y] += sz[x];
                 else
                     fa[y] = x, sz[x] += sz[y];
             }
         }

     solve(, p);

     for (int i = ; i <= p; ++i)
         puts(q[i].connect ? "Connected" : "Disconnected");
 }

@Author: YouSiki