题目粗心

给定一个无向图，判断查问的门路是否是一个哈密顿圈。

算法思路

判断一条门路是一个哈密顿圈的办法为

  • 1、除了首尾节点其余节点没有反复,不反复的节点数目等于N
  • 2、首节点只能反复一次，所有节点数目为N+1
  • 3、首尾节点得相等
  • 4、任意两点之间连通

在输出每一条门路的时候，首先判断输出节点与上一个输出节点是否连通，如果不是设置flag为false.而后统计节点数目cnt，并将节点增加进set汇合s中，只有s.size()!=n||cnt!=n+1||!flag||start!=End，就阐明该门路不是哈密顿圈，输入NO，否则输入YES。

提交后果

AC代码

#include<cstdio>#include<unordered_set>#include<set>#include<vector>using namespace std;int G[205][205];int main() {    int n, m;    scanf("%d %d", &n, &m);    for (int i = 0; i < m; ++i) {        int a, b;        scanf("%d %d", &a, &b);        G[a][b] = G[b][a] = 1;    }    int k;    scanf("%d", &k);    for (int i = 0; i < k; ++i) {        int num;        scanf("%d", &num);        unordered_set<int> s;        // 终点，节点个数，起点        int start, cnt = 1, End = 0;        bool flag = true;// 门路是否连通        scanf("%d", &start);        int pre = start;        for (int j = 1; j < num; ++j) {            int v;            scanf("%d", &v);            if (G[pre][v] == 0) {                flag = false;            }            if (j == num - 1) {                End = v;            }            pre = v;            ++cnt;            s.insert(v);        }        if (s.size() != n || cnt != n + 1 || !flag || start != End) {            printf("NO\n");        } else {            printf("YES\n");        }    }    return 0;}