题解 | #D 与 S#

简单的博弈论，内测阶段由于疏忽大意慢了一拍太菜了痛失一血。

其实这个逃亡的过程很简单，考虑这么一个结构：

• 如果 $a\to b,a\to ca\backslash rightarrow\; b,\; a\backslash rightarrow\; c$，且 $b,cb,c$ 都可以胜利。

那么先手无论剪哪条边，后手选另外一个边走过去就赢了。

再考虑一个结构：

• 如果 $a\to ba\backslash rightarrow\; b$ 能赢，但是 $aa$ 到其他所有 $c_1,c_2,\cdots ,c_{k}c\_1,c\_2,\backslash cdots,c\_\{k\}$ 都赢不了。

那先手直接剪了 $bb$ 后手就输了。

考虑完了这两个性质之后，其实这道题咱们已经思考完了：

• $\ge 2\backslash ge2$ 个必胜点，可以共同作用于一个“未知胜负”的点，使之变成“必胜”点。

那么咱们直接从最开始的 $kk$ 个必胜点开始，建立反向边，如果某个点被 $\ge 2\backslash ge2$ 个必胜点“直接达到”，那么他也变成必胜点即可。

int main(){
    int T = init();
    while (T--) {
        memset(vis, 0, sizeof(vis));
        memset(du, 0, sizeof(du));
        int n = init(), m = init(), k = init();
        for (int i = 1; i <= n; ++i)
            G[i].clear();
        q[0] = 0;
        for (int i = 1; i <= k; ++i)
            q[++q[0]] = init();
        for (int i = 1; i <= k; ++i)
            vis[q[i]] = 1;
        for (int i = 1; i <= m; ++i) {
            int u = init(), v = init();
            G[u].push_back(v), G[v].push_back(u);
        }
        int nxt = 1;
        while (nxt <= q[0]) {
            int u = q[nxt++];
            for (std::vector<int>::iterator it = G[u].begin(); 
                it != G[u].end(); ++it) { // 反向遍历
                int v = *it;
                ++du[v]; // 度数 + 1
                if (du[v] >= 2 && !vis[v]) { // 如果度数 >= 2，并且它还是未知的，那么就是必胜点
                    vis[v] = 1;
                    q[++q[0]] = v; // 加入队列，继续影响后面的点
                }
            }
        }
        if (vis[1]) puts("yes");
        else puts("no");
    }
}