题目描述
著名的“汉密尔顿（Hamilton）回路问题”是要找一个能遍历图中所有顶点的简单回路（即每个顶点只访问 1 次）。本题就要求你判断任一给定的回路是否汉密尔顿回路。
输入
首先第一行给出两个正整数：无向图中顶点数 N（2<N≤200）和边数 M。随后 M 行，每行给出一条边的两个端点，格式为“顶点1 顶点2”，其中顶点从 1 到N 编号。再下一行给出一个正整数 K，是待检验的回路的条数。随后 K 行，每行给出一条待检回路，格式为：
n V1 V2 ⋯ Vn
其中 n 是回路中的顶点数，Vi 是路径上的顶点编号。
输出
对每条待检回路，如果是汉密尔顿回路，就在一行中输出"YES"，否则输出"NO"。
输入样例1
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
输出样例1
YES NO NO NO YES NO
思路分析
一开始我的想法是用搜索算法像DFS之类把所有路径都探寻出来然后和输入进行比较，但是把所有路径探寻出来太难了，后来改用正向思维，即，先读取所给的回路，用一个队列去存储，然后每次根据队首两个元素去寻找该路径是否存在，以及判断是否存在已访问过再次访问的情况，最后判断是否有元素未被该回路囊括。
程序还进行了一些预先判断，即如果回路节点小于等于图的节点数，那必然不是汉密尔顿回路，我直接输出NO。
AC代码
代码语言：javascript复制#include<iostream>
#include<queue>
using namespace std;
const int max_vertex_number = 100;
class Map {
int vertex_number = 0, edge_number = 0;
int matrix[max_vertex_number][max_vertex_number];
public:
Map() {
cin >> vertex_number >> edge_number;
int tail, head;
for (int i = 0; i < edge_number; i ) {
cin >> tail >> head;
matrix[tail - 1][head - 1] = matrix[head - 1][tail - 1] = 1;
}
}
void Hamilton() {
bool visited[max_vertex_number] = {false};
queue<int> path;
int vertex;
cin >> vertex;
for (int i = 0; i < vertex; i ) {
int temp;
cin >> temp;
path.push(temp);
}
if (vertex <= vertex_number) {
cout << "NO" << endl;
return;
}
for (int i = 0; i < vertex - 1; i ) {
int head = path.front();
path.pop();
int tail = path.front();
if (matrix[head - 1][tail - 1]&&visited[tail-1]!= true)
visited[tail - 1] = true;
else{
cout<<"NO"<<endl;
return;
}
}
for (int i = 0; i < vertex_number; i )
if (visited[i] == false) {
cout << "NO" << endl;
return;
}
cout << "YES" << endl;
}
};
int main() {
Map test;
int t;
cin >> t;
while (t--)
test.Hamilton();
return 0;
}
