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--) { // 从最大编号开始进行遍历，这里采用了bfsif (!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;
}