4 3  1 2  2 4  4 3

4 4 3 4

【题目分析】

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

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

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

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

一个常见的思路是

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

一个常见的技巧是：

• 建反向图（即原图中的边 $\mathrm{<br><br>}$u→v 变成 $\mathrm{<br><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;  }