AcWing 1319. 移棋子游戏 SG函数模板题
原题链接
中等
作者:
皓首不倦
,
2020-09-18 00:58:42
,
所有人可见
,
阅读 844
node_num, edge_num, chess_num = map(int, input().split())
link = {i:[] for i in range(1, node_num+1)}
for i in range(edge_num):
a, b = map(int, input().split())
link[a].append(b)
from functools import lru_cache
@lru_cache(typed=False, maxsize=128000000)
def sg(node) -> int:
sg_vals = set()
if len(link[node]) == 0:
return 0
else:
for next_node in link[node]:
sg_vals.add(sg(next_node))
ans = 0
while ans in sg_vals:
ans += 1
return ans
xor_val = 0
nodes = list(map(int, input().split()))
for node in nodes:
xor_val ^= sg(node)
print('win' if xor_val != 0 else 'lose')