（判连通+暴力）UVA

原题链接：

比较麻烦，就不挂，可以上uva live找，也可以用virtual judge挂题。

---

题意：

输出从1到k的所有路径，不能重复经过

---

分析：

这题就是简单的深搜回溯，用一个数组记录路径，满足条件时输出。紫书上说需要先判断1到k是否联通，不然会超时。交了一发直接深搜，果然TLE。所以需要先判连通。

判连通的方法有（能想到的）：

1、dfs和bfs，两者感觉差不多，但是我选择的bfs

2、floyd，n^3的复杂度，但更加粗暴直接，也更好写

3、待添加

---

感悟：

不预先判连通3000ms超时，判了连通就0ms秒AC，感慨啊。

---

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <queue>
#include <cmath>
#include <stack>
#include <cctype>
#include <list>

#define ll long long
#define ull unsigned long long
#define VNAME(name) (#name)
#define debug(a) cout<<VNAME(a)<<" = "<<(a)<<endl;

using namespace std;

const int maxn = 100010;
const int inf = 1 << 30;
int k;
vector<int> edge[22];
queue<int> q;
bool vis[22];
int road[22];
int sum;

void init() {
    memset(vis,0,sizeof(vis));
    for(int i=0; i<22; i++) {
        edge[i].clear();
    }
    sum=0;
}

//一个很标准的宽搜
bool bfs(int v) {
    bool mark[22]= {0};
    while(!q.empty())q.pop();
    q.push(v);
    mark[v]=1;
    while(!q.empty()) {
        int s=q.front();
        q.pop();
        if(s==k)return true;//找到k点，返回
        for(int i=0; i<edge[s].size(); i++) {
            if(!mark[edge[s][i]]) {
                q.push(edge[s][i]);
                mark[edge[s][i]]=1;
            }
        }
    }
    return false;
}


void dfs(int v,int cnt) {
    road[cnt]=v;//记录路径
    if(v==k) {
        for(int i=0; i<cnt; i++) {
            printf("%d ",road[i]);
        }
        printf("%d
",road[cnt]);
        sum++;//记录路径数量
        return ;
    }
    for(int u=0; u<edge[v].size(); u++) {
        if(!vis[edge[v][u]]) {
            vis[v]=1;//标记原点
            dfs(edge[v][u],cnt+1);
            vis[v]=0;//回溯
        }
    }
}

int main() {
    //iostream::sync_with_stdio(false);

#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
#endif

    int kace=0;
    while(~scanf("%d",&k)) {
        init();//预处理清空
        int v,u;
        while(scanf("%d%d",&v,&u)) {
            if(v==0&&u==0)break;
            edge[v].push_back(u);
            edge[u].push_back(v);//无向图双向连边
        }
        for(int i=0; i<22; i++) {
            sort(edge[i].begin(),edge[i].end());//排序，可以很方便的让dfs出来的路径按字典序排列
        }
        printf("CASE %d:
",++kace);
        if(bfs(1))dfs(1,0);//如果连通，开始深搜
        printf("There are %d routes from the firestation to streetcorner %d.
",sum,k);
    }
    return 0;
}