4 3
1 2
2 4
4 3

4 4 3 4

【题目分析】

题目要求对于每个点$\mathrm{<br>}$v，找出从它出发能到达的编号最大的点。

也就是说，如果从v出发，出发可以到达点x1,x2,x3....  那么

R(v)=max(x1,x2,x3.....)

其中也包括$\mathrm{<br>}$v 本身（因为从$v$v 出发至少能到达自己）。

一个常见的思路是

反向图 + 按编号从大到小 BFS

一个常见的技巧是：

• 建反向图（即原图中的边 $\mathrm{<br>}$u→v 变成 $\mathrm{<br>}$v→u）。

• 从编号最大的点 $N$ 开始 BFS，在反向图中能到达的点 $x$，意味着在原图中 $x$能到达 $N$。

• 那么这些点的答案至少是 $N$。

• 然后从 $N-1$开始，如果它还没被访问过，就 BFS，能到达的点答案至少是 $N-1$，但注意如果之前已经赋过更大的值，就不用更新。

• 这样按编号从大到小做 BFS，每个点只会被访问一次，因为一旦被访问，它的答案就已经确定（是当前起点的编号，并且这个编号是递减考虑的，所以第一次访问时就是最大可能值）。

算法步骤：

1. 构建反向图 rG。

2. 初始化答案数组 ans[i] = 0。

3. 从 i = N 到 1：

• 如果 i 还没有被访问过，从 i 开始在反向图上 BFS/DFS。

• 在 BFS 过程中，对于每个到达的点 u，如果它还没被访问过，就设置 ans[u] = i，并标记访问，加入队列。

4. 输出 ans[1..N]。

【参考答案】

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

int main() {
    int N, M;
    cin >> N >> M;

    vector<vector<int>> rG(N + 1);

    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        rG[v].push_back(u);
    }

    vector<int> ans(N + 1, 0);
    vector<bool> visited(N + 1, false);

    for (int i = N; i >= 1; i--) {
        if (visited[i]) continue;

        queue<int> q;
        q.push(i);
        visited[i] = true;
        ans[i] = i;

        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            for (int j = 0; j < rG[cur].size(); j++) {
                int nxt = rG[cur][j];
                if (!visited[nxt]) {
                    visited[nxt] = true;
                    ans[nxt] = i;
                    q.push(nxt);
                }
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        cout << ans[i];
        if (i < N) {
            cout << " ";
        }
    }
    cout << endl;

    return 0;
}