Zielonka 奇偶博弈算法

第一轮试图利用全图最小色m：如果离开它的吸引域以后，对手已经无处可赢，那么己方可以在关键色与剩余获胜区之间安全组合。

若第一次递归真的找到对手获胜区，就不能继续把整个A当作己方。对手的种子Xₒ回到原图后可能吸进A中的顶点，甚至改变其他顶点可用的安全出口。因此必须在原图重新求B，再求G∖B，而不是只把第一次结果机械拼回去。

七顶点触发两次递归 ​

在六顶点例基础上加一个Odd顶点t，优先级3，后继s、a。全部数据如下：

顶层最小色为0，p=Even，U={b}，A={b,d}。第一次递归图H={s,a,c,e,t}的结果为

a可留在1自环；t可主动进a。Odd种子非空，因此回到原图计算 $B={\mathrm{Attr}}_1^G(\{a,t\})=\{a,b,t\}$。b只有后继a，被一并吸入；d有e出口，s有c出口，所以不被吸入。

第二次递归图C={s,c,d,e}中，最小色1在d，当前p变为Odd。Odd吸引域为{d,c,s}：c可选d，s在子图中只剩c。去掉它剩{e}，由Even在优先级2自环获胜；这又触发第二分支。

回到C取Even吸引域Attr₀ᶜ({e})={d,e}，因为d可选e。余下{s,c}只含优先级2，Even获胜。最终C全部由Even赢，顶层返回

递归账本不丢图版本 ​

第二行的B不含t：求Even吸引域时，t归Odd，虽然有一条边到种子s，另一条边仍可去a，所以不能强迫它进入Even种子。表中的集合必须按当前诱导图核算，不能只凭“有一条边到种子”判断。

策略怎样合并 ​

最终Even选择s→c、d→e；Odd选择a→a、t→a，b由Even所有但只有a后继。这给出从整片获胜区统一有效的策略。

合并B上的策略时，Xₒ本身必须保留第一次递归得到的获胜策略。吸引域工具只负责从B∖Xₒ有限步到目标，它对目标中的任意选边没有长期保证。若在Xₒ上也随便覆盖成“某个合法后继”，就可能把已经证明的奇偶策略毁掉。

第一次递归的己方策略也不总能直接用作最终己方策略；第二次递归可能删掉它原本依赖的顶点。代码保留σ′ₒ用于种子，重新计算σ″用于剩余图，正是为了区分这两项用途。

每次非空调用至少删除一个顶点后递归，因此递归深度至多n。一次调用至多两个子调用，最粗的递归树节点数小于2ⁿ⁺¹；用线性队列法计算吸引域及扫描边，每个调用花O(n+m)，得到 $O(2^n(n+m))$ 的宽松上界。算法一般不能被表述成“每种优先级扫一遍”的多项式过程。

若只共享原邻接表，每层保存顶点集合、秩与策略数组，深度优先求解可用 $O(n^2+m)$ 规模的存储；若每次复制诱导边表，空间成本会更大。这里的界描述明确的朴素实现，不借用未实现的优化。

输入若采用max-even，可选偶数D≥maxΩ，先改为Ω′=D−Ω，再执行本页min-even代码。反序但保持奇偶后，两种约定获胜区相同。仅把min改成max而不同时核对证明与优先级方向，会改变输出。

单元终点将在确定规格自动机的积图上重用此算法，交付位置选择以及失败初态的环境反策略，而不把一次发现接受环当成综合完成。