PAT1122 Hamiltonian Cycle (25分)

75 阅读 0 评论 50 点赞

我是靠谱客的博主殷勤跳跳糖，最近开发中收集的这篇文章主要介绍PAT1122 Hamiltonian Cycle (25分)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

原文链接：我的个人博客

原题链接

1122 Hamiltonian Cycle (25分)

考点

图论

思路

该题是需要让你判断输入的那些顶点是否可以构成哈密顿环，需要满足一下条件
1. 输出的顶点总数是n+1,其中第一个顶点和最后一个顶点相同
2. 每前后两节点要相连
3. 所有节点均要出现

代码

#include <bits/stdc++.h>
using namespace std;
int e[510][510];
int main(){
    int n,m,k;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        e[a][b] = e[b][a] = 1;
    } 
    cin>>k;
    for(int i=0;i<k;i++){
        int num,tmp,flag=1;
        cin>>num;
        vector<int>v;
        v.resize(num);
        for(int j=0;j<num;j++){
            cin>>v[j];
        }
        for(int t=0;t<v.size()-1;t++){
            if(e[v[t]][v[t+1]]==0){
                flag = 0;
                break;
            }
        }
        if(num!=n+1 || v[0]!=v[num-1]){
            cout<<"NO"<<endl;
        }else{
            set<int>s(v.begin(),v.end());
            if(s.size()==n&&flag==1) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
}