用数据结构c++处理:给定 � n个点, � m条边的有向图,对于每个点 � v,求 � ( � ) f(v)表示从点 � v出发能到达的编号最大的点(包括自己在内)。 � , � ≤ 1 0 5 n,m≤10 5 Input Format 第一行有 2 2个整数 � n, � m。 接下来 � m行,每行2个整数 � � , � � u i ,v i ,表示 � � u i 到 � � v i 有一条边。 点用 1 , 2 , ⋯ , � 1,2,⋯,n编号。 Output Format数据结构c++
时间: 2023-07-15 22:11:39 浏览: 107
可以使用邻接表来存储有向图,然后对于每个点,进行一次DFS或BFS遍历,记录能够到达的最大编号的点。
具体实现可以参考以下代码:
```c++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 1e5 + 5;
vector<int> adj[MAXN];
int n, m;
bool visited[MAXN];
// DFS遍历
int dfs(int v) {
int res = v;
visited[v] = true;
for (int i = 0; i < adj[v].size(); i++) {
int u = adj[v][i];
if (!visited[u]) {
int tmp = dfs(u);
if (res < tmp) res = tmp;
}
}
return res;
}
// BFS遍历
int bfs(int v) {
int res = v;
queue<int> q;
q.push(v);
visited[v] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < adj[u].size(); i++) {
int w = adj[u][i];
if (!visited[w]) {
visited[w] = true;
q.push(w);
if (res < w) res = w;
}
}
}
return res;
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
for (int v = 1; v <= n; v++) {
// 初始化visited数组
for (int i = 1; i <= n; i++) visited[i] = false;
// DFS或BFS遍历
int max_id = dfs(v); // or bfs(v)
cout << max_id << endl;
}
return 0;
}
```
阅读全文