7-169 汉密尔顿回路 (25 分)
著名的“汉密尔顿（Hamilton）回路问题”是要找一个能遍历图中所有顶点的简单回路（即每个顶点只访问 1 次）。本题就要求你判断任一给定的回路是否汉密尔顿回路。
输入格式：
首先第一行给出两个正整数：无向图中顶点数 N（2<N≤200）和边数 M。随后 M 行，每行给出一条边的两个端点，格式为“顶点1 顶点2”，其中顶点从 1 到N 编号。再下一行给出一个正整数 K，是待检验的回路的条数。随后 K 行，每行给出一条待检回路，格式为：
n V1 V2 ⋯ Vn
其中 n 是回路中的顶点数，Vi 是路径上的顶点编号。
输出格式：
对每条待检回路，如果是汉密尔顿回路，就在一行中输出"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
输出样例：
1. YES 2. NO 3. NO 4. NO 5. YES 6. NO
#include<iostream> using namespace std; int N ,M ,K ,n ,n1 ,n2 ,v ,start ,pre; int link[201][201]; int main() { cin >> N >> M; for (int i = 0; i < M; ++i) { cin >> n1 >> n2; link[n1][n2] = link[n2][n1] = 1; } cin >> K; for (int j = 0; j < K; ++j) { cin >> n; //int flag = (n != N + 1) ,vis[201] = {0}; int flag = 0 ,vis[201] = {0}; if (n != N + 1) { flag = 1; } for (int i = 0; i < n; ++i) { cin >> v; if (i == 0) start = v; else if (!link[pre][v]) flag = 1; if (vis[v] && (i != n - 1 || v != start)) flag = 1; pre = v; vis[v] = 1; } // cout << (flag ? "NO" : "YES") << endl; if (flag) cout << "NO" << endl; else cout << "YES" << endl; } return 0; }
