UVA208 Firetruck 题解

题目链接：UVA208 Firetruck

题意：

输入一个 \(n(n \le 20)\) 个结点的无向图以及某个结点 \(k\)，按照字典序从小到大顺序输出从结点 \(1\) 到结点 \(k\) 的所有简单路径

怎么随机到这么水的题的啊（

这个题直接 dfs 暴搜就好了。唯一需要注意的是，这道题很无聊的卡了下无解的情况，所以要 bfs 先判一下

时间复杂度 \(\mathcal{O}(\text{ok})\)

代码：（题解区随便扒的）

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX_N = 25;

int target, cnt;
int path[MAX_N];
bool vis[MAX_N];
bool G[MAX_N][MAX_N];

bool BFS()
{
	queue<int> q;

	q.push(1), vis[1] = true;

	while (!q.empty())
	{
		int cur = q.front();
		q.pop();

		if (cur == target) { return true; }

		for (int i = 0; i < MAX_N; ++i)
		{
			if (G[cur][i] && !vis[i])
			{
				vis[i] = true;
				q.push(i);
			}
		}
	}

	return false;
}

void DFS(int step, int node)
{
	if (node == target)
	{
		cnt++;
		printf("1");

		for (int i = 1; i < step; i++) { printf(" %d", path[i]); }

		putchar('\n');
		return;
	}

	for (int i = 0; i < MAX_N; ++i)
	{
		if (G[node][i] && !vis[i])
		{
			vis[i] = true;
			path[step] = i;
			DFS(step + 1, i);
			vis[i] = false;
			path[step] = 0;
		}
	}
}

int main()
{
	int kase = 1;

	while (scanf("%d", &target) == 1 && target)
	{
		int from, to;
		bool flag = true;
		cnt = 0;

		memset(path, 0, sizeof(path));
		memset(vis, false, sizeof(vis));
		memset(G, false, sizeof(G));

		while (scanf("%d%d", &from, &to) == 2 && from && to)
		{
			G[from][to] = G[to][from] = true;
		}

		printf("CASE %d:\n", kase++);

		if (BFS())
		{
			memset(vis, 0, sizeof(vis));
			path[0] = 1, vis[1] = true;
			DFS(1, 1);
		}

		printf("There are %d routes from the firestation to streetcorner %d.\n", cnt, target);
	}

	return 0;
}