Rhss @ 2023-05-19 13:38:53
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
const int N = 4e5 + 10, M = 2e5 + 10;
int n, m, k;
int h[N], e[M], ne[M], idx;
int f[N], broke[N], ans[N], id[N];
pll edg[M];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int find(int x) {
if (x == f[x]) return x;
return f[x] = find(f[x]);
}
int main() {
scanf("%d%d", &n, &m);
memset(h , -1 , sizeof h);
for (int i = 0 ; i < n ; ++i) f[i] = i;
for (int i = 1 ; i <= m ; ++i) {
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
edg[i] = {a, b};
}
scanf("%d", &k);
for (int i = 1 ; i <= k ; ++i) {
int x;
scanf("%d", &x);
id[i] = x;
broke[x] = 1;
}
int total = n - k;
for (int i = 1 ; i <= m ; ++i) {
int x = edg[i].x, y = edg[i].y;
//如果起点和终点都没有被破坏 , 且不在一个集合内
if (!broke[x] && !broke[y] && f[x] != f[y]) {
//合并 , 联通块减少
total--;
//合并集合
f[find(x)] = find(y);
}
}
//K个地区都被占领后的联通块数量
ans[k] = total;
for (int i = k - 1 ; i >= 0 ; --i) {
total++;
//取出第 i 次会被占领的地区
int t = id[i];
broke[t] = 0;
for (int j = h[j] ; ~j ; j = ne[j]) {
int u = e[j];
if (!broke[t] && !broke[u] && f[t] != f[u]) {
total--;
f[find(t)] = find(u);
}
}
ans[i] = total;
}
cout << endl;
for (int i = 0 ; i <= k ; ++i) cout << ans[i] << endl;
return 0;
}