# UVA-208 Firetruck （回溯）

```# include<iostream>
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;

int mp[25][25],vis[25],ans;

bool ok(int s,int e)
{
if(s==e)
return true;
vis[s]=1;
for(int i=1;i<=20;++i)
if(mp[s][i]&&!vis[i]&&ok(i,e))
return true;
return false;
}

void dfs(int s,int e,string p)
{
if(s==e){
++ans;
int l=p.size();
for(int i=0;i<l;++i)
printf("%d%c",p[i]-‘A‘+1,(i==l-1)?‘\n‘:‘ ‘);
}
for(int i=1;i<=20;++i){
if(mp[s][i]&&!vis[i]){
vis[i]=1;
dfs(i,e,p+char(‘A‘+i-1));
vis[i]=0;
}
}
}

int main()
{
int n,a,b,cas=0;
while(scanf("%d",&n)!=EOF)
{
memset(mp,0,sizeof(mp));
while(scanf("%d%d",&a,&b)&&a+b)
mp[a][b]=mp[b][a]=1;
printf("CASE %d:\n",++cas);
ans=0;
memset(vis,0,sizeof(vis));
if(ok(1,n)){
memset(vis,0,sizeof(vis));
vis[1]=1;
dfs(1,n,"A");
}
printf("There are %d routes from the firestation to streetcorner %d.\n",ans,n);
}
return 0;
}
```

## Firetruck UVA - 208

DFS+并查集 如果只用DFS的话会超时,用并查集剪枝,和起点终点不联通的点就不用跑了 这题有好多人写了博客,但是我觉得我的代码写的比较通俗易懂所以就贴上来了,我觉得我写代码的目标就是让任何人都能看懂,越小白越好(其实是因为真小白吧-- #include<bits/stdc++.h> using namespace std; int E[30][30]; int diste; int mark[30]; int path[30]; int fin[30]; int ans; int root[

## 【UVa 208】Firetruck

The Center City ?re department collaborates with the transportation department to maintain mapsof the city which re?ects the current status of the city streets. On any given day, several streets areclosed for repairs or construction. Fire?ghters need

## UVa 208 消防车（dfs+剪枝）

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=144 题意:给出一个n个结点的无向图以及某个结点k,按照字典序从小到大顺序输出从1到结点k的所有路径. 思路:如果直接矩阵深搜的话是会超时的,所以我们可以从终点出发,将与终点相连的连通块保存起来,这样dfs深搜时可以剪枝掉一些到达不了的点.只要解决了这个,dfs就是小问题. 这道题还有点坑的