一、题目描述
原题链接 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:
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写成序列之后的特点就可以顺利做出来了，首先，要成为一个cycle，那么前一个结点和后一个结点之间一定是连通的，此外，如果除了最后一个结点，中间某结点出现了两次，那么肯定也不是Hamiltonian Cycle，而且第一个数一定是要与最后一个数相同，才能构成一个环。把所有要素考虑进来，就不会错了。
三、AC代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std
;
const int maxn
= 220;
int G
[maxn
][maxn
];
int main()
{
int N
, M
, a
, b
, K
, num
;
scanf("%d%d", &N
, &M
);
for(int i
=0; i
<M
; i
++)
{
scanf("%d%d", &a
, &b
);
G
[a
][b
] = G
[b
][a
] = 1;
}
scanf("%d", &K
);
vector
<int> v(K
);
for(int i
=0; i
<K
; i
++)
{
scanf("%d", &num
);
bool flag
= true, simple
= true, cycle
= true;
int cnt
[N
+1] = {0};
for(int j
=0; j
<num
; j
++)
{
scanf("%d", &v
[j
]);
cnt
[v
[j
]]++;
if(j
>0 && G
[v
[j
-1]][v
[j
]] != 1) flag
= false;
if(j
!= num
-1 && cnt
[v
[j
]] > 1) simple
= false;
}
if(v
[0] != v
[num
- 1] || num
!= N
+1) cycle
= false;
(flag
&& simple
&& cycle
) ? printf("YES\n") : printf("NO\n");
}
return 0;
}
