[AtCoder Beginner Contest 264]E - Blackout 2（离线处理 + 并查集）

题目传送门：E - Blackout 2 (atcoder.jp)

题目 / Problem

有N个城市和M个发电厂，有E条边，第 i 条边连接两个点（可能是城市也可能是发电厂），现在有Q个项目，每个项目会摧毁第x条边，问每个项目之后有多少个城市可以到达发电厂。

思路 / Thought

因为M个发电厂都是等价的，所有可以把这M个发电厂都看作0号点。为了维护“是否可达”这个属性，可以用并查集，但是与此同时还需要一个集合来存储某个祖先的所有儿子。

在合并操作的时候需要将集合也进行合并，合并的规则需要注意：如果有0号点，就将另一个集合合并到0号点，否则将小集合合并到大集合。

我们又注意到，这里是要将边摧毁，也就是将点分离，显然不好操作，我们可以将询问离线，倒过来进行合并。

也就是说“正着分离” = “倒着合并”，将答案保存下来并输出即可。

需要记录一下有哪些点是没参与询问的，作为初始状态，然后从后往前将边一条一条地加入。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 9;
int pre[maxn];//0是发电厂 
set<int> s[maxn];//集合 
int N, M, E;

int root(int x){return pre[x] == x ? x : pre[x] = root(pre[x]);}

void Merge(int x,int y)
{
	int rx = root(x), ry = root(y);
	if(rx == ry)return;//如果已经是同一个集合不用合并 
	if(rx > ry)swap(rx, ry);//使得rx < ry 
	if(rx == 0)//如果rx是0合并到0号集合 
	{
		for(auto &i : s[ry])s[rx].insert(i);
		s[ry].clear();
		pre[ry] = 0;
	}else//否则合并到较大集合 
	{
		if(s[rx].size() > s[ry].size())swap(rx, ry);
		for(auto &i : s[rx])s[ry].insert(i);
		s[rx].clear();
		pre[rx] = ry;
	}
}

void solve()
{
	cin >> N >> M >> E;
	for(int i = 1;i <= N; ++ i)
	{
		pre[i] = i;
		s[i].insert(i);
	}
	
	vector<pair<int, int> > v;
	
	v.push_back({0, 0});
	for(int i = 1;i <= E; ++ i)
	{
		int x, y;cin >> x >> y;
		x = x > N ? 0 : x;
		y = y > N ? 0 : y;
		v.push_back({x, y});
	}
	
	bitset<maxn * 3> del;//删除的边
	
	int Q;cin >> Q;
	vector<int> q, ans(Q + 5, 0);
	
	for(int i = 0;i < Q; ++ i)
	{
		int x;cin >> x;
		q.push_back(x);
		del[x] = 1;
	}
	
	int cnt = 0;
	//将未被摧毁的边建立
	for(int i = 1;i <= E; ++ i)if(!del[i])Merge(v[i].first, v[i].second);
	
	for(int i = q.size() - 1;i >= 0; -- i)//反向重建
	{
		ans[i] = s[0].size();
		int x = v[q[i]].first, y = v[q[i]].second;
		Merge(x, y);
	}
	for(int i = 0;i < Q; ++ i)cout << ans[i] << '\n';
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int _ = 1;
	while(_ --)solve();
	
	return 0;
}