NOIp 考前适应题

A CF1494E A-Z Graph

题意

给一个有向图，边权是字母，有三种操作：

• 添加边 \((u,v,c)\)；
• 删除边 \((u,v)\)；
• 询问是否存在一个长度为 \(k\) 的非简单路径满足 \(v_1 \leftarrow v_k\) 的路径与 \(v_k \leftarrow v_1\) 的路径边权序列相同。

分析

手玩题。顶点数量为偶数的情况容易发现只要有一个二元环就行了。

容易发现路径 \([1,2,1]\) 满足题设，同样 \([1,2,1,2,1],[1,2,1,2,1,2,1]\) 也都满足题设，这启示我们将所有奇数的询问归位一类。

必要性也很显然，任意满足题设的路径必然至少包含一个二元环。

顶点数量为奇数的情况是类似的，结论是存在一个二元环且环上的相反边字母相同。

判二元环存在性只需要 map 等容器维护所有边就行了。

#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef pair<int,int> pii;
typedef unsigned long long ull;
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
int n,m;
map<pii,char> mp;
int cnt1,cnt2;
signed main()
{
	IOS;
	cin>>n>>m;
	while(m--)
	{
		char op; cin>>op;
		if(op=='+')
		{
			int x,y; char c;
			cin>>x>>y>>c;
			mp[{x,y}]=c;
			if(mp[{y,x}]) cnt1++;
			if(mp[{y,x}]==c) cnt2++;
		}
		else if(op=='-')
		{
			int x,y; cin>>x>>y;
			if(mp[{x,y}]&&mp[{y,x}]) cnt1--;
			if(mp[{x,y}]==mp[{y,x}]) cnt2--;
			mp.erase({x,y});
		}
		else
		{
			int k; cin>>k;
			if(k&1) cout<<((cnt1!=0)?"YES":"NO")<<"\n";
			else cout<<((cnt2!=0)?"YES":"NO")<<"\n";
		}
	}
	return 0;
}