本文共 1175 字，大约阅读时间需要 3 分钟。

题意:

给出一个无向图

题解:

我们首先需要学习一下什么是哈密顿回路：从某一点出发，经过所有点恰好一次并且回到原点的回路

经验小结:

1.欧拉回路 图G中经过每条边一次并且仅一次的回路称作欧拉回路。

回路转一圈后即回到原点，路径不需要

另外要小心对于MAXN的定义，输入的点可不止N个，最后一个测试点

#include
   
    using namespace std;#define ms(x, n) memset(x,n,sizeof(x));typedef  long long LL;const int INF = 1 << 30;const int MAXN = 2010;int G[MAXN][MAXN], N, M, Q, k, v[MAXN];set
    
      vis;bool judge(){
       if(v[1] != v[k] || k-1 != N || vis.size() != N) //vis==N且k-1==N说明所有节点均访问且仅访问一次        return false;    for(int i = 1; i < k; ++i)        if(!G[v[i]][v[i+1]])            return false;    return true;}int main() {
       ios::sync_with_stdio(false);    int a, b;    cin >> N >> M;    while(M--){
           cin >> a >> b;        G[a][b] = G[b][a] = 1;    }    cin >> Q;    while(Q--){
           cin >> k;        vis.clear();        for(int i = 1; i <= k; ++i){
               cin >> v[i];             vis.insert(v[i]);        }        if(judge())            cout << "YES\n";        else            cout << "NO\n";    }    return 0;}
    
   

转载地址：https://suprit.blog.csdn.net/article/details/104324746 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！