1 solutions

  • 1
    @ 2023-10-27 16:21:34
    #include<bits/stdc++.h>
    using namespace std;
    const int N=4e5+5;
    vector<int>E[N];
    int vis[N],w[N],ans[N];
    int fa[N];
    int get(int x){
    	if(fa[x]==x)return x;
    	return fa[x]=get(fa[x]);
    }
    int main(){
    	int n,m;scanf("%d%d",&n,&m);
    	for(int i=1;i<=m;i++){
    		int x,y;scanf("%d%d",&x,&y);
    		x++,y++;
    		E[x].push_back(y);
    		E[y].push_back(x);
    	}
    	for(int i=1;i<=n;i++){
    		vis[i]=1;
    	}
    	int q;scanf("%d",&q);
    	for(int i=1;i<=q;i++){
    		scanf("%d",&w[i]);
    		w[i]++;
    		vis[w[i]]=0;
    	}
    	for(int i=1;i<=n;i++){
    		fa[i]=i;
    	}
    	for(int x=1;x<=n;x++){
    		if(!vis[x])continue;
    		for(int y:E[x]){
    			if(!vis[y])continue;
    			int tx=get(x),ty=get(y);
    			if(tx!=ty){
    				fa[tx]=ty;
    			}
    		}
    	}
    	for(int i=1;i<=n;i++){
    		if(fa[i]==i&&vis[i]){
    			ans[q+1]++;
    		}
    	}
    	for(int i=q;i>=1;i--){
    		int x=w[i];
    		vis[x]=1;
    		ans[i]=ans[i+1]+1;
    		for(int y:E[x]){
    			if(!vis[y])continue;
    			int tx=get(x),ty=get(y);
    			if(tx!=ty){
    				fa[tx]=ty;
    				ans[i]--;
    			}
    		}
    	}
    	for(int i=1;i<=q+1;i++){
    		printf("%d\n",ans[i]);
    	}
    	return 0;
    }
    
    • 1

    Information

    ID
    1015
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    1
    Tags
    # Submissions
    43
    Accepted
    36
    Uploaded By