526互联

P1137 旅行计划

发布时间 2023-08-11 08:55:27作者: 糖豆爸爸

\(P1137\) 旅行计划

这个题，我们根据题意是不是知道这个是一个\(DAG\)，我们需要计算的是以城市 \(i\) 为终点最多能够游览多少个城市；这个是不是也是在一个拓扑序上做一个简单的\(dp\)就行了，我们记录一下最大值即可；

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 2 * N, INF = 0x3f3f3f3f;

int n, m;

//链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int in[N], f[N];

void topsort() {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (!in[i]) {
            q.push(i);
            f[i] = 1;
        }

    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            f[j] = max(f[j], f[u] + 1);
            in[j]--;
            if (in[j] == 0) q.push(j);
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    for (int i = 1; i <= m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        in[b]++;
    }

    topsort();

    for (int i = 1; i <= n; i++) printf("%d\n", f[i]);

    return 0;
}