P3916 图的遍历 - 洛谷 | 计算机科学教育新生态

题目描述

给出 N 个点，M 条边的有向图，对于每个点 v，求 A(v)表示从点 v 出发，能到达的编号最大的点。

输入格式

第 1 行 2个整数 N,M表示点数和边数。

接下来 M 行，每行2个整数 Ui,Vi表示边 (Ui,Vi)。点用 1,2,…,N 编号。

输出格式

一行 N个整数 A(1),A(2),…,A(N)。

• 对于 60% 的数据，1≤N,M≤10^3。
• 对于 100%的数据，1≤N,M≤10^5。

  #include<iostream>
  #include<vector>
  using namespace std;//本题是图的遍历（简单版）的数据加强版
  //本题数据规模较大，故图的空间和时间消耗较大，需要引入邻接表
  //另外当数据量超过1e5，建议使用scanf、printf进行IO优化
  //本题优化：反向建图，考虑较大的点能到达哪些点 
  const int N = 1e5 + 10;
  vector<int> g[N];//邻接表 
  int n, m;int cnt[N];//记录每个点能搜到的最远点 
  bool vis[N];//标记数组 //cur-当前点，  maxv-最远点 
  void dfs(int maxv, int cur) {if (cnt[cur]) return;//如果cur已经记录最远点，则直接结束 cnt[cur] = maxv; //记录cur的最远点maxv  cnt[3]=3  cnt[4]=4  cnt[2]=4 cnt[1]=4//沿着邻接点搜索 for (auto u : g[cur]) {dfs(maxv, u);}
  }int main() {cin >> n >> m;for (int i = 1; i <= m; i++) {int u, v; scanf("%d %d", &u, &v);g[v].push_back(u);//反向建图 }for (int i = n; i >= 1; i--) {dfs(i, i);//针对每个最远点搜索能到达的点 }for (int i = 1; i <= n; i++) printf("%d ", cnt[i]);return 0;
  }