洛谷 P1197 [JSOI2008]星球大战——并查集

时间：2022-03-22 09:28:38

先上一波题目 https://www.luogu.org/problem/P1197

很明显删除的操作并不好处理 那么我们可以考虑把删边变成加边

只需要一波时间倒流就可以解决拉

储存删边顺序倒过来加边 问题便完美解决了qwq

#include<cstdio>

#include<cstring>

#include<algorithm>

const int M=;

using namespace std;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,k,cnt=,tot=;

int first[M],bomb[M],in[M],fa[M],ans[M];

struct node{int to,next;}e[M];

void ins(int x,int y){cnt++; e[cnt].to=y,e[cnt].next=first[x]; first[x]=cnt;}

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

void insert(int x){

    //puts("qwq");

    for(int i=first[x];i;i=e[i].next){

        //printf("%d %d\n",x,e[i].to);

        int now=e[i].to;

        if(in[now]) continue;

        int p=find(x),q=find(now);

        if(p!=q){tot--; fa[p]=q;}

    }

}

int main(){

    int x,y;

    n=read(); m=read();

    for(int i=;i<=n;i++) fa[i]=i;

    for(int i=;i<=m;i++) x=read()+,y=read()+,ins(x,y),ins(y,x);

    //printf("qwq%d\n",cnt);

    k=read();

    for(int i=;i<=k;i++) bomb[i]=read()+,in[bomb[i]]=;

    for(int i=;i<=n;i++)if(!in[i]) tot++,insert(i);

    ans[k+]=tot; //printf("%d\n",ans[k]);

    for(int i=k;i>=;i--){

        in[bomb[i]]=;

        tot++;

        insert(bomb[i]);

        ans[i]=tot;

    }

    for(int i=;i<=k+;i++) printf("%d\n",ans[i]);

    return ;

}

相关文章