洛谷P1137 旅行计划 题解

题目链接：P1137 旅行计划

题意：

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

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

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

输入格式：

第\(1\)行为两个正整数 \(N, M\) 。

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

输出格式：

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

数据范围：

\(1\le N \le 10^5,~M \le 2\times 10^5\)。

设 \(f_u\) 为结点 \(u\) 的答案，拓扑排序更新答案即可。 \[ f_v \uparrow f_u + 1 \] 时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))
#define M ((int)(2e5+15))

queue<int> q;
int n,m,pos=1,f[N],head[N],in[N];
struct Edge{ int u,v,next; } e[M];
void addEdge(int u,int v)
{ e[++pos] = {u,v,head[u]}; head[u] = pos; ++in[v]; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1,u,v; i<=m; i++) { cin >> u >> v; addEdge(u,v); }
    for(int i=1; i<=n; i++) if(!in[i]) { q.push(i), f[i] = 1; }
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int i=head[u]; i; i=e[i].next)
        {
            int v = e[i].v; up(f[v], f[u] + 1);
            if(!(--in[v])) { q.push(v); }
        }
    }
    for(int i=1; i<=n; i++) cout << f[i] << '\n';
    return 0;
}