题解：P17235 [Algo Beat Contest 017 D] 图博弈

· · 题解

思路

根据游戏规则，第 n 轮结束后节点 u 上的棋子数，恰好等于从 u 出发、顺着有向边走向 k 且长度恰好为 n 的有向游走数量。

因此，若要满足最终恰好剩 1 枚棋子，上述长度为 n 的有向游走需存在且唯一。

具体而言：

综上，满足条件的局部骨架只能由一个环及一条通向 k 的单向链构成，即一个 \rho 形结构；若 k 位于环上，则链长为 0。

考虑在图中找出一个包含 k 的 \rho 形子图。我们将环定向为一个有向环，并将环到 k 的链统一朝 k 定向。同时，将所有不属于该子图的边沿远离骨架的方向定向，以切断外围节点逆向连入的可能。

具体而言：

可将输入视为无向图。从 k 开始跑单源 BFS 构建生成树，遍历过程中遇到的第一条非树边即可作为闭合环的关键边。若遍历结束未找到非树边，则无解。

接着记录闭合边的两个端点，先将深度较大的节点向上回溯至同一深度，再同步向上回溯至最近公共祖先。在此过程中，将经过的树边定向，从而构成一个有向环。随后从 LCA 沿父亲指针一路回溯至 k，并将经过的边统一朝 k 定向。

最后将所有骨架节点压入队列，进行多源 BFS，将所有未定向边沿 BFS 的扩展方向定向，以防止外围节点重新连入骨架而产生额外棋子。

时间复杂度

单源 BFS 的时间复杂度为 O(n + m)；爬树求 LCA 的时间复杂度为 O(n)；多源 BFS 的时间复杂度为 O(n + m)。总时间复杂度为 O(n + m)。

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 3005, M = 6005;

vector<pair<int, int>> g[N];
int dis[N], fa[N], fe[N];
int U[M], V[M], ans[M], vise[M];

void dir(int id, int u, int v) 
{
    ans[id] = (U[id] == u) ? 0 : 1;
    vise[id] = 1;
}

void solve() 
{
    int n, m, k; 
    cin >> n >> m >> k;

    for (int i = 1; i <= n; i++) 
    {
        g[i].clear();
        dis[i] = -1;
    }

    for (int i = 1; i <= m; i++) 
    {
        cin >> U[i] >> V[i];
        g[U[i]].push_back({V[i], i});
        g[V[i]].push_back({U[i], i});
        vise[i] = 0;
        ans[i] = 0;
    }

    // 寻找环的闭合边
    queue<int> q;
    q.push(k);
    dis[k] = fa[k] = fe[k] = 0;

    int cu = 0, cv = 0, ce = 0;

    while (!q.empty()) 
    {
        int u = q.front();
        q.pop();
        for (auto tmp : g[u]) 
        {
            int v = tmp.first, id = tmp.second;
            if (id == fe[u]) continue; 

            if (dis[v] == -1) 
            {
                dis[v] = dis[u] + 1;
                fa[v] = u;
                fe[v] = id;
                q.push(v);
            } 
            else if (!ce) 
            {
                cu = u; 
                cv = v; 
                ce = id; 
            }
        }
    }

    if (!ce) 
    {
        cout << "No\n"; 
        return;
    }

    // 求 LCA
    dir(ce, cu, cv); 
    int u = cu, v = cv;

    while (dis[u] > dis[v]) 
    {
        dir(fe[u], fa[u], u); 
        u = fa[u]; 
    }

    while (dis[v] > dis[u]) 
    {
        dir(fe[v], v, fa[v]); 
        v = fa[v]; 
    }

    while (u != v) 
    {
        dir(fe[u], fa[u], u);
        dir(fe[v], v, fa[v]);
        u = fa[u]; 
        v = fa[v];
    }

    while (u != k) 
    {
        dir(fe[u], u, fa[u]);
        u = fa[u];
    }

    // 非骨架边隔离
    for (int i = 1; i <= n; i++) dis[i] = -1;
    while (!q.empty()) q.pop();

    dis[k] = 0;
    q.push(k);

    for (int i = 1; i <= m; i++) 
    {
        if (vise[i]) 
        {
            if (dis[U[i]] == -1) 
            {
                dis[U[i]] = 0; 
                q.push(U[i]); 
            }

            if (dis[V[i]] == -1) 
            {
                dis[V[i]] = 0; 
                q.push(V[i]); 
            }
        }
    }

    while (!q.empty()) 
    {
        int u = q.front();
        q.pop();
        for (auto tmp : g[u]) 
        {
            int v = tmp.first, id = tmp.second;
            if (!vise[id]) 
            {
                dir(id, u, v); 
                if (dis[v] == -1) 
                {
                    dis[v] = dis[u] + 1;
                    q.push(v);
                }
            }
        }
    }

    cout << "Yes\n";
    for (int i = 1; i <= m; i++) 
        cout << ans[i];
    cout << "\n";
}

int main() 
{
    cin.tie(0)->sync_with_stdio(0);

    int T; 
    cin >> T;
    while (T--) 
        solve();

    return 0;
}