Firetruck UVA - 208（并查集+dfs）

2024-02-17 22:48

文章标签 dfs 查集 uva 208 firetruck

本文主要是介绍Firetruck UVA - 208（并查集+dfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

给出终点，然后给出哪两个点连通，注意这里的连通是没有方向的那种连通。然后按字典序输出所有可能从1到终点的路径。

思路

由于1可能到达不了终点，盲目暴力肯定会超时，所以可以先用并查集看1和终点是否连通，然后在开始用dfs打印路径。这里的dfs写法是看一位大佬的写法才豁然开朗。

代码

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;const int maxn = 21;
int pre[maxn];                   // 父节点 
bool G[maxn][maxn];              // 记录两点是否连通
int ans;  
int vis[maxn];
int en;                          // 最终要到达的目标位置
vector<int> res;                 // 保存路径结果int find(int x) {int r = x;int temp;while(r != pre[r])  {r = pre[r];}while(x != r) {              // 路径压缩temp = pre[x];pre[temp] = r;           // 把每一个都连到根节点x = temp;}return r;
}void dfs(int cur)
{if (cur == en){ans++;for (int i = 0; i != res.size(); i++)printf("%d%c", res[i], i == res.size()-1 ? '\n' : ' ');return;}for (int i = 2; i <= 21; i++) {if (!vis[i] && G[cur][i]) {vis[i] = 1;res.push_back(i);dfs(i);vis[i] = 0;res.pop_back();}}
}int main() {freopen("input.txt", "r", stdin);int x, y;int kase = 0;while(~scanf("%d", &en)) {for(int i = 1; i <= maxn; i++) {pre[i] = i;}memset(G, false, sizeof(G));while(scanf("%d%d", &x, &y) && x && y) {G[x][y] = G[y][x] = true;int rx = find(x);int ry = find(y);if (rx != ry) {pre[rx] = ry;   }}ans = 0;printf("CASE %d:\n", ++kase);int fen = find(en);int fbe = find(1);if (fbe != fen) {goto END;     // 用并查集防止超时}memset(vis, 0, sizeof(vis));res.clear();res.push_back(1);vis[1] = 1;dfs(1);END:printf("There are %d routes from the firestation to streetcorner %d.\n", ans, en);}return 0;
}