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時，并查集維護的剛好不包含當前這組詢問中的邊，此時記錄下答案即可。

?

1 #include <bits/stdc++.h> 2 3 inline int getC(void) { 4 static const int siz = 1024; 5 6 static char buf[siz]; 7 static char *hd = buf + siz; 8 static char *tl = buf + siz; 9 10 if (hd == tl) 11 fread(hd = buf, 1, siz, stdin); 12 13 return int(*hd++); 14 } 15 16 inline int getI(void) { 17 register int ret = 0; 18 register int neg = false; 19 register int bit = getC(); 20 21 for (; bit < 48; bit = getC()) 22 if (bit == '-')neg ^= true; 23 24 for (; bit > 47; bit = getC()) 25 ret = ret * 10 + bit - '0'; 26 27 return neg ? -ret : ret; 28 } 29 30 const int maxn = 500005; 31 32 int n, m, p; 33 34 struct edge { 35 int x, y; 36 }e[maxn]; 37 38 struct query { 39 int k, s[5]; 40 bool connect; 41 }q[maxn]; 42 43 int fa[maxn]; 44 int sz[maxn]; 45 46 int cnt[maxn]; 47 48 inline int find(int u) { 49 while (fa[u] != u) 50 u = fa[u]; 51 return u; 52 } 53 54 int stk[maxn], tot; 55 56 void solve(int l, int r) { 57 if (l == r) { 58 q[l].connect = sz[find(1)] == n; 59 return; 60 } 61 62 int mid = (l + r) >> 1, top = tot; 63 64 for (int i = l; i <= mid; ++i) 65 for (int j = 1; j <= q[i].k; ++j) 66 if (--cnt[q[i].s[j]] == 0) { 67 int x = find(e[q[i].s[j]].x); 68 int y = find(e[q[i].s[j]].y); 69 if (x != y) { 70 if (sz[x] < sz[y]) 71 fa[x] = y, sz[y] += sz[x], stk[++tot] = x; 72 else 73 fa[y] = x, sz[x] += sz[y], stk[++tot] = y; 74 } 75 } 76 77 solve(mid + 1, r); 78 79 while (tot > top) { 80 int t = stk[tot--]; 81 sz[fa[t]] -= sz[t]; 82 fa[t] = t; 83 } 84 85 for (int i = l; i <= mid; ++i) 86 for (int j = 1; j <= q[i].k; ++j) 87 ++cnt[q[i].s[j]]; 88 89 for (int i = mid + 1; i <= r; ++i) 90 for (int j = 1; j <= q[i].k; ++j) 91 if (--cnt[q[i].s[j]] == 0) { 92 int x = find(e[q[i].s[j]].x); 93 int y = find(e[q[i].s[j]].y); 94 if (x != y) { 95 if (sz[x] < sz[y]) 96 fa[x] = y, sz[y] += sz[x], stk[++tot] = x; 97 else 98 fa[y] = x, sz[x] += sz[y], stk[++tot] = y; 99 } 100 } 101 102 solve(l, mid); 103 104 while (tot > top) { 105 int t = stk[tot--]; 106 sz[fa[t]] -= sz[t]; 107 fa[t] = t; 108 } 109 110 for (int i = mid + 1; i <= r; ++i) 111 for (int j = 1; j <= q[i].k; ++j) 112 ++cnt[q[i].s[j]]; 113 } 114 115 signed main(void) { 116 n = getI(); 117 m = getI(); 118 119 for (int i = 1; i <= n; ++i) 120 fa[i] = i, sz[i] = 1; 121 122 for (int i = 1; i <= m; ++i) 123 e[i].x = getI(), 124 e[i].y = getI(); 125 126 p = getI(); 127 128 for (int i = 1; i <= p; ++i) { 129 q[i].k = getI(); 130 for (int j = 1; j <= q[i].k; ++j) 131 ++cnt[q[i].s[j] = getI()]; 132 } 133 134 for (int i = 1; i <= m; ++i) 135 if (!cnt[i]) { 136 int x = find(e[i].x); 137 int y = find(e[i].y); 138 if (x != y) { 139 if (sz[x] < sz[y]) 140 fa[x] = y, sz[y] += sz[x]; 141 else 142 fa[y] = x, sz[x] += sz[y]; 143 } 144 } 145 146 solve(1, p); 147 148 for (int i = 1; i <= p; ++i) 149 puts(q[i].connect ? "Connected" : "Disconnected"); 150 }

?

@Author: YouSiki

?

轉載于:https://www.cnblogs.com/yousiki/p/6243002.html

總結

以上是生活随笔為你收集整理的BZOJ 3237: [Ahoi2013]连通图的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。