有向图游戏

What · 是什么

有向图游戏：给定有向图 G（顶点为状态，边为移动），从起始顶点出发，玩家轮流沿出边移动一步，无法移动者判定胜/负（按规则）。与 Nim/SG 的 DAG 情形不同，这里图允许有环，因此存在平局（双方都不犯错则永不停机）。每个顶点有三种可能：先手必胜（W）、先手必败（L）、平局（D）。分类规则：无出边顶点按规则定 W/L；有出边指向 L 的 → W；所有出边都指向 W 的 → L；其余为 D（无法确定时游戏可在环上无限进行）。O(|V|+|E|) 算法用反图 BFS + 出度递减实现。

Why · 为什么

How · 实现

伪代码

# 输入: n 顶点，adj[u] 出边表，normal=True 表示无法移动者输（反常则取反初始）
outdeg[u] = len(adj[u]); 反图 radj
state[u] = 0 (未定), 1 (W), -1 (L)
queue ← 所有 outdeg==0 的 u，state[u] = -1 (无法移动者输，正常规则)
while queue:
  u = pop()
  for v in radj[u]:
    if state[v] != 0: continue
    if state[u] == -1:
      state[v] = 1; queue.push(v)
    else:
      outdeg[v] -= 1
      if outdeg[v] == 0:
        state[v] = -1; queue.push(v)
剩余 state==0 的顶点 → 平局 D

Python 实现

from collections import deque


def classify_cycles(n, adj, normal=True):
    """任意有向图（可含环）的胜负平局三分类。
    normal=True: 无法移动者输；False: 无法移动者赢（反常）。
    返回 state: 1=先手必胜, -1=先手必败, 0=平局。
    """
    outdeg = [len(adj[u]) for u in range(n)]
    radj = [[] for _ in range(n)]
    for u in range(n):
        for v in adj[u]:
            radj[v].append(u)

    state = [0] * n
    q = deque()
    for u in range(n):
        if outdeg[u] == 0:
            state[u] = -1 if normal else 1
            q.append(u)
    while q:
        u = q.popleft()
        for v in radj[u]:
            if state[v] != 0:
                continue
            if state[u] == -1:
                state[v] = 1
                q.append(v)
            else:
                outdeg[v] -= 1
                if outdeg[v] == 0:
                    state[v] = -1
                    q.append(v)
    return state


if __name__ == "__main__":
    # 无环：0->1->2->3（正常规则）
    s = classify_cycles(4, [[1], [2], [3], []])
    assert s == [1, -1, 1, -1], s

    # 纯环 0<->1：无出度 0 顶点，全部平局
    s2 = classify_cycles(2, [[1], [0]])
    assert s2 == [0, 0], s2

    # 环 1<->2 + 出口 2->3：3 输, 2 赢, 1 所有后继(2)赢→输, 0 赢
    s3 = classify_cycles(4, [[1], [2], [1, 3], []])
    assert s3[3] == -1 and s3[2] == 1 and s3[1] == -1 and s3[0] == 1, s3

    # 反常规则翻转无出边顶点的初值：无环链 0->1->2->3
    s4 = classify_cycles(4, [[1], [2], [3], []], normal=False)
    # 3: 无法移动者赢 → W(1)；2: 后继全 W → L；1: 有后继 L → W；0: L
    assert s4 == [-1, 1, -1, 1], s4

    print("All tests passed.")

易错点

• 有环时不能直接当作 DAG 标记 N/P（残留未定会被误判），必须先跑出度归零流程
• 出度递减要放在 state[u]==1 分支，且检查归零后标 L；state[u]==-1 分支直接标 W 不递减
• 正常/反常规则决定无出边顶点的初值，别统一设 L
• 反图构建必须完整（每条正向边对应一条反向边）
• 平局态的判定是'流程结束仍 state==0'，不是在中间标记
• 多个测试用例共用一个图时 state/outdeg 要重新初始化

例题

信源

• CP-Algorithms✓ https://cp-algorithms.com/game_theory/games_on_graphs.html
• OI Wiki✓ https://oi-wiki.org/math/game-theory/impartial-game/