G. How Many Paths? - 题解

比赛与标签

比赛: Codeforces Round 731 (Div. 3) 标签: dfs and similar, dp, graphs, trees 难度: *2100

题目大冒险喵~

主人，这次的任务是探索一个有向图G哦！这个图里可能会有自环（自己指向自己的边），但是没有重边（两个点之间同向的边最多一条）。

我们的目标是，对于图中的每一个顶点v，都要弄清楚从起点1号点到v有多少条不同的路径。根据路径数量的不同，我们要输出四种不同的答案呐：

0: 如果从1号点根本走不到v点，一条路都没有的说。
1: 如果从1号点到v点，不多不少，正好只有一条路径。特别注意，从一个点到它自己的空路径（长度为0的路径）也算一条哦！
2: 如果从1号点到v点的路径不止一条，但是是有限的。
-1: 如果从1号点到v点的路径有无限多条！

听起来是不是有点小复杂？别担心，跟着本猫娘的思路，一步一步来，肯定能解决的啦！

解题思路大揭秘！

这个问题最关键的地方在于如何区分“有限路径”和“无限路径”。无限路径是怎么产生的呢？当然是因为图里有环啦！

想象一下，如果从起点1到终点v的某条路径上，经过了一个环，那我们就可以在这个环里一直兜圈子，每兜一圈，就多出一条新的路径。这样一来，到v的路径就变得无限多了，对吧喵？

所以，我们的解题思路可以分成几个清晰的步骤：

步骤一：哪些点是可达的？(0)

最简单的情况！如果一个点v从1号点根本就无法到达，那路径数自然是0啦。我们可以从1号点开始做一次广度优先搜索（BFS）或者深度优先搜索（DFS），标记所有能访问到的点。对于那些没被标记的点，答案就是0！

步骤二：哪些点有无限路径？(-1)

这是最核心的一步！一个点v有无限路径，当且仅当：

1号点可以到达某个点u。
点u在一个环上。
点v可以从点u到达。

简单来说，就是1 -> ... -> u (在环上) -> ... -> v。

如何高效地找到所有在环上的点呢？这就要请出我们的好朋友——强连通分量 (Strongly Connected Components, SCC) 啦！

如果一个强连通分量里有超过一个顶点，那么这些顶点显然都在一个环里。
如果一个强连通分量只有一个顶点，但这个点有自环，那它自己也构成了一个环。

我们把这样的强连通分量称为“非平凡”的。所有在“非平凡”强连通分量里的点，以及所有能从这些点出发到达的点，它们的路径数都是无限的！

所以，我们的策略是：

找出所有从1可达的“非平凡”强连通分量。我们可以用 Kosaraju 算法或者 Tarjan 算法来找 SCC。
将这些“非平凡”SCC中的所有点作为起点，进行一次图遍历（BFS/DFS）。
所有被这次遍历访问到的点，答案都是-1。

步骤三：哪些点路径数是有限的？(1 或 2)

排除了答案是0和-1的点之后，剩下的点都是从1可达，但路径数是有限的。这些点构成的子图一定是一个有向无环图 (DAG)。

在 DAG 上统计路径数，就是动态规划（DP）的经典应用啦！设 dp[v] 为从1到v的路径数。

基础状态: dp[1] = 1 （因为有一条空路径）。
状态转移: 对于任意一个点v，它的路径数等于所有能直接到达它的前驱节点u的路径数之和。也就是 dp[v] = sum(dp[u])，其中 (u, v) 是一条边。

因为我们只关心路径数是1还是>1，所以计算时可以把上限设为2，避免数字过大。转移方程就变成了 dp[v] = min(2, dp[v] + dp[u])。

为了保证在计算dp[v]时，所有的dp[u]都已经被计算好，我们需要按照拓扑序来更新dp值。一个简单的实现方式是，把所有入度为0的点（在这里就是起点1）放入队列，然后进行类似 BFS 的更新。当一个点的dp值更新后，就把它加入队列，继续更新它的后继节点。

总结一下我们的完整计划喵：

