can_can_need_ @ 2023-11-08 21:39:03
#include <bits/stdc++.h>
using namespace std;
#define umap unordered_map
#define forn_(i, l, r) for (int i = l; i >= r; i--)
#define forn(i, l, r) for (int i = l; i <= r; i++)
const int N = 4e5 + 5;
vector<int> g[N];
int n, m, k;
int u, v, x[N];
bool is[N];
int cnt, ans[N];
class DSU {
public:
void init(int n) {
size = n;
p.resize(size + 1);
forn(i, 0, size - 1) p[i] = i;
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
bool merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return 0;
p[fx] = fy;
cnt--;
return 1;
}
private:
vector<int> p;
int size;
} p;
void dfs(int now) {
forn(i, 0, g[now].size() - 1) {
int v = g[now][i];
if (is[v]) continue;
if (!p.merge(now, v)) continue;
dfs(v);
}
}
int main() {
cin >> n >> m;
forn(i, 1, m) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
cin >> k;
forn(i, 1, k) cin >> x[i], is[x[i]] = 1;
p.init(n);
cnt = n - k;
forn(i, 0, n - 1) {
if (is[i]) continue;
dfs(i);
}
ans[k + 1] = cnt;
forn_(i, k, 1) {
is[x[i]] = 0;
cnt++;
dfs(x[i]);
ans[i] = cnt;
}
forn(i, 1, k + 1) cout << ans[i] << endl;
return 0;
}
N开1e6还是RE