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

题意:

给出一个无向图

在给出若干组路径，要求判断该路径是否为哈密顿回路

题解:

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

题中并没有给出什么是Hamilton Cycle，我们也可以通过样例自己猜一下

经验小结:

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

2.欧拉路径 图G中经过每条边一次并且仅一次的路径称作欧拉路径。 3.欧拉图 存在欧拉回路的图称为欧拉图。 4.半欧拉图 存在欧拉路径但不存在欧拉回路的图称为半欧拉图。 5.哈密顿回路：经过每个点一次并且回到起点

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

另外要小心对于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;}
    
   

转载地址：http://bnydf.baihongyu.com/