上一篇博客中我特意介绍了并查集，那么今天就来特意讲一下并查集的一个具体的应用。

题目

先给出传送门：https://vjudge.net/problem/UVA-208

首先先来大概讲一下题目具体的意思，首先题目会给你一个数字k，然后会给好多组数字，这道题的意思就是有一张图结构，给出的n对数据,假设是a和b吧，意思就是a节点和b节点之间有路可以走（无向图，去和来都可以），然后我们还有一个一开始就输入的k数字对吧，题目的意思就是让我们以字典序的顺序输出从1节点到k节点的所有的路径。

题目看似要求并不难，但是这道题对于时间却比较严格，因为数据会出现1到k根本走不通的情况，而且如果你使用普通的DFS去判断联通应该是会超时的，所以我们需要用一个更为简单直接的方法去判联通。

这时候就要用到我们前面所讲的并查集了，每次输入的一组数据都相当于是将两个节点合并，合并到最后就会自然而然地出现一些小的或者大的集合，这样我们只需要去询问起点与终点是否在同一个集合就可以快速判断是否有通路了。而且，当我们使用DFS+回溯的时候，如果这个节点不与起点和终点在同一个集合内，我们就可以忽略这个节点（因为不在同一个集合内肯定就是断路了，根本就不需要考虑）。

其他就是要注意一些细节吧，因为题目中说要按字典序排序，这个其实是非常简单，只要每次从小到大考虑DFS就行了，还有这题需要使用到回溯，所以不要忘记在DFS结束后把vis标记改回来。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;

int far[25],ran[25];
void init(){
    for(int i=0;i<25;i++){
        far[i]=i;
    }
}
int find(int v){
    return far[v]=far[v]==v?v:find(far[v]);
}
void merge(int x,int y){
    int a=find(x),b=find(y);
    if(a==b)
        return;
    if(ran[a]<ran[b]){
        far[a]=b;
    }
    else{
        far[b]=a;
        if(ran[a]==ran[b])
            ++ran[a];
    }
}
bool same(int x,int y){
    return find(x)==find(y);
}

int k,route,root;
int map[25][25];
int ans[25],vis[25];

void dfs(int node,int d){
    ans[d]=node;
    if(node==k){
        for(int i=0;i<=d;i++){
            cout << ans[i]<< (i==d?'\n':' ');
        }
        route++;
        return;
    }
    for(int i=1;i<25;i++){
        if(!vis[i]&&map[node][i]&&find(i)==root) {
            vis[i]=1;
            dfs(i,d+1);
            vis[i]=0;
        }
    }
}

int main(){
    int a,b;
    for(int cas=1;cin>>k;cas++){
        cout << "CASE "<<cas<<":"<<endl;
        route=0;
        memset(map,0, sizeof(map));
        memset(ans,0, sizeof(ans));
        memset(vis,0, sizeof(vis));
        init();
        while(cin>>a>>b&&a&&b){
            map[a][b]=map[b][a]=1;
            merge(a,b);
        }
        if(!same(1,k)){
            cout<< "There are 0 routes from the firestation to streetcorner "<<k<<"."<<endl;
        }
        else{
            root=find(1);
            vis[1]=1;
            dfs(1,0);
            cout <<"There are "<<route<<" routes from the firestation to streetcorner "<<k<<"."<<endl;
        }
    }
    return 0;
}

In The End

UVA208题：消防车（并查集+DFS回溯）

题目

代码