洛谷P1137题解：拓扑排序与动态规划求解城市游览问题

一、题目解读

洛谷P1137题目要求解决一个基于有向图的旅行计划问题：给定N个城市和M条单向道路，每个城市可游览一次，求每个城市最多能游览多少个连续城市（包括自身）。问题本质是寻找拓扑排序下的最长路径，需利用图论算法与动态规划思想。

二、解题思路

核心思路是将问题转化为拓扑排序与动态规划的结合：

1. 构建有向图：用邻接表存储道路信息，记录每个节点的入度。

2. 拓扑排序：优先处理入度为0的节点，确保遍历顺序正确。

3. 动态规划更新：在拓扑排序过程中，每个节点的最大游览数由其前驱节点的最大值+1决定。

三、解题步骤

1. 输入与初始化：读取N、M，构建邻接表graph与入度数组inDegree，初始化dp数组为1（每个城市至少游览自己）。

2. 入度处理：将入度为0的节点加入队列q，作为拓扑排序起点。

3. 拓扑排序循环：

○ 弹出队首节点u，遍历其邻居v。

○ 更新dp[v] = max(dp[v], dp[u] + 1)，记录最长路径。

○ 若v的入度减为0，则加入队列继续处理。

4. 输出结果：遍历dp数组输出每个城市的最长游览数。

四、代码与注释

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    // 构建图的邻接表表示
    vector<vector<int>> graph(N + 1); // 1-based索引
    vector<int> inDegree(N + 1, 0);   // 记录每个节点的入度

    // 读取道路信息并构建图
    for (int i = 0; i < M; ++i) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y); // x -> y 的有向边
        inDegree[y]++;         // y的入度增加
    }

    // 初始化拓扑排序队列
    queue<int> q;
    vector<int> dp(N + 1, 1); // 每个城市至少能游览自己

    // 将入度为0的节点加入队列
    for (int i = 1; i <= N; ++i) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    // 拓扑排序
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // 遍历u的所有邻居
        for (int v : graph[u]) {
            // 更新v的最大游览城市数
            dp[v] = max(dp[v], dp[u] + 1);

            // 减少v的入度，如果入度为0则加入队列
            if (--inDegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // 输出结果
    for (int i = 1; i <= N; ++i) {
        cout << dp[i] << endl;
    }

    return 0;
}

五、总结

该解法巧妙利用拓扑排序保证遍历顺序，结合动态规划实时更新最优解，时间复杂度为O(N+M)，适用于有向无环图（DAG）场景。掌握拓扑排序与动态规划的协同应用，可高效解决此类路径优化问题。