PTA 哈密尔回路(建图搜索)

题目

著名的“汉密尔顿（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

• 输出样例：

YES
NO
NO
NO
YES
NO

题解

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;const int N = 210;
int n, m, idx = 0;
int h[N];
int e[N * N];
int ne[N * N];
bool mry[N];void add(int a, int b) {e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}int main() {memset(h, -1, sizeof(h));cin >> n >> m;while (m--) {int x, y;cin >> x >> y;add(x, y);add(y, x);}int k;cin >> k;while (k--) {memset(mry, false, sizeof(mry));int num = 1;int kk, beg, end;cin >> kk ;int p[kk+1];for(int i=1;i<=kk;i++){cin >>p[i];}beg=p[1];end=p[kk];if (kk != n + 1 || beg != end) {cout << "NO" << endl;continue;}mry[beg] = true;int be = beg;for (int i = 2; i <= kk; i++) {int temp=p[i];if (mry[temp] && i != kk) {cout << "NO" << endl;break;}bool f = false;for (int j = h[be]; j != -1; j = ne[j]) {int l = e[j];if (l == temp) {f = true;break;}}if (!f) {cout << "NO" << endl;break;}mry[temp] = true;be = temp;num++;}bool flag2 = false;for (int i = 1; i <= n; i++) {if (!mry[i]) flag2 = true;}if (num == n + 1 && !flag2)cout << "YES" << endl;}return 0;
}

思路

建立静态链表，然后按照题目给的顺序遍历搜索即可。