作者：手机用户2602929101 | 来源：互联网 | 2024-12-23 21:02
哈密顿回路问题的目标是找到一条简单回路，使得该回路经过图中的每一个顶点恰好一次，并最终回到起点。这种回路被称为哈密顿回路。
在本题中，你需要编写一个程序来判断给定的路径是否为哈密顿回路。
输入格式:
输入文件包含多组测试数据。每组数据的第一行包含两个正整数 N 和 M，分别表示无向图中的顶点数和边数（2 ≤ N ≤ 200）。接下来的 M 行，每行描述一条边，格式为 Vertex1 Vertex2，顶点编号从 1 到 N。随后的一行给出一个正整数 K，表示查询次数，接下来的 K 行，每行包含一个查询，格式为：
n V1 V2 ... Vn
其中 n 表示路径上的顶点数，V1, V2, ..., Vn 是路径上依次经过的顶点。
输出格式:
对于每个查询，如果路径形成哈密顿回路，则输出 YES；否则输出 NO。
样例输入:
6 10
6 2
3 4
1 5
2 5
3 1
4 1
1 6
6 3
1 2
4 5
6
7 5 1 4 3 6 2 5
6 5 1 4 3 6 2
9 6 2 1 6 3 4 5 2 6
4 1 2 5 1
7 6 1 3 4 5 2 6
7 6 1 2 5 4 3 1
样例输出:
YES
NO
NO
NO
YES
NO
为了验证路径是否为哈密顿回路，需要满足以下条件：
- 遍历的所有顶点数量必须等于 N+1，因为路径需要遍历所有顶点并返回起点。
- 最后一个顶点必须是起点。
- 使用布尔数组
visit 记录每个顶点是否已被访问过。
- 使用二维数组
graph 记录图中各顶点之间的连通性。
1 #include
2 #include
3 using namespace std;
4 int main()
5 {
6 int n, m, k, a, b, start;
7 bool visit[205];
8 int graph[205][205];
9 fill_n(graph[0], 205 * 205, -1);
10 cin >> n >> m;
11 while (m--) {
12 cin >> a >> b;
13 graph[a][b] = graph[b][a] = 1;
14 }
15 cin >> k;
16 while (k--) {
17 cin >> m;
18 bool flag = true;
19 fill_n(visit, 205, false);
20 for (int i = 0; i 21 cin >> b;
22 if (!flag || m != n + 1) {
23 flag = false;
24 continue;
25 }
26 if (i == 0)
27 start = b;
28 else if (graph[a][b] != 1)
29 flag = false;
30 else if (i == m - 1 && b != start)
31 flag = false;
32 else if (i != m - 1 && visit[b])
33 flag = false;
34 else
35 visit[b] = true;
36 a = b;
37 }
38 if (flag) {
39 for (int i = 1; i <= n && flag; ++i)
40 if (!visit[i])
41 flag = false;
42 if (flag)
43 cout <<"YES" <44 }
45 if (!flag)
46 cout <<"NO" <47 }
48 return 0;
49 }
京公网安备 11010802041100号