CF1548A Web of Lies 题解

Web of Lies 题解

洛谷。

Codeforces。

题意比较直接，就不复述了。

思路

分析题意

首先根据操作 3，删人只是暂时的，可以分析出每次删的人对于后面都没有影响。

关注到这个词：

执行以下操作直至不可再执行为止。

显然，在整个图中所有该被删除的人都逃不掉，迟早被删除。

那么看看什么样的神犇才能从操作 3 中存活下来？

• 没朋友的人可以。（这很显然）
• 在所有朋友中，他是最强的一个。这样的话，他的所有朋友都会比他早归西，他也就没了朋友，可以当作第一种情况看待。

这么说来，这道题还挺富含哲理的……

当你最孤独，没朋友就能活下来。

当你在你朋友中是最强的，他们归西了，你还苟着。

当你的某个朋友比你强，你就得卒。

可以考虑用一个数组 e 来记录。\(e_i\) 表示第 \(i\) 个人有几个比他强的朋友。

现在看看操作

加边

当你交了一个朋友，会怎么样呢？

分下情况：

若他比你弱，啥事也没发生。

若他比你强，交了这个朋友会把你害死。必死无疑。\(e_i+1\)。答案 +1。

删边

若他比你弱，也是什么事都没发生。

比你强：

如果你只有这一个比你强的朋友，即 \(e_i=1\)，那么恭喜你，你跟他绝交，你活了下来。

如果你不止他一个，那你目前还得死。不过 \(e_i\) 可以减一。这样以后再绝交几个就可以活了。

询问

直接输出答案即可。

Code

//wrote by Atserckcn
#include<bits/stdc++.h>
using namespace std;
#define ljl long long
const ljl N=2e5+5,M=2e5+5;
ljl n,m,q,u,v,ans/*ans 即为答案*/,op,e[N];
struct EDGE{
	void solve1(ljl from,ljl to)//加边
	{
		ljl minn=(ljl)min(from,to);//选取主角：弱的那个
		if(!e[minn])//交了个比你强的朋友，很遗憾，你目前得死
			--ans;
		e[minn]++;
		return;
	}
	void solve2(ljl from,ljl to)//删边
	{
		ljl minn=(ljl)min(from,to);//找主角
		if(e[minn]==1)//你只有一个比你强的朋友，恭喜你，你能活着
			++ans;
		--e[minn];
		return;
	}
}edge;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	ans=n;
	for(ljl i=1;i<=m;++i)
	{
		cin>>u>>v;
		edge.solve1(u,v);
//		cout<<"----------"<<ans<<'\n';
	}
	cin>>q;
	while(q--)
	{
		cin>>op;
		if(op==1)
		{
			cin>>u>>v;
			edge.solve1(u,v);
			continue;
		}
		if(op==2)
		{
			cin>>u>>v;
			edge.solve2(u,v);
			continue;
		}
		cout<<ans<<'\n';
	}
	return 0;
}

AC 记录。