https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=144
题意：给出一个n个结点的无向图以及某个结点k，按照字典序从小到大顺序输出从1到结点k的所有路径。
思路：如果直接矩阵深搜的话是会超时的，所以我们可以从终点出发，将与终点相连的连通块保存起来，这样dfs深搜时可以剪枝掉一些到达不了的点。只要解决了这个，dfs就是小问题。
这道题还有点坑的就是输出格式和它所给的格式不一样，注意一下。
#include<iostream>
#include<cstring>
using namespace std; const int maxn = ; int n, step, route;
int map[maxn][maxn];
int path[maxn];
int vis[maxn];
int trunk[maxn]; void init(int cur) //从终点开始遍历，保存与终点相连的连通块
{
trunk[cur] = ;
for (int i = ; i < maxn; i++)
{
if (map[cur][i] && !trunk[i])
init(i);
}
} void dfs(int cur, int step)
{
if (cur == n)
{
cout << "";
for (int i = ; i < step; i++)
cout << " " << path[i];
cout << endl;
memset(path, , sizeof());
route++;
}
for (int i = ; i < maxn; i++)
{
if (map[cur][i] && !vis[i] && trunk[i])
{
vis[i] = ;
path[step] = i;
dfs(i, step + );
vis[i] = ;
}
}
return;
} int main()
{
//freopen("D:\\txt.txt", "r", stdin);
int a, b, kase = ;
while (cin >> n && n)
{
memset(vis, , sizeof(vis));
memset(map, , sizeof(map));
memset(path, , sizeof(path));
memset(trunk, , sizeof(trunk));
while (cin >> a >> b)
{
if (!a && !b) break;
map[a][b] = map[b][a] = ;
}
vis[] = ;
step = ;
route = ; //记录路径数量
init(n); //计算保存连通块
cout << "CASE " << ++kase << ":" << endl;
dfs(, );
cout << "There are " << route << " routes from the firestation to streetcorner " << n << "." << endl; }
return ;
}