用C++实现
时间: 2023-07-11 15:11:19 浏览: 69
好的,以下是用C++实现的代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
vector<int> graph[100000];
bool visited[100000];
int dfs(int v, int max_id) {
visited[v] = true;
max_id = max(max_id, v);
for (int i = 0; i < graph[v].size(); i++) {
int w = graph[v][i];
if (!visited[w]) {
max_id = max(max_id, dfs(w, max_id));
}
}
return max_id;
}
int main() {
int n, m;
cin >> n >> m;
// 构建邻接表
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u-1].push_back(v-1);
}
// 对每个点进行DFS
for (int i = 0; i < n; i++) {
memset(visited, false, sizeof(visited));
int max_id = dfs(i, i);
cout << max_id+1 << ' ';
}
return 0;
}
```
这里使用了vector来构建邻接表,时间复杂度和空间复杂度同样为O(nm)。