旅行计划(Travel Plan) 题解

思路分析

所有道路均由西指向东，构成一张有向无环图（DAG）。由于可以从任意城市出发，初始令所有城市的 dp[i] = 1；使用 Kahn 算法进行拓扑排序，每从队首取出城市 $u$，遍历所有出边 $u \to v$ 更新 dp[v] = max(dp[v], dp[u] + 1)，并在 inDeg[v] 减为 $0$ 时将 $v$ 入队。最终 dp[1..N] 即为以各城市为终点的最多游览城市数。时间复杂度 $O(N + M)$。

参考代码

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

const int MX = 100005;
vector<int> adj[MX];
int inDeg[MX], dp[MX];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    for (int i = 0; i < m; ++i)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        inDeg[v]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; ++i)
    {
        dp[i] = 1;
        if (inDeg[i] == 0) q.push(i);
    }
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int v : adj[u])
        {
            if (dp[u] + 1 > dp[v]) dp[v] = dp[u] + 1;
            if (--inDeg[v] == 0) q.push(v);
        }
    }
    for (int i = 1; i <= n; ++i) cout << dp[i] << "\n";
    return 0;
}