BFS/DFS from 1: 找出所有可达点，其余点答案为 0。
SCC on Reachable Subgraph: 在可达点构成的子图上跑 Kosaraju 算法，找到所有强连通分量。
Find Infinite Sources: 标记所有大小 > 1 的 SCC，以及大小为 1 但有自环的 SCC。
Propagate Infinity: 从这些被标记的点出发进行一次图遍历，所有能到达的点答案都是 -1。
DP on DAG: 对剩下的点（答案既不是 0 也不是 -1 的），进行 DP 计算路径数。dp[1] = 1，然后按拓扑序（或用队列模拟）更新 dp[v] = min(2, dp[v] + dp[u])。
Final Output: 根据 dp 数组的值输出 1 或 2。

好啦，思路清晰了，就让我们看看代码是怎么实现的吧！

Paws-on 代码实现！

cpp

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

using namespace std;

// 解决一个测试用例的主函数
void solve() {
    string line; // 用来吃掉测试用例之间的空行
    getline(cin, line);
    
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> g(n + 1), gr(n + 1); // g是原图，gr是反图，为Kosaraju算法做准备
    vector<bool> self_loop(n + 1, false); // 记录每个点是否有自环
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        if (a == b) {
            self_loop[a] = true;
        }
        g[a].push_back(b);
        gr[b].push_back(a);
    }

    // --- 步骤一：找出所有从1可达的点 ---
    vector<bool> reachable(n + 1, false);
    queue<int> q0;
    q0.push(1);
    reachable[1] = true;
    while (!q0.empty()) {
        int u = q0.front(); q0.pop();
        for (int v : g[u]) {
            if (!reachable[v]) {
                reachable[v] = true;
                q0.push(v);
            }
        }
    }

    // --- 步骤二 & 三：在可达子图上找SCC，并识别无限路径源头 ---
    // Kosaraju算法第一步：在原图上DFS，得到拓扑序的逆序（后序遍历）
    vector<int> order;
    vector<bool> visited(n + 1, false);
    for (int i = 1; i <= n; i++) {
        if (reachable[i] && !visited[i]) {
            stack<pair<int, int>> st; // 使用迭代式DFS避免爆栈
            st.push({i, 0});
            visited[i] = true;
            while (!st.empty()) {
                auto [u, ptr] = st.top();
                st.pop();
                bool pushed_child = false;
                for (int j = ptr; j < g[u].size(); ++j) {
                    int v = g[u][j];
                    if (reachable[v] && !visited[v]) {
                        visited[v] = true;
                        st.push({u, j + 1}); // 保存当前进度
                        st.push({v, 0});
                        pushed_child = true;
                        break;
                    }
                }
                if (!pushed_child) {
                    order.push_back(u);
                }
            }
        }
    }
    reverse(order.begin(), order.end()); // 得到拓扑序

    // Kosaraju算法第二步：在反图上按拓扑序的逆序DFS，找出SCC
    fill(visited.begin(), visited.end(), false);
    vector<int> comp(n + 1, -1); // 记录每个点所属的SCC编号
    vector<int> comp_size;       // 记录每个SCC的大小
    int comp_id = 0;
    for (int start_node : order) {
        if (reachable[start_node] && !visited[start_node]) {
            vector<int> current_comp;
            stack<int> st;
            st.push(start_node);
            visited[start_node] = true;
            while (!st.empty()) {
                int u = st.top();
                st.pop();
                current_comp.push_back(u);
                for (int v : gr[u]) {
                    if (reachable[v] && !visited[v]) {
                        visited[v] = true;
                        st.push(v);
                    }
                }
            }
            comp_size.push_back(current_comp.size());
            for (int node : current_comp) {
                comp[node] = comp_id;
            }
            comp_id++;
        }
    }

    // 标记“非平凡”的SCC（即无限路径的源头）
    vector<bool> comp_is_infinite_source(comp_id, false);
    for (int i = 0; i < comp_id; i++) {
        if (comp_size[i] > 1) { // SCC大小>1，必定有环
            comp_is_infinite_source[i] = true;
        }
    }
    for (int i = 1; i <= n; i++) {
        // SCC大小为1，但有自环
        if (reachable[i] && comp[i] != -1 && !comp_is_infinite_source[comp[i]] && self_loop[i]) {
            comp_is_infinite_source[comp[i]] = true;
        }
    }

    // --- 步骤四：传播无限状态 ---
    vector<int> ans(n + 1, 0); // 0:不可达, -1:无限, 1:有限1条, 2:有限>1条
    queue<int> q_inf;
    for (int i = 1; i <= n; i++) {
        if (reachable[i] && comp[i] != -1 && comp_is_infinite_source[comp[i]]) {
            if (ans[i] != -1) {
                ans[i] = -1;
                q_inf.push(i);
            }
        }
    }
    // 从无限源头开始BFS，将所有能到达的点都标记为-1
    while (!q_inf.empty()) {
        int u = q_inf.front(); q_inf.pop();
        for (int v : g[u]) {
            if (reachable[v] && ans[v] != -1) {
                ans[v] = -1;
                q_inf.push(v);
            }
        }
    }

    // --- 步骤五：DP计算有限路径 ---
    vector<int> dp(n + 1, 0);
    if (ans[1] != -1) { // 如果起点1本身不是无限路径点
        dp[1] = 1;
    }
    
    // 按拓扑序进行DP计算
    for (int u : order) {
        if (ans[u] == -1 || dp[u] == 0) continue; // 跳过无限点和从1不可达的有限点
        for (int v : g[u]) {
            if (ans[v] != -1) { // 只更新有限路径的点
                dp[v] = min(2, dp[v] + dp[u]);
            }
        }
    }

    // --- 最终输出 ---
    for (int i = 1; i <= n; i++) {
        if (!reachable[i]) {
            cout << 0;
        } else if (ans[i] == -1) {
            cout << -1;
        } else {
            cout << dp[i];
        }
        if (i < n) cout << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析喵

时间复杂度: O(N + M) 的说。整个算法的每一步，包括BFS找可达点、Kosaraju算法（两次DFS）、BFS传播无限状态、以及最后的DP，都只涉及到对图的顶点和边进行常数次遍历。所以总的时间复杂度是线性的，也就是O(N + M)啦，非常高效！
空间复杂度: O(N + M) 的说。我们需要存储图的邻接表（g和gr），这需要O(N + M)的空间。其他的辅助数组如reachable, visited, dp, ans等，以及DFS/BFS用的栈和队列，都需要O(N)的空间。所以总的空间复杂度也是O(N + M)。

知识点与总结

这次的冒险真是收获满满呀！我们来总结一下学到了什么吧，喵~

问题分解: 面对一个复杂的问题，把它拆解成几个更小的、更容易处理的子问题是王道！我们将路径计数问题分成了“不可达”、“无限路径”、“有限路径”三种情况，逐一击破。
图论大法好:
- BFS/DFS: 解决图上连通性和可达性问题的基本工具，是每个算法探险家必备的技能！
- 强连通分量 (SCC): 识别图中环结构的超级利器！Kosaraju 算法（两遍DFS）和 Tarjan 算法都是实现它的好方法。理解SCC是解决许多有向图问题的关键。
动态规划 (DP): 在有向无环图（DAG）上解决路径、计数等问题时，DP是我们的不二之选。沿着拓扑序进行状态转移，可以保证无后效性，让计算井井有条。
分类讨论: 本题的核心思想就是对图中的点进行分类。根据点与环的关系，将它们划分到不同的集合中，再分别处理。这种思想在很多图论题中都非常有用哦！

希望这次的题解能帮助到大家！只要我们思路清晰，一步一个脚印，再难的题目也无法阻挡我们前进的步伐！大家要继续加油哦，喵~！

G. How Many Paths? - 题解 ​

比赛与标签 ​

题目大冒险喵~ ​

解题思路大揭秘！ ​

步骤一：哪些点是可达的？(0) ​

步骤二：哪些点有无限路径？(-1) ​

步骤三：哪些点路径数是有限的？(1 或 2) ​

总结一下我们的完整计划喵： ​

Paws-on 代码实现！ ​

复杂度分析喵 ​

知识点与总结 ​