bzoj 1015[JSOI2008]星球大战starwar

1015: [JSOI2008]星球大战starwar

Time Limit: 3 Sec Memory Limit: 162 MB

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

第一行是开始时星球的连通块个数。接下来的K行，每行一个整数，表示经过该次打击后现存星球
的连通块个数。

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

比较水的一道题

并查集的性质是很好维护加边的操作，却不能支持删边

所以我们只需倒着做一遍就能将删边转为加边

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #define LL long long 
  6 
  7 using namespace std;
  8 
  9 const int MAXM = 2e5 + 10;
 10 const int MAXN = 4e5 + 10;
 11 int N, M, K;
 12 int cnt = 0;
 13 int ans[MAXN];
 14 int exs[MAXN];
 15 int x, y;
 16 int father[MAXN];
 17 int head[MAXN];
 18 
 19 int find(int x)
 20 {
 21     if(x != father[x]) {
 22         father[x] = find(father[x]);
 23     }
 24     return father[x];
 25 }
 26 struct edge {
 27     int use;
 28     int v;
 29     int next;
 30 } g[MAXM * 3];
 31 
 32 void addedge(int u, int v)
 33 {
 34     g[cnt].v = v;
 35     g[cnt].use = 0;
 36     g[cnt].next = head[u];
 37     head[u] = cnt++;
 38 }
 39 int d[MAXN];
 40 inline LL read()
 41 {
 42     LL x = 0, w = 1; char ch = 0;
 43     while(ch < '0' || ch > '9') {
 44         if(ch == '-') {
 45             w = -1;
 46         }
 47         ch = getchar();
 48     }
 49     while(ch >= '0' && ch <= '9') {
 50         x = x * 10 + ch - '0';
 51         ch = getchar();
 52     }
 53     return x * w;
 54 }
 55 
 56 void init()
 57 {
 58     memset(head, -1, sizeof head);
 59     for(int i = 0; i < N; i++) {
 60         father[i] = i;
 61     }
 62 }
 63 int main()
 64 {
 65     N = read(), M = read();
 66     init();
 67     for(int i = 1; i <= M; i++) {
 68         int u = read(), v = read();
 69         addedge(u, v);
 70         addedge(v, u);
 71     }
 72     K = read();
 73     for(int i = 1; i <= K; i++) {
 74         int k = read();
 75         d[i] = k;
 76         exs[k] = 1;
 77     }
 78     ans[K + 1] = N - K;
 79 /*    for(int i = 0; i < N; i++) {
 80         cout<<exs[i]<<" ";
 81     }
 82     cout<<endl;
 83     cout<<find(2)<<" "<<find(6)<<endl;*/
 84     for(int i = 0; i < N; i++) {
 85         if(!exs[i]) {
 86             for(int j = head[i]; j != -1; j = g[j].next) {
 87                 int to = g[j].v;
 88                 if(!g[j ^ 1].use && !exs[to]) {
 89                     g[j].use = 1;
 90                     x = find(to), y = find(i);
 91                     if(x != y) {
 92                         father[y] = x;
 93                         ans[K + 1]--;
 94                     }
 95                 }
 96             }
 97         }
 98     }
 99     for(int i = K; i >= 1; i--) {
100         int k = d[i];
101         ans[i] = ans[i + 1] + 1;
102         for(int j = head[k]; j != -1; j = g[j].next) {
103             int to = g[j].v;
104             if(!exs[to] && !g[j ^ 1].use) {
105                 g[j].use = 1;
106                 x = find(to), y = find(k);
107                 if(x != y) {
108                     father[y] = x;
109                     ans[i]--;
110                 }
111             }
112         }
113         exs[k] = 0;
114     }
115     for(int i = 1; i <= K + 1; i++) {
116         printf("%d
", ans[i]);
117     }
118     return 0;
119 }
120 
121 /*
122 8 13
123 0 1
124 1 6
125 6 5
126 5 0
127 0 6
128 1 2
129 2 3
130 3 4
131 4 5
132 7 1
133 7 2
134 7 6
135 3 6
136 5
137 1
138 6
139 3
140 5
141 7
142 
143 
144 */

View Code