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

题目

著名的“汉密尔顿（Hamilton）回路问题”是要找一个能遍历图中所有顶点的简单回路（即每个顶点只访问 1 次）。本题就要求你判断任一给定的回路是否汉密尔顿回路。

输入格式：

首先第一行给出两个正整数：无向图中顶点数 N（2

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 输出样例：

YES
NO
NO
NO
YES
NO
1
2
3
4
5
6

题解

#include 
#include 
#include 
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

思路

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