ABC的E求助T两个点
  • 板块学术版
  • 楼主wangshi
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/8/13 21:44
  • 上次更新2023/10/27 15:33:03
查看原帖
ABC的E求助T两个点
541553
wangshi楼主2022/8/13 21:44
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<stack>
#define ll long long
using namespace std;
const int N=5e5+10;
bool f[N],vis[N],dis[N];
int u[N],v[N],n,m,E,ans;
int q,x[N],head[N],cnt;
stack<int> s;
struct edge
{
	int to,next;
}e[N<<1];
inline ll read()
{
	char c;ll res=0,flag=1;
	for(;!isdigit(c);c=getchar())if(c=='-')flag=-1;
	for(;isdigit(c);c=getchar())res=res*10+c-'0';
	return res*flag;
}
void add(int u,int v)
{
	e[++cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}
void dfs(int u)
{
	vis[u]=1;
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(!vis[v])
		{
			if(v>=1&&v<=n)
			{
				if(!dis[v])
				{
					dis[v]=1;
					ans++;
				}
			}
			dfs(v);
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	n=read(),m=read(),E=read();
	for(int i=1;i<=E;i++)
	{
		u[i]=read(),v[i]=read();
	}
	q=read();
	for(int i=1;i<=q;i++) 
	{
		x[i]=read();
		f[x[i]]=1;
	}
	for(int i=1;i<=E;i++)
	{
		if(!f[i]) 
		{
			add(u[i],v[i]);
			add(v[i],u[i]);
		}
	}
	for(int i=n+1;i<=n+m;i++)
	{
		if(!vis[i]) dfs(i);
	}
	for(int i=q;i>=1;i--)
	{
		s.push(ans);
		add(u[x[i]],v[x[i]]);
		add(v[x[i]],u[x[i]]);
		if(u[x[i]]>n)
		{
			if(v[x[i]]>n) continue;
			else dfs(u[x[i]]);
		}
		if(v[x[i]]>n)
		{
			if(u[x[i]]>n) continue;
			else dfs(v[x[i]]);			
		}
		if(u[x[i]]<=n&&v[x[i]]<=n)
		{
			if(dis[u[x[i]]]&&!dis[v[x[i]]]) dfs(u[x[i]]);
			if(!dis[u[x[i]]]&&dis[v[x[i]]]) dfs(v[x[i]]);
		}
	}
	while(!s.empty())
	{
		cout<<s.top()<<"\n";
		s.pop();
	}
	return 0;
}

2022/8/13 21:44
加载中...