#1#2#5AC,其它T飞掉,求调(或优化)
查看原帖
#1#2#5AC,其它T飞掉,求调(或优化)
658620
Youth_Glory楼主2024/7/19 09:22
#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;
}
2024/7/19 09:22
加载中...