Day50_ 图论1.md

可达路径

问题描述

给定有N个节点的有向无环图，节点编号从1到n,返回从1到n的所有路径。
输入：
第一行输入两个整数，分别表示节点个数和边的个数
以后m行每行给出从节点s到t的一条路径
N M
s1 t1
s2 t2
......
sm tm
输出：每行输出一条路径

思路

图的存储

1.邻接表

vector<list<int>> graph(n+1);
graph[s].push_back(t);

2.邻接矩阵

vector<vector<int>> graph(n+1,vector<int>(n+1,0));
graph[s][t];

实现

#include<iostream>
#include<vector>
#include<list>
using namespace std;vector<vector<int>> vec;
vector<int> path;
void dfs(const vector<vector<int>> & graph,int x,int n){if(x==n){vec.push_back(path);return;}//邻接表写法/*for(int i:graph[x]){path.push_back(x);dfs(graph,i,n);path.pop_back();//抽象}*///邻接矩阵写法for(int i=0;i<=n;i++){if(graph[x][i] == 1){path.push_back(i);dfs(graph,i,n);path.pop_back();}}
}
int main(){int n;int m;int s,t;cin>>n>>m;//邻接表写法// vector<list<int>> graph(n+1);//邻接矩阵写法vector<vector<int>> graph(n+1,vector<int>(n+1,0));while(m--){cin>>s>>t;//邻接表写法//graph[s].push_back(t);//// 邻接矩阵写法：graph[s][t]=1;}path.push_back(1);dfs(graph,1,n);if(vec.size()==0) cout<<-1<<endl;for(const vector<int>& path:vec){for(int i=0;i<path.size()-1;i++){cout<<path[i]<<" ";}cout<<path[path.size()-1]<<endl;}
}

力扣797：https://leetcode.cn/problems/all-paths-from-source-to-target/