1122 Hamiltonian Cycle（40行代码+详细注释）

news/2024/7/15 17:16:49 标签: c++, 算法, 图论

分数 25

全屏浏览题目

作者 CHEN, Yue

单位浙江大学

The "Hamilton cycle problem" is to find a simple cycle that contains every vertex in a graph. Such a cycle is called a "Hamiltonian cycle".

In this problem, you are supposed to tell if a given cycle is a Hamiltonian cycle.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive integers N (2<N≤200), the number of vertices, and M, the number of edges in an undirected graph. Then M lines follow, each describes an edge in the format Vertex1 Vertex2, where the vertices are numbered from 1 to N. The next line gives a positive integer K which is the number of queries, followed by K lines of queries, each in the format:

n V1 V2 ... Vn

where n is the number of vertices in the list, and Vi's are the vertices on a path.

Output Specification:

For each query, print in a line YES if the path does form a Hamiltonian cycle, or NO if not.

Sample Input:

6 10
6 2
3 4
1 5
2 5
3 1
4 1
1 6
6 3
1 2
4 5
6
7 5 1 4 3 6 2 5
6 5 1 4 3 6 2
9 6 2 1 6 3 4 5 2 6
4 1 2 5 1
7 6 1 3 4 5 2 6
7 6 1 2 5 4 3 1

Sample Output:

YES
NO
NO
NO
YES
NO

代码长度限制

16 KB

时间限制

300 ms

内存限制

64 MB

哈密顿回路满足四个条件：

1.起点终点相等
2.路径每一步有边
3.所有点都访问到
4.总共n+1个点

#include<bits/stdc++.h>
using namespace std;
const int N=210;
int n,m;
int g[N][N];
int main(){
   cin>>n>>m;//v,e
   memset(g,0,sizeof g);
   for(int i=0;i<m;i++){
       int a,b;
       cin>>a>>b;
       g[a][b]=g[b][a]=1;
   }
   int k;
   cin>>k;//query
   while(k--){//k个查询
       int num;
       cin>>num;
       vector<int>path;
       while(num--){//将num个点插入到path数组
           int ver;
           cin>>ver;
           path.push_back(ver);
       }
       int len=path.size();//获得点的个数
       int flag=1;//用于判断是否为哈密顿回路，1表示是哈密顿回路，0则不是
       bool st[N];//用于判断某结点是否被访问过
       memset(st,0,sizeof st);
if(len!=n+1)flag=0;//结点数不为n+1个则不是哈密顿回路
       if(path[0]!=path[len-1])flag=0;//起点终点不等不是哈密顿回路
       for(int i=0;i<len-1;i++){//遍历每个结点
           st[path[i]]=true;//访问过的结点标记为true
           if(!g[path[i]][path[i+1]])flag=0;//相邻的结点没有边则不是哈密顿回路
       }
       for (int i = 1; i <= n; i ++ )if (!st[i])flag=0;//若有结点没被访问过就不是哈密顿回路
if(flag==0)puts("NO");//输出
else puts("YES");
   }
   return 0;
}