星球大战

链接

这题并不简单,说实话,就算想到了关键解法(逆向思维)还会被时间卡住

相比于平常的并查集,这题需要逆向思维,由于我们并不方便在找到摧毁后的信息

所以我们反着来,假设要摧毁3号星球,我们可以排除与三号星球有关的合并(Union),这样就是摧毁后的答案了

为了方便且快速查找与某个星球有关的合并操作,我们可以写一个unordered_map,键负责存储每个星球,值存储vector(planet存储两个数据,分别是两个连接的星球)

在设置一个bool类型的数组destroyed,表示是否被摧毁,使用合并函数的时候只要合并的两个星球都满足destroyed[k]都为0就行

  #include<iostream>
#include<stack>
#include<unordered_map>
#include<vector>
#include<list>
using namespace std;
int n, m;
vector<int>num;
struct planet {
	int x, y;
};
unordered_map<int, vector<planet>>P;

int Find(int x) {
	if (num[x] < 0) {
		return x;
	}
	else {
		return num[x] = Find(num[x]);
	}
}

bool Union(int x, int y) {
	int root_x = Find(x);
	int root_y = Find(y);
	if (root_x != root_y) {
		if (num[root_x] < num[root_y]) {
			num[root_x] += num[root_y];
			num[root_y] = root_x;
		}
		else if (num[root_y] < num[root_x]) {
			num[root_y] += num[root_x];
			num[root_x] = root_y;
		}
		else {
			num[root_x] += num[root_y];
			num[root_y] = root_x;
		}
		return 1;
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	num.resize(n, -1);
	for (int i = 0;i < m;i++) {
		int x, y;
		cin >> x >> y;
		P[x].push_back({ x,y });
		P[y].push_back({ x,y });
	}
	int k;
	cin >> k;
	stack<int>st;
	vector<bool>destoryed(n, 0);
	for (int i = 0;i < k;i++) {
		int pl;
		cin >> pl;
		st.push(pl);
		destoryed[pl] = 1;
	}

	int count = n;
	count -= k;
	
	for (int i = 0;i < n;i++) {
		for (planet it : P[i]) {
			if (!destoryed[it.x] && !destoryed[it.y]) {
				if (Union(it.x, it.y)) {
					count--;
				}
			}
		}
	}
	stack<int>ans;
	ans.push(count);
	while (!st.empty()) {
		int cur = st.top();
		st.pop();
		count++;
		destoryed[cur] = 0;
		for (planet it : P[cur]) {
			if (!destoryed[it.x] && !destoryed[it.y]) {
				if (Union(it.x, it.y)) {
					count--;
				}
			}
		}
		ans.push(count);
	}
	while (!ans.empty()) {
		cout << ans.top() << '\n';
		ans.pop();
	}

}

当然,由于我存储了两次,

P[x].push_back({ x,y });

P[y].push_back({ x,y });

所有Union的调用会重复,不过没有影响(第二次二者就位于同一颗树上了,不会影响count,而且Find函数的调用是O(1)的,可以直接忽略了)

时间复杂度:O(m + k)

空间复杂度:O(n + m + k)