Description

　　很久以前，在一個遙遠的星系，一個黑暗的帝國靠著它的超級武器統治者整個星系。某一天，憑著一個偶然的
機遇，一支反抗軍摧毀了帝國的超級武器，并攻下了星系中幾乎所有的星球。這些星球通過特殊的以太隧道互相直
接或間接地連接。 但好景不長，很快帝國又重新造出了他的超級武器。憑借這超級武器的力量，帝國開始有計劃
地摧毀反抗軍占領的星球。由于星球的不斷被摧毀，兩個星球之間的通訊通道也開始不可靠起來。現在，反抗軍首
領交給你一個任務：給出原來兩個星球之間的以太隧道連通情況以及帝國打擊的星球順序，以盡量快的速度求出每
一次打擊之后反抗軍占據的星球的連通快的個數。（如果兩個星球可以通過現存的以太通道直接或間接地連通，則
這兩個星球在同一個連通塊中）。

Input

　　輸入文件第一行包含兩個整數，N (1? < =? N? < =? 2M) 和M (1? < =? M? < =? 200,000)，分別表示星球的
數目和以太隧道的數目。星球用 0 ~ N-1的整數編號。接下來的M行，每行包括兩個整數X, Y，其中（0 < = X <>?
Y 表示星球x和星球y之間有“以太”隧道，可以直接通訊。接下來的一行為一個整數k，表示將遭受攻擊的星球的
數目。接下來的k行，每行有一個整數，按照順序列出了帝國軍的攻擊目標。這k個數互不相同，且都在0到n-1的范
圍內。

Output

　　輸出文件的第一行是開始時星球的連通塊個數。接下來的N行，每行一個整數，表示經過該次打擊后現存星球
的連通塊個數。

Sample Input

8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6
5
1
6
3
5
7

Sample Output

1
1
1
2
3
3

HINT

Source

Solution

　　從后往前用冰炸雞并查集連邊算聯通塊個數，注意不能算被毀掉的星球

　　據說cin有危險

　　冰炸雞好不好吃？

1 #include <bits/stdc++.h> 2 using namespace std; 3 struct edge 4 { 5 int v, nxt; 6 }e[400005]; 7 int fa[400005], fst[400005], dam[400005], ans[400005]; 8 bool vis[400005]; 9 10 void addedge(int i, int u, int v) 11 { 12 e[i] = (edge){v, fst[u]}, fst[u] = i; 13 } 14 15 int getfa(int x) 16 { 17 return fa[x] = x == fa[x] ? x : getfa(fa[x]); 18 } 19 20 int main() 21 { 22 int n, m, k, u, v; 23 scanf("%d%d", &n, &m); 24 for(int i = 1; i <= n; ++i) 25 fa[i] = i; 26 for(int i = 1; i <= m; ++i) 27 { 28 scanf("%d%d", &u, &v); 29 ++u, ++v; 30 addedge(i << 1, u, v); 31 addedge(i << 1 | 1, v, u); 32 } 33 scanf("%d", &k); 34 for(int i = 1; i <= k; ++i) 35 { 36 scanf("%d", dam + i); 37 vis[++dam[i]] = true; 38 } 39 for(int i = 1; i <= n; ++i) 40 { 41 if(vis[i]) continue; 42 for(int j = fst[i]; j; j = e[j].nxt) 43 if(!vis[e[j].v]) 44 { 45 u = getfa(i), v = getfa(e[j].v); 46 if(u != v) fa[u] = v; 47 } 48 } 49 for(int i = 1; i <= n; ++i) 50 if(fa[i] == i) ++ans[k + 1]; 51 ans[k + 1] -= k; 52 for(int i = k; i; --i) 53 { 54 ans[i] = ans[i + 1] + 1; 55 vis[dam[i]] = false; 56 for(int j = fst[dam[i]]; j; j = e[j].nxt) 57 if(!vis[e[j].v]) 58 { 59 u = getfa(dam[i]), v = getfa(e[j].v); 60 if(u != v) fa[u] = v, --ans[i]; 61 } 62 } 63 for(int i = 1; i <= k + 1; ++i) 64 printf("%d\n", ans[i]); 65 return 0; 66 } View Code

轉載于:https://www.cnblogs.com/CtrlCV/p/5585550.html

總結

以上是生活随笔為你收集整理的[BZOJ1015] [JSOI2008] 星球大战starwar (并查集)的全部內容，希望文章能夠幫你解決所遇到的問題。

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