逆序遍历 + 并查集
先保存下来所有边,标记并保存所有被删除的点。
用剩余的点和边建立并查集,此时可以得到最后一个点被删除后的连通块数量。
开始逆序遍历:
- 加入最后一个被删除的点,可以得到删除倒数第二个点后的连通块数量;
- 加入倒数第二个被删除的点,可以得到删除倒数第三个点后的连通块数量;
- …
- 加入第一个被删除的点,可以得到初始时的连通块数量
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int N = 4e5 + 10;
int p[N];
vector<int> v[N];
int st[N];
int find(int x) {
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++) {
int a, b;
scanf("%d%d", &a, &b);
v[a].push_back(b), v[b].push_back(a);
}
int k;
scanf("%d", &k);
stack<int> dest, ans;
for(int i = 0; i < k; i++) {
int a;
scanf("%d", &a);
st[a] = 1;
dest.push(a);
}
int cnt = n - k;
for(int i = 0; i < n; i++) {
p[i] = i;
}
for(int i = 0; i < n; i++) {
if(st[i]) continue;
for(auto j : v[i]) {
if(st[j]) continue;
int pa = find(i);
int pb = find(j);
if(pa == pb) continue;
p[pa] = pb;
cnt--;
}
}
ans.push(cnt);
while(dest.size()) {
auto u = dest.top();
dest.pop();
st[u] = 0;
cnt++;
for(auto j: v[u]) {
if(st[j]) continue;
int pu = find(u), pj = find(j);
if(pu == pj) continue;
p[pu] = pj;
cnt--;
}
ans.push(cnt);
}
while(ans.size()) {
auto t = ans.top();
ans.pop();
printf("%d\n", t);
}
return 0;
}