对于这个有向图,找出并输出每个节点能到达的最远节点C++实现
时间: 2024-02-12 18:06:48 浏览: 20
这个问题可以使用深度优先搜索(DFS)来解决。从每个节点开始进行DFS,记录能够到达的最远节点,最终输出每个节点能到达的最远节点即可。
下面是C++实现:
```c++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
void dfs(int u, vector<vector<int>>& graph, vector<bool>& visited, vector<int>& farthest) {
stack<int> s;
s.push(u);
visited[u] = true;
while (!s.empty()) {
int v = s.top();
s.pop();
for (int i = 0; i < graph[v].size(); i++) {
int w = graph[v][i];
if (!visited[w]) {
visited[w] = true;
s.push(w);
farthest[w] = farthest[v] + 1;
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
}
vector<int> farthest(n, 0);
for (int i = 0; i < n; i++) {
vector<bool> visited(n, false);
dfs(i, graph, visited, farthest);
}
for (int i = 0; i < n; i++) {
cout << "Node " << i << " can reach farthest node " << farthest[i] << endl;
}
return 0;
}
```
首先,读入有向图并构建邻接表,然后从每个节点开始进行DFS。在DFS过程中记录每个节点能够到达的最远节点farthest,最后输出每个节点能到达的最远节点即可。
注意,为了避免使用递归的DFS方式在大规模图上可能导致栈溢出,我们在此处使用了栈来实现DFS。