Home PAT 1122 Hamiltonian Cycle
Post
Cancel

PAT 1122 Hamiltonian Cycle

Link

这题本身很简单, 不过我对此有一些拓展的想法.

如果给出的只是一些点的集合, 要求判断这些点 (可能不是按照给出的顺序) 能不能构成 Hamiltonian Cycle, 就可以用 DFS 来解决 (开始以为是这个意思于是写的 DFS 🐭).

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
void DFS(int u,int cur){
    if(cur==num){
        if(g[u][vertex[1]]) flag=true;
        return;
    }
    for(int i=1;i<=num;++i){
        if(flag) return;
        if(g[u][vertex[i]]&&!v[vertex[i]]){
            v[vertex[i]]=true;
            DFS(vertex[i],cur+1);
            v[vertex[i]]=false;
        }
    }
}
int main(){
    //...
    while(k--){
        scanf("%d",&num);
        vertex.clear();
        vertex.resize(num+1);
        for(int i=1;i<=num;++i)
            scanf("%d",&vertex[i]);
        memset(v,false,sizeof(v));
        flag=true;
        v[vertex[1]]=true;
        DFS(vertex[1],1);
        //...
    }
    //...
}

AC 代码:

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n,m,k,num;
bool g[210][210];
bool v[210];
bool flag;
vector<int>vertex;
bool Hamiltonian(){
    if(num!=n+1||vertex[num]!=vertex[1]) return false;
    for(int i=2;i<=num;++i)
        if(!g[vertex[i]][vertex[i-1]])
            return false;
    return true;
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int v1,v2;
        scanf("%d%d",&v1,&v2);
        g[v1][v2]=g[v2][v1]=true;
    }
    scanf("%d",&k);
    while(k--){
        scanf("%d",&num);
        vertex.clear();
        vertex.resize(num+1);
        memset(v,false,sizeof(v));
        flag=true;
        for(int i=1;i<=num;++i){
            scanf("%d",&vertex[i]);
            if(i!=num&&v[vertex[i]]) flag=false;
            v[vertex[i]]=true;
        }
        if(!flag) printf("NO\n");
        else if(Hamiltonian()) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}
This post is licensed under CC BY 4.0 by the author.