DFS寻找从s到t的所有路径

问题描述：

输入一个有向图，输出从s到t的所有路径的结点

输入：
3 3
0 1
1 2
0 2
输出：

0 1 2

0  2

代码：

#include<bits/stdc++.h>
using namespace std;const int N = 103;
vector<int>e[N];//用行为N的，列为可变长度的二维数组表示邻接表 
bool vis[N];//定义访问标记数组 
int path[N],cnt;//path用于记录路径，cnt用于记录路径长度(cnt初值为0，全局变量默认为0)
int n,m;//n为结点数，m为边数 void dfs(int s,int t){//找到从s到t的所有路径vis[s] = 1;//第一件事永远都是把当前结点置为已访问path[cnt++] = s;//把当前结点加入路径中 if(s==t){//如果找到一条从s到t的路径for(int i=0;i<cnt;++i){printf("%d ",path[i]);//打印路径}printf("\n");vis[s] = 0;//回溯操作，如果不回溯，则结果只能找到一条从s到t的路径 cnt--;//回溯 return;}for(int i=0;i<e[s].size();++i){//如果当前还没找到s到t路径，继续访问当前s的下一个邻接点   e.[s].size表示，当前结点s的邻接点的个数 if(!vis[e[s][i]]){//如果第s行，第i个结点没有被访问过，则继续访问 dfs(e[s][i],t);//继续从当前扫描到的结点出发去寻找到t的路径 }}vis[s]=0;//回溯，如果没有找到路径，也要回溯，因为如果访问过s之后，就无法再访问当前这个s结点了，也只会找到一条路径 cnt--;
}int main(void){while(~scanf("%d%d",&n,&m)&&(n||m)){//输入结点数n和边数m for(int i=0;i<n;++i){e[i].clear();//把邻接表中每一行的节点数清空，相当于初始化邻接表 } for(int i=0;i<m;++i){//输入边 int x,y;scanf("%d%d",&x,&y);e[x].push_back(y);//如果是有向图，只需要在x后面连上y即可 //	e[y].push_back(x);如果是无向图，同样也要在y结点后面加上x } dfs(0,n-1);}return 0;
}