【2025NOI模拟赛01】图上的游戏 做题记录

给定一个 $2n$ 点 $m$ 边的有向图，Alice 和 Bob 开始博弈。

刚开始每个点都没有颜色，两个人轮流操作，Alice 先手。第 $i$ 轮的人会将 $2i-1$ 和 $2i$ 两个点染上黑色或白色，要求两个点必须一黑一白。

若最后存在某条边满足其入点为黑色，出点为白色则 Bob 赢，否则 Alice 赢。

两人都绝顶聪明，求谁赢。

$1\le n\le 5\times 10^5$，$0\le m\le 5\times 10^5$。

不难发现 Bob 赢面很大，所以考虑判断 Alice 能不能赢。

先把每个点的编号减一。设点 $i$ 最终颜色为 $a_i$，其中黑色为 $1$，白色为 $0$。那么 Alice 赢当且仅当每条边 $u\to v$ 都满足 $a_u\le a_v$。

考虑新建一个有向图 $G$，$G$ 中的连边 $u\to v$ 表示 $a_u\ge a_v$。对于原图的每条边 $u\to v$，$G$ 中都会新建边 $v\to u$。并且由于 $a_i\not=a_{i\oplus 1}$，所以 $a_u\ge a_v$ 时必然有 $a_{v\oplus 1}\ge a_{u\oplus 1}$，所以 $G$ 中还要新建边 $u\oplus 1\to v\oplus 1$。

这个时候 $a_i\not=a_{i\oplus 1}$ 的限制已经满足了。观察一下可以发现，对于一条满足两端由不同人染色的边 $u\to v$，若 Bob 的点染色时间比 Alice 的晚，则 Alice 一定要防止 Bob 通过这条边赢，所以他染的点的颜色是固定的。具体的，若 Bob 控制的点是 $u$，则 $a_u$ 必须为 $0$，在 $G$ 中添加边 $u\oplus1\to u$；否则添加边 $u\to u\oplus 1$。

接下来缩点，缩点后有几种 Bob 赢的情况：

• $u$ 和 $u\oplus 1$ 在同一个连通分量；
• 存在某个连通分量满足其中有至少两个由 Bob 染色的点；
• 存在某个连通分量满足其中有一个由 Bob 染色的点，且该点不是其连通分量中第一个被染色的点；
• 某个由 Bob 染色的点可以到达另外一个由 Bob 染色的点；

不难发现这样就是充要的，那么 bfs 一下即可。

时间复杂度 $O(n+m)$，代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

template<typename T>
inline void read(T &x)
{
	x=0;
	T w=1;
	char c=getchar();
	while(c<'0'||c>'9') w=(c=='-'?-w:w),c=getchar();
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	x=x*w;
}

const int S=3000005;

int n,m;
vector<int> g1[S];
int cnt,dfn[S],low[S];
int top,sta[S];
bool vis[S];
int tot,idx[S];
vector<int> vec[S];
vector<int> g[S],gg[S];
bool bb[S],flg[S];
int ind[S],hed,til,que[S*5];

inline bool bob(int x)
{
	return x/2&1;
}

void dfs(int u)
{
	low[u]=dfn[u]=++cnt;
	vis[sta[++top]=u]=true;
	for(int v:g1[u])
	{
		if(dfn[v]==0) dfs(v),low[u]=min(low[u],low[v]);
		else if(vis[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u])
	{
		tot++;
		while(1)
		{
			int v=sta[top--];
			vis[v]=false;
			vec[idx[v]=tot].push_back(v);
			if(v==u) break;
		}
	}
}

inline void build()
{
	for(int x=0;x<n;x++)
	{
		int u=idx[x];
		for(int y:g1[x])
		{
			int v=idx[y];
			if(u==v) continue;
			g[u].push_back(v);
		}
	}
}

int main()
{
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	read(n),read(m);
	n*=2;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		read(x),read(y);
		if(x==y) continue;
		x--,y--;
		g1[y].push_back(x);
		g1[x^1].push_back(y^1);
		if(bob(x)==bob(y)) continue;
		if(bob(x)&&x>y) g1[y].push_back(y^1);
		if(bob(y)&&x<y) g1[x^1].push_back(x);
	}
	// for(int i=0;i<n;i++) for(int v:g1[i]) printf("%d %d\n",i,v);
	for(int i=0;i<n;i++) if(dfn[i]==0) dfs(i);
	build();
	for(int i=0;i<n;i+=2) if(idx[i]==idx[i^1]) return puts("Bob"),0;
	for(int i=1;i<=tot;i++)
	{
		if(vec[i].size()==1) bb[i]=bob(vec[i][0]);
		else
		{
			int cnt=0;
			for(int x:vec[i]) cnt+=bob(x);
			bb[i]=cnt>0;
			if(cnt>1) return puts("Bob"),0;
			if(cnt==1)
			{
				sort(vec[i].begin(),vec[i].end());
				if(!bob(vec[i][0])) return puts("Bob"),0;
			}
		}
	}
	// puts("bobo");
	for(int i=1;i<=tot;i++) for(int v:g[i]) gg[v].push_back(i);
	// for(int i=1;i<=tot;i++)
	// {
		// printf("%d %d: %d\n",i,vec[i][0],bb[i]);
	// }
	hed=1,til=0;
	for(int i=1;i<=tot;i++)
	{
		ind[i]=gg[i].size();
		flg[i]=bb[i];
		if(ind[i]==0) que[++til]=i;
	}
	while(hed<=til)
	{
		int u=que[hed++];
		for(int v:g[u])
		{
			flg[v]|=flg[u];
			if(flg[u]&&bb[v]) return puts("Bob"),0;
			if(--ind[v]==0) que[++til]=v;
		}
	}
	puts("Alice");
	return 0;
}