H. Mad City - 题解

比赛与标签

比赛: Codeforces Round 898 (Div. 4) 标签: dfs and similar, dsu, games, graphs, shortest paths, trees 难度: *1700

题目大意喵~

主人，欢迎来到疯狂之城！这座城市里有 n 座建筑和 n 条双向道路，构成了一张连通的图~

我们的主角是 Marcel 和 Valeriu。Marcel 是追捕者，从 a 点出发；Valeriu 是逃亡者，从 b 点出发。他们的目标是：

• Marcel 想抓住 Valeriu，也就是和他到达同一个建筑，或者在某条路上迎面相遇。
• Valeriu 想永远地逃离 Marcel。

他们每一步都可以移动到相邻的建筑，或者待在原地。最关键的是，Valeriu 非常聪明，他能预测到 Marcel 下一步会去哪里，并利用这个信息来规划自己的行动。

现在需要我们判断，假设双方都采取最优策略，Valeriu 是否有办法永远不被抓住呢？如果可以，就输出 "YES"，否则输出 "NO"，的说。

解题思路大揭秘！

喵哈哈~ 这道题就像一场猫捉老鼠的游戏，不过这次老鼠（Valeriu）特别聪明呢！要解决这个问题，我们得分三步走，喵~

第一步：找到安全的“游乐场”——环！

首先，我们来分析一下这个“疯狂之城”的地图结构。题目说有 n 个点和 n 条边，并且整个图是连通的。主人，你有没有闻到一丝特别的气息？

一个 n 个点的连通图，如果只有 n-1 条边，那它就是一棵树。现在多了 1 条边，就必然会形成一个环！所以，这个城市的结构其实是一个环，环上的某些节点可能还连接着一些“树枝”结构。我们把这种图叫做基环树。

对于 Valeriu 来说，哪里是安全的呢？当然是那个环啦！只要 Valeriu 能成功跑进环里，他就可以绕着圈圈一直跑，Marcel 就像追着自己尾巴的猫猫一样，永远也抓不到他！(ฅ'ω'ฅ)

所以，我们的首要任务就是找出这个环。一个超棒的方法是使用类似拓扑排序的思想：

1. 计算每个节点的度（连接的道路数量）。
2. 把所有度为 1 的节点（也就是“树枝”的末梢）放进一个队列里。
3. 不断从队列里取出节点，并把它“删掉”（逻辑上）。同时，与它相连的邻居节点的度减一。
4. 如果邻居节点的度也变成了 1，就把它也加入队列。
5. 这样一层一层像剥洋葱一样把所有“树枝”都剥掉后，剩下的节点就都是环上的节点啦！

第二步：比赛开始，看谁跑得快！

Valeriu 能不能成功逃脱，完全取决于他能否在被 Marcel 抓住之前，安全地跑到环上。这本质上是一场速度竞赛！

• Marcel 的最优策略：他肯定会走最短的路径去追赶 Valeriu。
• Valeriu 的最优策略：他会利用自己能预知 Marcel 动向的优势，选择一条能最快到达安全区（环）的路径。

所以，我们需要知道 Marcel 和 Valeriu 各自到达地图上任意一点需要的最短时间（步数）。在一个没有边权的图里求最短路，用**广度优先搜索（BFS）**再合适不过了！

• 我们从 Marcel 的起点 a 进行一次 BFS，计算出 da[i]，即 Marcel 到达节点 i 的最短距离。
• 我们再从 Valeriu 的起点 b 进行一次 BFS，计算出 db[i]，即 Valeriu 到达节点 i 的最短距离。

第三步：决定胜负的时刻！

现在，万事俱备！Valeriu 能否逃脱，就看是否存在一个环上的节点 u，使得 Valeriu 能比 Marcel 先到达。

也就是说，我们需要遍历所有在第一步中找到的环上节点 u，检查是否满足 db[u] < da[u]。

• 如果存在至少一个这样的环上节点 u，说明 Valeriu 有一条逃生路线！他可以全速冲向 u，抢在 Marcel 到达之前进入环，然后就可以高枕无忧地开始绕圈跑了。这种情况下，答案就是 "YES"！
• 如果对于所有环上节点 u，都满足 db[u] >= da[u]，那 Valeriu 就太可怜了。他去任何一个环入口的路上都会被 Marcel 截胡或者同时到达。他无法进入安全区，最终会被抓住。这种情况下，答案就是 "NO"。

别忘了，如果 Marcel 和 Valeriu 一开始就在同一个地方（a == b），那游戏直接结束，Valeriu 输了。这也是一个需要处理的小细节哦~

总结一下我们的策略就是：

