#1#2#5AC,其它T飞掉,求调(或优化)

P1197 [JSOI2008] 星球大战

Youth_Glory @ 2024-07-19 09:22:39

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const ll N=2e5+5;
ll n,m,k,fa[2*N],head=1,cnt;
bool vis[2*N];
stack<ll>record;
stack<ll>answer;

struct edge{
    ll from,reach,u=0,v=0;
}e[N];

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

signed main()
{
    IOS;
    cin>>n>>m;
    cin>>k;e[1].from=k;
    cin>>k;e[1].reach=k;
    for(ll i=2,u,v;i<=m;i++){
        cin>>u>>v;
        e[i].from=u;
        e[i].reach=v;
        e[i-1].v=i;
        e[i].u=i-1;
    }
    cin>>k;
    for(ll i=1,s;i<=k;i++){
        cin>>s;
        record.push(s);
        vis[s]=true;
    }
    cnt=n-k;
    for(ll i=1;i<=n;i++)fa[i]=i;
    while(!record.empty()){
        for(ll i=head,u,v;i;i=e[i].v){
            u=e[i].from;v=e[i].reach;
            if(vis[u]||vis[v])continue;
            if((u=find(u))!=(v=find(v))){
                fa[find(u)]=find(v);
                --cnt;
            }
            e[e[i].u].v=e[i].v;
            e[e[i].v].u=e[i].u;
            if(e[i].u==0)head=e[i].v;
        }
        answer.push(cnt);
        vis[record.top()]=false;
        ++cnt;
        record.pop();
    }
    for(ll i=head,u,v;i;i=e[i].v){
        u=e[i].from;v=e[i].reach;
        if((u=find(u))!=(v=find(v))){
            fa[find(u)]=find(v);
            --cnt;
        }
    }
    cout<<cnt<<"\n";
    while(!answer.empty()){
        cout<<answer.top()<<"\n";
        answer.pop();
    }
    return 0;
}

|