社区讨论

样例没过,求调

P1197[JSOI2008] 星球大战参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lo2km3tm
此快照首次捕获于
2023/10/23 15:22
2 年前
此快照最后确认于
2023/10/23 15:22
2 年前
查看原帖
CPP
#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;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...