1. 拓扑排序找环 -> 2. 两次BFS算距离 -> 3. 遍历环上节点判断是否能抢先到达。是不是很清晰了呢？喵~

代码实现喵~

// 完整的AC代码，添加详细注释解释关键逻辑
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    // 提高IO效率，喵~
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n, a, b;
        cin >> n >> a >> b;
        vector<vector<int>> graph(n + 1);
        vector<int> deg(n + 1, 0); // 存储每个节点的度
        for (int i = 0; i < n; i++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
            deg[u]++;
            deg[v]++;
        }

        // 特殊情况：如果一开始就在同一点，Valeriu直接被抓住
        if (a == b) {
            cout << "NO\n";
            continue;
        }

        // 第一步：用类似拓扑排序的方法找出环上的节点
        vector<bool> in_cycle(n + 1, true); // 先假设所有点都在环上
        vector<int> deg_work = deg; // 复制一份度的信息用于操作
        queue<int> q_leaf; // 存储度为1的叶子节点
        for (int i = 1; i <= n; i++) {
            if (deg_work[i] == 1) {
                q_leaf.push(i);
                in_cycle[i] = false; // 度为1的点肯定不在环上
            }
        }

        // 不断移除叶子节点，直到队列为空
        while (!q_leaf.empty()) {
            int u = q_leaf.front();
            q_leaf.pop();
            for (int v : graph[u]) {
                if (in_cycle[v]) { // 只处理还可能是环上节点的邻居
                    deg_work[v]--;
                    if (deg_work[v] == 1) { // 如果邻居也变成了叶子节点
                        q_leaf.push(v);
                        in_cycle[v] = false;
                    }
                }
            }
        }

        // 第二步：从 Marcel 的起点 a 开始 BFS，计算最短距离 da
        vector<int> da(n + 1, -1);
        queue<int> qa;
        da[a] = 0;
        qa.push(a);
        while (!qa.empty()) {
            int u = qa.front();
            qa.pop();
            for (int v : graph[u]) {
                if (da[v] == -1) {
                    da[v] = da[u] + 1;
                    qa.push(v);
                }
            }
        }

        // 第二步：从 Valeriu 的起点 b 开始 BFS，计算最短距离 db
        vector<int> db(n + 1, -1);
        queue<int> qb;
        db[b] = 0;
        qb.push(b);
        while (!qb.empty()) {
            int u = qb.front();
            qb.pop();
            for (int v : graph[u]) {
                if (db[v] == -1) {
                    db[v] = db[u] + 1;
                    qb.push(v);
                }
            }
        }

        // 第三步：检查是否存在 Valeriu 能抢先到达的环上节点
        bool escape = false;
        for (int u = 1; u <= n; u++) {
            // 如果节点 u 在环上，并且 Valeriu 到达 u 的时间比 Marcel 短
            if (in_cycle[u] && db[u] < da[u]) {
                escape = true; // 找到了逃生路线！
                break;
            }
        }

        cout << (escape ? "YES" : "NO") << '\n';
    }

    return 0;
}

复杂度分析的说~

• 时间复杂度: O(N) 的说 对于每个测试用例，建图和计算度是 O(N)。找环的过程，每个节点和每条边最多被访问一次，所以是 O(N)。两次 BFS 分别是 O(N+M)，因为 M=N（边数等于点数），所以也是 O(N)。最后的遍历检查是 O(N)。总的时间复杂度就是 O(N) 啦，非常高效！

• 空间复杂度: O(N) 的说 我们需要 graph 邻接表、deg、in_cycle、da、db 数组来存储图的信息和计算结果，这些都需要 O(N) 的空间。BFS 和找环时用的队列，最多也只会包含所有节点，所以也是 O(N)。总的空间复杂度就是 O(N) 哦。

知识点与小贴士

主人，通过这道题我们又学到了很多东西呢，喵~

1. 图的结构分析: 看到“n个点n条边的连通图”，就要立刻想到它是一棵基环树哦！这是解题的关键突破口呐。
2. 寻找环的方法: 用类似拓扑排序的思想，不断移除度为1的节点，是找出图中环或环上节点的经典技巧。简单又高效！
3. 博弈问题转化: 这道题表面上是博弈论，但通过分析双方的最优策略（都走最短路），我们成功地把它转化成了一个最短路问题。很多博弈题都可以这样简化呢！
4. BFS大法好: 在无权图中求最短路，BFS 永远是你最可靠的伙伴，喵~
5. 换位思考: 解题时要分别站在 Marcel 和 Valeriu 的角度思考他们的最优策略，这样才能找到问题的核心——时间的竞争。

希望这篇题解能帮助到你！继续加油，算法的世界还有更多有趣的冒险等着我们去探索！喵~ (づ｡◕‿‿◕｡)づ