abc264 E

标签：连通 ch int cnt fa abc264 read

题目链接:click here

Solution:

首先考虑维护连通块，但是在删边的条件下进行维护连通块显然比较复杂

如果不是删边，而是增添边，那么连通块的维护难度将大大减少，那么我们如何从删边变成添加边呢

不妨考虑倒过来做，我们先把所有要删去的边一次性删去，然后反过来依次加回去即可

现在我们要添加一条边，如果两个点本来就处于相同连通块，那么不需要额外操作

如果他们处于不同连通块，且这两个连通块的发电情况不同，那么就需要更新答案

连通块的维护考虑并查集即可

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
const int M=1e6+1;
bool is[M],elfed[N];
int n,m,e,q,cnt,tot;
int eg1[M],eg2[M],eg3[M];
int ans,head[N],nxt[M],to[M];
int cpt[N],sz[N],fa[N],Ans[M];
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
void ins(int x,int y){
    nxt[++cnt]=head[x];
    head[x]=cnt;to[cnt]=y;
}
void Iins(int x,int y){
    ins(x,y);
    ins(y,x);
}
void dfs(int x){
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(is[y]) continue;
        is[y]=1;cpt[y]=cpt[x];
        if(y<=n) ++sz[cpt[x]];
        if(y>n) elfed[cpt[x]]=1;
        dfs(y);
    }
}
int gf(int x){
    if(x==fa[x]) return x;
    return fa[x]=gf(fa[x]);
}
signed main(){
    n=read(),m=read(),e=read();
    for(int i=1;i<=e;i++)
        eg1[i]=read(),eg2[i]=read();
    q=read();
    for(int i=1;i<=q;i++)
        eg3[i]=read(),is[eg3[i]]=1;
    for(int i=1;i<=e;i++)
        if(!is[i]) Iins(eg1[i],eg2[i]);
    for(int i=1;i<=n+m;i++) is[i]=0;
    for(int i=1;i<=n+m;i++)
        if(!is[i]){
            is[i]=1,cpt[i]=++tot;
            if(i<=n) ++sz[tot];
            if(i>n) elfed[tot]=1;
            fa[tot]=tot;dfs(i);
        }
    for(int i=1;i<=n;i++) if(elfed[cpt[i]]) ++ans;
    for(int i=q;i;i--){
        Ans[i]=ans;
        int x=eg1[eg3[i]],y=eg2[eg3[i]];
        x=gf(cpt[x]);y=gf(cpt[y]);
        if(x==y) continue;
        if(elfed[x]&&!elfed[y]){
            ans+=sz[y];
            fa[y]=x;
            sz[x]+=sz[y];
        }
        if(elfed[y]&&!elfed[x]){
            ans+=sz[x];
            fa[x]=y;
            sz[y]+=sz[x];
        }
        if(elfed[x]^elfed[y]==0){
            fa[x]=y;
            sz[y]+=sz[x];
        }
    }
    for(int i=1;i<=q;i++) printf("%d\n",Ans[i]);
    return 0;
}

标签：连通,ch,int,cnt,fa,abc264,read
From： https://www.cnblogs.com/NLDQY/p/16588515.html