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;
}