[ABC229E] Graph Destruction 题解

思路解析

题目要求删点，而众所周知删点的代价要大于加点的代价，于是我们考虑倒着处理询问，将每一个删点改成加点，而加点时就用并查集维护连通块即可。

code

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, fa[N];
vector<int> g[N];
int find(int x) {
	if(x == fa[x]) return x;
	return (fa[x] = find(fa[x]), fa[x]);
}
int main() {
	cin >> n >> m;
	for(int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i = 1; i <= n; i++) fa[i] = i;
	int ans = 0;
	stack<int> st;
	for(int i = n; i >= 1; i--) {
		st.push(ans);
		ans ++;
		for(auto it : g[i]) {
			if(it > i) {
				if(find(it) != find(i)) ans --;
				fa[find(it)] = find(i);
			}
		}
	}
	while(!st.empty()) cout << st.top() << '\n', st.pop();
	return 0;
}