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 Kwhich 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
题意:判断是否为Hamiltonian Cycle:条件是简单回路(除最后一个结点以外只出现一次),并且相邻两点之间连通。
1 /**
2 * Copyright(c)
3 * All rights reserved.
4 * Author : Mered1th
5 * Date : 2019-02-28-00.13.48
6 * Description : A1122
7 */
8 #include<cstdio>
9 #include<cstring>
10 #include<iostream>
11 #include<cmath>
12 #include<algorithm>
13 #include<string>
14 #include<unordered_set>
15 #include<map>
16 #include<vector>
17 #include<set>
18 using namespace std;
19 const int maxn=210;
20 const int INF=1000000000;
21 int G[maxn][maxn];
22 int n,m,k;
23 int main(){
24 #ifdef ONLINE_JUDGE
25 #else
26 freopen("1.txt", "r", stdin);
27 #endif
28 scanf("%d%d",&n,&m);
29 fill(G[0],G[0]+maxn*maxn,INF);
30 int u,v;
31 for(int i=0;i<m;i++){
32 scanf("%d%d",&u,&v);
33 G[u][v]=G[v][u]=1;
34 }
35 scanf("%d",&k);
36 int t,a;
37 for(int i=0;i<k;i++){
38 scanf("%d",&t);
39 vector<int> temp;
40 bool vis[maxn]={false};
41 bool flag=true;
42 for(int j=0;j<t;j++){
43 scanf("%d",&a);
44 temp.push_back(a);
45 }
46 if(temp[0]!=temp[temp.size()-1]){
47 printf("NO\n");
48 continue;
49 }
50 for(int x=0;x<temp.size()-1;x++){
51 if(G[temp[x]][temp[x+1]]!=1 || vis[temp[x]]==true){
52 printf("NO\n");
53 flag=false;
54 break;
55 }
56 else{
57 vis[temp[x]]=true;
58 }
59 }
60 if(flag==false) continue;
61 for(int j=1;j<n;j++){
62 if(vis[j]==false){
63 printf("NO\n");
64 flag=false;
65 break;
66 }
67 }
68 if(flag) printf("YES\n");
69 }
70 return 0;
71 }