【题目来源】https://www.acwing.com/problem/content/1617/【题目描述】哈密顿回路问题是找到一个包含图中每个顶点的简单回路。这样的回路称为“哈密顿回路”。在本题中你需要做的是判断给定路径是否为哈密顿回路。【输入格式】第一行包含一个整数 N 表示顶点数一个整数 M 表示给定无向图中的边数。接下来 M 行每行包含两个整数 a,b表示点 a 和 b 之间存在一条边。所有顶点编号从 1 到 N。再一行给出整数 K表示询问次数。接下来 K 行每行包含一个询问格式如下n V1 V2 … Vnn 表示给定路径经过的点的数目Vi 是路径中经过的点。【输出格式】对于每个询问如果是哈密顿回路则在一行输出 YES否则输出 NO。​​​​​​​【输入样例】6 106 23 41 52 53 14 11 66 31 24 567 5 1 4 3 6 2 56 5 1 4 3 6 29 6 2 1 6 3 4 5 2 64 1 2 5 17 6 1 3 4 5 2 67 6 1 2 5 4 3 1​​​​​​​【输出样例】YESNONONOYESNO​​​​​​​【数据范围】2N≤200N−1≤M≤N(N−1)/21≤K≤10001≤n≤410【算法分析】● Hamilton 回路是经过图中每个顶点恰好一次并能回到起点的闭合路径。● 欧拉回路是经过图中每条边恰好一次并能回到起点的闭合路径顶点可重复访问。● 一个路径是哈密顿回路必须同时满足1路径长度 n1n 个顶点各走一次最后回到起点多一步2起点 终点3所有顶点都被访问到4中间每个顶点只出现一次5​​​​​​​​​​​​​​相邻两个顶点之间必须有边【算法代码】#include bits/stdc.h using namespace std; const int N2e25; int g[N][N]; bool st[N]; int val[N1]; int n,m; bool check(int cnt) { memset(st,0,sizeof st); if(cnt!n1) return 0; if(val[1]!val[cnt]) return 0; for(int i1; icnt; i) { int uval[i],vval[i1]; if(st[u]) return 0; if(!g[u][v]) return 0; st[u]1; } for(int i1; in; i) { if(!st[i]) return 0; } return 1; } int main() { cinnm; while(m--) { int a,b; cinab; g[a][b]g[b][a]1; } int T; cinT; while(T--) { int cnt; cincnt; for(int i1; icnt; i) cinval[i]; if(check(cnt)) coutYESendl; else coutNOendl; } return 0; } /* in: 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 out: YES NO NO NO YES NO */【参考文献】https://www.acwing.com/solution/content/85416/https://www.acwing.com/solution/content/287515/