洛谷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;
}