Alice 和 Bob 在一张有向图 G=(V,E) 上玩游戏，初始时，在某个顶点 s0 上有一枚石子。
每当轮到某个玩家操作时，设石子在顶点 u，则她需要选择顶点 v 满足 (u→v)∈E，然后将石子从 u 移到 v。如果找不到这样的顶点 v，则该玩家输掉游戏。
可以发现，游戏一共有三种状态：Alice 赢 (Bob 输)、Bob 赢 (Alice 输) 和无限进行 (平局)。
她们对这三种状态的排名是不相同的：Alice 最希望无限进行，其次是 Alice 赢，最后是 Bob 赢。Bob 最希望 Bob 赢，其次是 Alice 赢，最后是无限进行。
两个人严格会按照上述策略进行 (如，若 Alice 能使游戏无限进行，她决不会赢；同理，若 Bob 能输，她决不会使游戏无限进行)。
求对于每个 s0∈V，当 Alice 先手和 Bob 先手时，最终游戏的状态。
第一行包含两个正整数 n,m (n≤105;m≤2×105)，分别表示图 G 的顶点数和边数。
接下来 m 行，每行两个正整数 a,b (1≤a,b≤n)，表示一条从顶点 a 指向顶点 b 的边。保证 G 中没有重边，但可能有自环。
输出两行，每行一个字符串，分别记为 A,B。每个字符为 W,L,D 之一，分别表示先手赢，后手赢和无限进行。其中 Ai 表示当 Alice 先手且 s0=i 时，游戏最终的状态，Bi 表示当 Bob 先手且 s0=i 时，游戏最终的状态。
用 vA 表示现在石子在 v 处且下一步轮到 Alice 的状态，vB 同理。显然，我们就是要得到每个 vA 和 vB 的 (最终) 状态 (Alice 赢，Bob 赢，无限进行)
根据图论的传统定义，用 N+(v) 表示 v 通过一条边可以到达的顶点集合。
对于 N+(vA)，规定里面的元素为下一步轮到 Bob 的状态，N+(vB) 里的元素都是下一步轮到 Alice 的状态。
我们考虑一个状态什么时候可以无限进行。
uA 是无限进行的充分必要条件是，存在 vB∈N+(uA)，使得 vB 是无限进行。
uB 是无限进行的充分必要条件是，N+(uB)≠∅ 且对于每个 vA∈N+(uB)，都有 vA 是无限进行。
(充分性显然，对于必要性，若 N+(uB)=∅，显然 uB 是 Alice 赢。若存在 vA∈uB 使得 vA 不是无限进行，那么 B 肯定会将石子从 v 移到 u)
首先，对于 d+(v)=0 (出度为零) 的顶点 v，显然 vA,vB 都是后手赢，总之，不是无限进行。
考虑根据有向图博弈的经验，按照拓扑序的逆序进行更新。根据之前粉色的结论，对于边 uB→vA，如果 vA 不是无限进行，则可得 uB 不是无限进行；对于 uA→vB，如果所有的 vB 都不是无限进行 (即像拓扑排序一样没入度了)，则 uA 也被确定为无限进行。
于是，通过上述算法，我们可以得到若干不是无限进行的点。那剩下的点是否一定是无限进行呢？答案是肯定的，证明如下：
设剩下的点的集合为 R。考虑 uA∈RA，先证明 uA 是无限进行。
首先，由算法的过程知，N+(uA)∩RB≠∅，因此存在 vB∈N+(uA)∩RB。
而因为 vB∈RB，则由算法的过程知 ∅⊂N+(vB)⊆RA，于是 B 不会输，且无论 B 如何决策，下一步时石子仍在 R 中。
于是 Alice 就有主动权了，她有能力保持游戏无限进行。从而 uA 是无限进行。
对于 uB∈RB，可以发现 Bob 无论如何只能走向 RA 中的点，于是转化为 Alice 先手的情形，由上面分析知该情形是无限进行的。这说明 uB 的所有后继状态都是无限进行，由粉色结论知 uB 本身也是无限进行。
从而我们可以在 O(n+m) 的时间内得到每个点是否是无限进行。
接下来，考虑一个非无限进行的状态是 Alice 赢还是 Bob 赢。
我们将所有无限进行的状态从图中删去，得到新图 G′。
此时，我们就可以按照传统的有向图博弈的方法去更新了：若一个点存在先负的后继状态，则它一定是先胜；若一个点的所有后继状态都是先胜 (含没有后继状态)，则它是先负。
于是还是按照拓扑序的逆序更新即可。当然这里要对于每个顶点 v 同时记录 vA 的剩余入度和 vB 的剩余入度。
但是，G′ 也不一定是 DAG，因此如果最后遇到了圈，那些点的状态又如何呢？
设剩下的点的集合为 S。考察 uA∈SA，则 N+(uA) 要么在 S 中，要么是 Bob 赢。同理，对 uB∈SB，N+(uB) 中的元素也是要么在 S 中，要么是 Alice 赢。
我们证明，这些点的状态都是 Alice 赢。
反证法。假设有一个点不是 Alice 赢。
首先，显然 S 中的点不可能无限进行，因此它只可能是 Bob 赢。
于是，Bob 存在必胜策略。这个必胜策略显然存在一步会离开集合 S，离开集合 S 分为两种情况：
Bob 主动离开集合 S。
而对于 uB∈SB，N+(uB)∖S 中的所有元素都是 Alice 赢，矛盾。
Alice 被 Bob 逼着离开集合 S。
而对于 uA∈SA，一定有 N+(uA)∩S=∅。否则由算法的过程知 uA 就不应该属于 S。
从而 Alice 存在一种策略，使得永远不会被 Bob 逼着离开 S，该情况也矛盾。
这说明，假设 Bob 赢是错误的，又这里的点不可能无限进行，于是这些点都是 Alice 赢。
这样我们就确定了所有的点最终的状态，整个算法只需要两次 bfs (类似拓扑排序)，故时间复杂度 O(n+m)。
#include <bits/stdc++.h>
using std::cin;
using std::cout;
const int N = 100054, M = N * 2;
struct edge {
int u, v;
edge (int u0 = 0, int v0 = 0) : u(u0), v(v0) {}
} e[M];
int V, E;
int first[N], next[M];
int deg[N], Deg[N], que[M];
bool leaf[N];
char alice[N], bob[N];
inline void addedge(int u, int v, int id) {e[id] = edge(u, v), next[id] = first[u], first[u] = id;}
void solve_infinity() {
int i, h, t = 0, x, y;
for (i = 1; i <= E; ++i) ++deg[e[i].v];
for (i = 1; i <= V; ++i) if ((leaf[i] = !deg[i])) alice[i] = bob[i] = 1, que[t++] = i, que[t++] = -i;
for (h = 0; h < t; ++h)
if ((x = que[h]) > 0) {
for (i = first[x]; i; i = next[i])
if (bob[y = e[i].v] == 68) bob[y] = 1, que[t++] = -y;
} else
for (i = first[-x]; i; i = next[i])
if (!--deg[y = e[i].v]) alice[y] = 1, que[t++] = y;
}
void solve_winlose() {
int i, h, t = 0, x, y;
for (i = 1; i <= E; ++i) {
if (alice[e[i].u] == 1) ++deg[e[i].v];
if (bob[e[i].u] == 1) ++Deg[e[i].v];
}
for (i = 1; i <= V; ++i) if (leaf[i]) alice[i] = bob[i] = 76, que[t++] = i, que[t++] = -i;
for (h = 0; h < t; ++h)
if ((x = que[h]) > 0) {
for (i = first[x]; i; i = next[i]) if (bob[y = e[i].v] != 68) {
if (alice[x] == 76) {
if (bob[y] == 1) bob[y] = 87, que[t++] = -y;
} else {
if (!--deg[y]) bob[y] = 76, que[t++] = -y;
}
}
} else
for (i = first[-x]; i; i = next[i]) if (alice[y = e[i].v] != 68) {
if (bob[-x] == 76) {
if (alice[y] == 1) alice[y] = 87, que[t++] = y;
} else {
if (!--Deg[y]) alice[y] = 76, que[t++] = y;
}
}
std::replace(alice + 1, alice + (V + 1), 1, 87),
std::replace(bob + 1, bob + (V + 1), 1, 76);
}
int main() {
int i, u, v;
std::ios::sync_with_stdio(false), cin.tie(NULL);
cin >> V >> E;
for (i = 1; i <= E; ++i) cin >> u >> v, addedge(v, u, i);
memset(alice + 1, 68, V), memset(bob + 1, 68, V),
solve_infinity(), solve_winlose();
cout << alice + 1 << '\n' << bob + 1 << '\n';
return 0;
}
坑1：粉色条件中的 2 不要忘记 N+(uB)=∅，度数为 0 的点一定是先手必败的。
坑2：点的度数要利用多次，因此不要把上次拓扑排序更改后的 deg 拿来用。