共计 857 个字符，预计需要花费 3 分钟才能阅读完成。
题目粗心
给定一个无向图，判断查问的门路是否是一个哈密顿圈。
算法思路
判断一条门路是一个哈密顿圈的办法为
- 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
[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;
}
正文完
