python - 查找遍历游戏中获胜者的算法

我们将使用图表和两个玩家。在这个连通图中，获胜的条件是第二个玩家没有其他路径可走关键是一旦一条路被一个玩家走了，就不能再走了。
假设初始输入是邻接列表（x，y）意味着x有到y的路径
目标是返回一组顶点，玩家1可以选择这些顶点，这样它将始终获胜。
例如，如果我有[(1,2), (2,0), (0, 3), (3,2)]并且player 1启动，那么我们应该返回[1, 0, 3]我们不能返回：
2-->播放机1从这里开始
（2,0）-->玩家2转到0
（0,3）-->玩家1转到3
（3,2）-->玩家2转到2
（2,0）-->玩家1不能到这里，已被占领

already_visited = []

turn = 1

result = []

def findStarting(L):
    global already_visited
    global turn
    global result

    for x,y in L:
        allowed = can_visit(L, y) # function tell me which I can visit safely

        turn = (turn % 2) + 1 # increment the turn

        already_visited.append((x,y)) # we visited this edge

        res = findStarting([(x, y)]) # recursive call (search on this node for paths)


    if (turn == 2): return True

def can_visit(L, y):
    res = []
    for a,b in L: if (a==y and (a,b) not in already_visited): res.append((a,b))
    return res

我对递归的情况有困难我想我要做的是返回2如果我们到达一个转折点是2并且玩家没有他们可以走的路，但是我不确定如何从这里向前移动

最佳答案

这是一个简单的递归解决方案它不是有效的，它是没有任何中间状态缓存的蛮力搜索，所以它肯定可以更快，尽管我不知道是否有一个有效的（即非指数）解决方案来解决这个问题。

def firstPlayerWins(g,v):
  for i,e in enumerate(g):
    if e[0]==v and not firstPlayerWins(g[:i]+g[i+1:],e[1]):
        return True
  return False

def winningVertices(g):
  return [v for v in set(e[0] for e in g) if firstPlayerWins(g,v)]

winningVertices([(1,2), (2,0), (0, 3), (3,2)])
## [0, 2, 3]