1122 Hamiltonian Cycle (25分)

题目链接：1122 Hamiltonian Cycle (25分)

题意：

给出路径，判断是否为Hamiltonian cycle ，就是一个联通圆环，N个顶点N条边。

分析

路径顶点个数只能为N+1，并且要判断是否联通，满足这个条件的就输出YES。联通可以输入时判断是否有两个顶点的边，然后在判断是否N个顶点都出现过。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
const int maxn = 210;
int graph[maxn][maxn] = {
    0};
int book[maxn];
int main(int argc, char** argv) {
    int n, m, x1, x2, t, k;scanf("%d%d", &n, &m);for (int i = 0; i < m; i++) {
    scanf("%d%d", &x1, &x2);graph[x1][x2] = graph[x2][x1] = 1;}scanf("%d", &t);for (int i = 0; i < t; i++) {
    scanf("%d", &k);int pre, flag = 1, first, end, flag2 = 1;memset(book, 0, sizeof(book));for (int j = 0; j < k; j++) {
    scanf("%d", &x1);book[x1] = 1;if (j == 0) {
    pre = x1;first = x1;} else {
    if (graph[pre][x1] != 1) // 不连通 flag = 0;pre = x1;}}if (k != n + 1 || first != x1 || flag == 0) // 不等于顶点数加1或者第一个不等于最后一个 printf("NO\n");else {
    for (int i = 1; i <= n; i++) {
     if (book[i] == 0) // 是否有没遍历过的顶点flag2 = 0;}if (flag2 == 0)printf("NO\n");elseprintf("YES\n");} }return 0;
}