PAT (Advanced Level) Practice - 1122 Hamiltonian Cycle（25 分）

题目链接：点击打开链接

 

题目大意：判断给出的 K 次询问中的结点序列，是否为哈密顿回路？

 

解题思路：判定哈密顿回路条件：
a、路径节点个数等于 n+1；
b、相邻点之间存在连通的边；
c、各点只出现过1次（除了首尾）；
d、第一个节点等于最后一个节点（构成回路）。

 

AC 代码

#include<bits/stdc++.h>
#include<cmath>

#define mem(a,b) memset(a,b,sizeof a)
#define ssclr(ss) ss.clear(), ss.str("")
#define INF 0x3f3f3f3f
#define MOD 1000000007

using namespace std;

typedef long long ll;

const int maxn=250;

int n,m;
int vis[maxn], a[maxn];
int mp[maxn][maxn];

int main()
{
    int u,v,k,l,f;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&u,&v);
        mp[u][v]=mp[v][u]=1;
    }

    scanf("%d",&k);
    while(k--)
    {
        mem(vis,0), f=1;
        scanf("%d",&l);
        for(int i=0;i<l;i++)
        {
            scanf("%d",&a[i]);
            if(i!=l-1 && vis[a[i]]==0) vis[a[i]]=1;
            else if(i!=l-1) f=0;
        }

        if(f && a[0]==a[l-1] && l==n+1)
        {
            for(int i=0;i<l-1;i++)
                if(mp[a[i]][a[i+1]]!=1){f=0; break;}
            puts(f?"YES":"NO");
        }
        else puts("NO");
    }

    return 0;
}