赞
踩
深度搜索
广度搜索
给定一个有 n 个节点的有向无环图,节点编号从 1 到 n。请编写一个函数,找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。
输入描述
第一行包含两个整数 N,M,表示图中拥有 N 个节点,M 条边
后续 M 行,每行包含两个整数 s 和 t,表示图中的 s 节点与 t 节点中有一条路径
输出描述
输出所有的可达路径,路径中所有节点之间空格隔开,每条路径独占一行,存在多条路径,路径输出的顺序可任意。如果不存在任何一条路径,则输出 -1。
注意输出的序列中,最后一个节点后面没有空格! 例如正确的答案是 1 3 5
,而不是 1 3 5
, 5后面没有空格!
# include <iostream> # include <vector> using namespace std; vector<vector<int> > result; vector<int> path; void dfs(vector<vector<int> > graph, int now, int end) { //path.push_back(now); if (now == end) { result.push_back(path); //path.pop_back(); return; } for (int node: graph[now]) { path.push_back(node); dfs(graph, node, end); path.pop_back(); } //path.pop_back(); } int main() { int n, m; cin>> n >>m; vector< vector<int> > graph(n + 1, vector<int> (0)); for (int i = 0; i < m; i++) { int start, end; cin >> start >> end; graph[start].push_back(end); } path.push_back(1); dfs(graph, 1, n); for (vector<int> paths : result) { for (int i : paths) { cout<< i ; if (i != n) cout<< " "; } cout <<endl; } if (result.size() == 0) cout << -1; }
# include <iostream> # include <vector> # include <queue> using namespace std; int main() { int n, m; cin>> n >>m; vector<vector<int> > result; vector<vector<int> > graph(n + 1, vector<int> (0)); for (int i = 0; i < m; i++) { int start, end; cin >> start >> end; graph[start].push_back(end); } queue<vector<int> > que; vector<int> path(1, 1); que.push(path); while(que.size() > 0) { int size = que.size(); for (int i = 0; i < size; i++) { path = que.front(); if (path[path.size() -1] == n) { result.push_back(path); que.pop(); }else { que.pop(); for (int i : graph[path[path.size() - 1]]) { path.push_back(i); que.push(path); path.pop_back(); } } } } for (vector<int> paths : result) { for (int i : paths) { cout<< i ; if (i != n) cout<< " "; } cout <<endl; } if (result.size() == 0) cout << -1; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。