拓扑排序+dp

小明要去一个国家旅游。这个国家有 N 个城市，编号为 1 至 N，并且有 M 条道路连接着，小明准备从其中一个城市出发，并只往东走到城市 i 停止。

所以他就需要选择最先到达的城市，并制定一条路线以城市 i 为终点，使得线路上除了第一个城市，每个城市都在路线前一个城市东面，并且满足这个前提下还希望游览的城市尽量多。

现在，你只知道每一条道路所连接的两个城市的相对位置关系，但并不知道所有城市具体的位置。现在对于所有的 i，都需要你为小明制定一条路线，并求出以城市 i 为终点最多能够游览多少个城市。

输入格式

第一行为两个正整数 N,M。

接下来 M 行，每行两个正整数 x,y，表示了有一条连接城市 x 与城市 y 的道路，保证了城市 x 在城市 y 西面。

输出格式

N 行，第 i 行包含一个正整数，表示以第 i 个城市为终点最多能游览多少个城市。

输入输出样例

输入 #1复制

5 6
1 2
1 3
2 3
2 4
3 4
2 5

输出 #1复制

1
2
3
4
3

说明/提示

均选择从城市 1 出发可以得到以上答案。

• 对于 20% 的数据，1≤N≤100；
• 对于 60% 的数据，1≤N≤1000；
• 对于 100% 的数据，1≤N≤100000，1≤M≤200000。

//拓扑排序排的就是先后顺序

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int N, M;

    cin >> N >> M;

    vector<vector<int>> adj(N + 1);  // 邻接表

    vector<int> in_degree(N + 1, 0); // 入度

    vector<int> dp(N + 1, 1);        // dp[i] 表示以 i 为终点的最长路径

    for (int i = 0; i < M; ++i) {

        int x, y;

        cin >> x >> y;

        adj[x].push_back(y);  // x -> y

        in_degree[y]++;       // y 的入度 +1

    }

    // 拓扑排序（BFS）

    queue<int> q;

    for (int i = 1; i <= N; ++i) {

        if (in_degree[i] == 0) {

            q.push(i);  // 入度为 0 的节点入队

        }

    }

    while (!q.empty()) {

        int u = q.front();

        q.pop();

        for (int v : adj[u]) {

            // 更新 dp[v]

            if (dp[v] < dp[u] + 1) {

                dp[v] = dp[u] + 1;

            }

            // 减少入度，若为 0 则入队

            if (--in_degree[v] == 0) {

                q.push(v);

            }

        }

    }

    // 输出结果

    for (int i = 1; i <= N; ++i) {

        cout << dp[i] << "\n";

    }

    return 0;

}

for (int v : adj[u]) 是 C++11 引入的范围 for 循环（Range-based for loop），用于遍历容器（如数组、vector、list 等）中的元素。

具体含义

• adj[u] 是一个 vector<int>，存储了所有从节点 u 出发能直接到达的节点（即 u 的邻接节点）。

• for (int v : adj[u]) 表示：

  • 依次取出 adj[u] 中的每一个元素，赋值给变量 v。

  • 然后执行循环体内的代码（如 dp[v] = max(dp[v], dp[u] + 1)）。

等价写法

如果用传统的 for 循环，可以写成：

cpp

复制

下载

for (int i = 0; i < adj[u].size(); ++i) {
    int v = adj[u][i];
    // 循环体
}

或使用迭代器：

cpp

复制

下载

for (vector<int>::iterator it = adj[u].begin(); it != adj[u].end(); ++it) {
    int v = *it;
    // 循环体
}

但 范围 for 循环更简洁，且不易出错（无需手动管理索引或迭代器）。

在该代码中的作用

这段代码是 拓扑排序 + DP 的核心部分：

cpp

复制

下载

for (int v : adj[u]) {
    // 更新 dp[v]
    if (dp[v] < dp[u] + 1) {
        dp[v] = dp[u] + 1;
    }
    // 减少入度，若为 0 则入队
    if (--in_degree[v] == 0) {
        q.push(v);
    }
}

• v 是 u 的直接后继节点（即 u → v 是一条边）。

• 更新 dp[v]：如果从 u 走到 v 能获得更长的路径（dp[u] + 1），则更新 dp[v]。

• 减少 v 的入度：如果 v 的入度变为 0，加入队列（拓扑排序的标准操作）。

示例说明

假设 adj[2] = {3, 4, 5}（即节点 2 有 3 条边：2→3、2→4、2→5），则：

cpp

复制

下载

for (int v : adj[2]) {
    // v 依次为 3、4、5
    // 对每个 v 执行循环体
}

相当于：

cpp

复制

下载

int v = 3; // 第一次循环
dp[3] = max(dp[3], dp[2] + 1);
if (--in_degree[3] == 0) q.push(3);

v = 4;    // 第二次循环
dp[4] = max(dp[4], dp[2] + 1);
if (--in_degree[4] == 0) q.push(4);

v = 5;    // 第三次循环
dp[5] = max(dp[5], dp[2] + 1);
if (--in_degree[5] == 0) q.push(5);

总结

这种写法在 图论算法（如 DFS、BFS、拓扑排序）中非常常见，建议熟练掌握！