比赛链接

AtCoder Beginner Contest 264

E.Blackout 2

给出很多点(\(n+m\leq 2\times 10^5\))，有发电站和城市，以及很多边（\(e\leq 5\times 10^5\)），有 \(q\) 次删边操作，求每次操作后有电的城市数量

解题思路

并查集

离线逆序处理，即只考虑建边操作，用并查集维护有电城市的信息即可

• 时间复杂度：\(O(n+m+e+q)\)

代码

// Problem: E - Blackout 2
// Contest: AtCoder - freee Programming Contest 2022（AtCoder Beginner Contest 264）
// URL: https://atcoder.jp/contests/abc264/tasks/abc264_e
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
// #define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=5e5+5;
int n,m,e,q,Q[N],fa[N],sz[N],res[N];
bool v[N],st[N];
PII a[N];
int find(int x)
{
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main()
{
    cin>>n>>m>>e;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=n;i++)sz[i]=1;
    for(int i=1;i<=e;i++)
    {
    	cin>>a[i].fi>>a[i].se;
    	if(a[i].fi>a[i].se)swap(a[i].fi,a[i].se);
    }
    cin>>q;
    for(int i=1;i<=q;i++)cin>>Q[i],st[Q[i]]=true;
    for(int i=1;i<=e;i++)
    {
    	if(!st[i])
    	{
    		if(a[i].fi<=n&&a[i].se>n)
    		{
    			int x=find(a[i].fi);
    			if(!v[x])
    			{
    				v[x]=true;
    				res[q]+=sz[x];
    			}
    		}
    		else if(a[i].se<=n)
    		{
    			int x=find(a[i].fi),y=find(a[i].se);
    			if(x!=y)
    			{
    				if(!v[x]&&v[y])
    				{
    					res[q]+=sz[x];
    					fa[x]=y,sz[y]+=sz[x];
    				}
    				else if(!v[y]&&v[x])
    				{
    					res[q]+=sz[y];
    					fa[y]=x,sz[x]+=sz[y];
    				}
    				else
    					fa[y]=x,sz[x]+=sz[y];
    			}
    		}
    	}
    }
    for(int i=q;i;i--)
    {
    	int id=Q[i];
    	int t=res[i];
    	if(a[id].fi<=n&&a[id].se>n)
		{
			int x=find(a[id].fi);
			if(!v[x])
			{
				v[x]=true;
				t+=sz[x];
			}
		}
		else if(a[id].se<=n)
		{
			int x=find(a[id].fi),y=find(a[id].se);
			if(x!=y)
			{
				if(!v[x]&&v[y])
				{
					t+=sz[x];
					fa[x]=y,sz[y]+=sz[x];
				}
				else if(!v[y]&&v[x])
				{
					t+=sz[y];
					fa[y]=x,sz[x]+=sz[y];
				}
				else
    				fa[y]=x,sz[x]+=sz[y];
			}
		}
    	res[i-1]=t;
    }
    for(int i=1;i<=q;i++)cout<<res[i]<<'\n';
    return 0;
}