40分求助

提交记录

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
#include<stack>
#define REG register
#define INL inline
#define Max(x,y) (x<y?y:x)
#define int long long
using namespace std;
int fa[2000005];int co[1000005];
INL int find(int x){
    if(fa[x]!=x)fa[x]=find(fa[x]);
    return fa[x];
}
INL int merge(int x,int y,int fl){
    int xx=find(x),yy=find(y);
    int re;
    if(xx == yy||fl)re=0;
    else re=1;
    if(xx!=yy)
    fa[xx]=yy;
    return re;
}
int n,m;
int x[1000005],y[1000005];
int visit[1000005];

vector<int> l[1000005];
int ed[1000005];

signed main(){
    cin>>n>>m;
    for(REG int i=0;i<n;i++)fa[i]=i,co[i]=1;
    for(REG int i=1;i<=m;i++){
        scanf("%lld%lld",&x[i],&y[i]);
        l[x[i]].push_back(i);
        l[y[i]].push_back(i);
    }
    int k;
    cin>>k;
    int cnt=n;
    for(int i=1;i<=k;i++){
        scanf("%lld",&ed[i]);
        co[ed[i]]=0;
        cnt--;
    }
    stack<int>sta;
    for(int i=0;i<n;i++){
        if(!co[i])continue;
        for(REG int j=0;j<l[i].size();j++){
            if(visit[l[i][j]])continue;
            if(co[x[l[i][j]]] == 0||co[y[l[i][j]]] == 0){
                continue;
            }
            merge(x[l[i][j]],y[l[i][j]],1);
        }
    }
    for(REG int i=k;i>=1;i--){
        sta.push(cnt);
        co[ed[i]]=1;
        int flag=1;
        int use=1;
        for(REG int j=0;j<l[ed[i]].size();j++){
            if(visit[l[ed[i]][j]])continue;
            if(x[l[ed[i]][j]]!=ed[i]&&co[x[l[ed[i]][j]]] == 0)continue;
            if(y[l[ed[i]][j]]!=ed[i]&&co[y[l[ed[i]][j]]] == 0)continue;
            visit[l[ed[i]][j]]=1;
            cnt-=merge(x[l[ed[i]][j]],y[l[ed[i]][j]],use);
            use=0;
            flag=0;
        }
        if(flag)cnt++;
    }
    sta.push(cnt);
    while(!sta.empty()){
        cout<<sta.top()<<endl;
        sta.pop();
    }
}