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)。

输入输出样例

输入 #1

4 3 1 2 2 4 4 3

输出 #1

4 4 3 4 说明/提示 对于 60% 的数据，1≤N,M≤103。对于 100% 的数据，1≤N,M≤105。

如果简单地dfs遍历，会导致至少一个测试点超时。

题目求的是每个连通分量的最大值，那我们可以考虑反向建图，随后从最大编号节点开始进行遍历。代码如下：

#include<bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; vector<vector<int>> graph(n + 1); vector<int> ans(n + 1); vector<bool> visited(n + 1, false); for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; graph[v].push_back(u); // 反向建图 } for (int i = n; i > 0; i--) { // 从最大编号开始进行遍历，这里采用了bfs if (!visited[i]) { queue<int> q; q.push(i); visited[i] = true; ans[i] = i; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : graph[u]) { if (!visited[v]) { visited[v] = true; ans[v] = i; // 对每个同连通分量的节点的值，更新为当前编号 q.push(v); } } } } } for (int i = 1; i <= n; ++i) { cout << ans[i] << " "; } return 0; }