牛客多校十 - Shannon Switching Game (倒推，bfs)

https://ac.nowcoder.com/acm/contest/33195/F

题意
给定一个 n 个点，m 条边的无向图，可能存在重边，不存在自环。
有一个棋子放在起点 $st$，要走到终点 $en$。

两个人轮流操作，第二个人先操作：

• 第一个人选择棋子相邻的一条边，然后删掉；
• 第二个人选择棋子相邻的一条边，然后走到其另一端点。

第二个人想要把棋子走到终点，而第一个人想要阻止他。两个人都按最佳策略操作。
问，棋子是否能够到达终点？

$1\le T\le 20,n\le 100,1\le m\le 10000,1\le st,en\le n,st!=en$

思路
第二个人想要阻止棋子走到终点，其肯定会把走到终点路径上的边拿掉。而如果一个点走到终点的路径有不少于两条，那么第二人不论拿掉哪条边都不能阻止棋子到达终点。
也就是说，如果有一个点相连了至少两个必胜点的话，那么这个点也是必胜点，如果能够走到这个点，那么第一个人就必胜。

如果正着从起点考虑，并不知道是否该点有两条路径能够到达终点，不能确定当前点相连的是否是必胜点。

反过来，从终点往前推，从终点出发，终点肯定是必胜点。如果一个点能由两个至少两个必胜点到达的话，由双向边，那么这个点往后走就能至少到达两个必胜点，无论切掉哪个边都能到达必胜点，胜利不可阻挡，当前点就是必胜点。

把所有必胜点放到队列里去更新相邻点，如果一个点被走到两次，说明其就是必胜点，放到队列。最后看起点是不是必胜点即可。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];
int st, en;
vector<int> e[N];
int f[N], vis[N];

void bfs()
{
	queue<int> que;
	que.push(en);
	f[en] = 1;
	
	while(que.size())
	{
		int x = que.front(); que.pop();
		
		for(int tx : e[x])
		{
			if(f[tx]) continue;
			vis[tx] ++;
			if(vis[tx] == 2)
			{
				f[tx] = 1;
				que.push(tx);
			}
		}
	}
}

signed main(){
	Ios;
	cin >> T;
	while(T--)
	{
		cin >> n >> m >> st >> en;
		
		for(int i=1;i<=n;i++){
			e[i].clear();
			f[i] = 0;
			vis[i] = 0;
		}
		
		while(m--)
		{
			int x, y; cin >> x >> y;
			e[x].push_back(y);
			e[y].push_back(x);
		}
		
		bfs();
		
		if(f[st]) cout << "Join Player\n";
		else cout << "Cut Player\n";
	}
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

经验
正着复杂的话就想着能不能反着来，正难则反！