P6970

zhylj · 2021-11-01 20:54:54 · 题解

也许是个更简洁的做法？

记希望平局玩家的为 A，不希望平局玩家的为 B。

把一个点拆成两个：一个代表此时在这个点且先手是 A，另一个代表先手是 B。不妨称其为 A 类点和 B 类点。

我们考虑如何判断平局：我们已知「出度为 0 的点」代表的状态是不平局，且所有不平局的状态进行下去都必然会在某一刻到达这样的状态。

可以发现，对于 A 类点，只有在其所有出边都是不平局的点时它才会不平局；而对于 B 类点，在它有任意一条边是不平局的点时它就是不平局。于是我们考虑一个做法：从所有出度为 0 的点开始 DFS，当前访问过的节点均为不平局的点。那么，对于假如一个点被访问到，我们就遍历其所有入边对应的点：

• 若其为 A 类点，我们判断其所有边是否都被访问过，若其所有边都被访问过，那么就访问它（类似拓扑排序）。
• 否则其为 B 类点，那么我们可以直接确定其一定为不平局，那么如果它曾经未被访问过，我们就可以直接访问它（类似贪心的思想：我们马上处理它能影响到的点）。

不难证明，如果某一时刻这个操作停止了，那么剩下的点一定是平局的（若不是容易证明其必然被访问过）。

接下来我们考虑如何判断输赢，注意到我们已经确定了「出度为 0 的 A 类点」代表的状态是 B 胜利。我们可以先用上面的 DFS 处理这部分点（即，假装不平局只有这些点），那么此时被访问过的点就是 B 必胜的点了。

时间复杂度 \mathcal O(n+m)，代码很简单。

const int N = 1e5 + 5;

int n, m, dg[N][2], f[N][2], vis[N][2];
std::vector <int> r_E[N];

void Dfs(int u, int typ) {
    vis[u][typ] = true;
    for(int v : r_E[u]) {
        --dg[v][typ ^ 1];
        if(!typ && !vis[v][1]) Dfs(v, 1);
        if(typ && !dg[v][0]) Dfs(v, 0);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i) {
        scanf("%d%d", &u, &v);
        r_E[v].push_back(u);
        ++dg[u][0]; ++dg[u][1];
    }
    for(int i = 1; i <= n; ++i)
        if(!dg[i][0] && !vis[i][0])
            Dfs(i, 0);
    memcpy(f, vis, sizeof(f));
    for(int i = 1; i <= n; ++i)
        if(!dg[i][1] && !vis[i][1])
            Dfs(i, 1);
    for(int t = 0; t < 2; ++t) {
        for(int i = 1; i <= n; ++i)
            printf(vis[i][t] ? ((f[i][t] ^ t ^ 1) ? "W" : "L") : "D");
        printf("\n");
    }
    return 0;
}