题目描述

哈密尔顿回路的判定：  包含所有节点的简单回路
1. 包含所有节点，首尾节点相同，所以序列总节点个数为n+1,并且首尾节点相同
2. 将所有的节点标记，恰好所有节点都走一遍，即对应所有的节点都被标记
3. 保证序列路径是可达到的

算法1

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
const int N=210;
int g[N][N];
int n,m;
int path[N];
int st[N];

bool check(int q){
    memset(st,0,sizeof(st));

    if(path[0]!=path[q-1]||q!=n+1){
        return false;
    }

    for(int i=0;i<q-1;i++){
        st[path[i]]=1;
        if(!g[path[i]][path[i+1]]){
            return false;
        }
    }

    for(int i=1;i<=n;i++){
        if(!st[i]) return false;
    }

    return true;
}

int main(){
    cin>>n>>m;

    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        g[a][b]=g[b][a]=1;
    }

    int k;cin>>k;
    for(int i=0;i<k;i++){
        int q;cin>>q;
        for(int j=0;j<q;j++){
            cin>>path[j];
        }
        if(check(q)){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }



    return 0;
}