1122. Hamiltonian Cycle (25)
時間限制
300 ms
記憶體限制
65536 kB
代碼長度限制
16000 B
判題程式
Standard
作者
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
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
const int maxn = 210;
const int INF = 1000000000;
int a[maxn];
int G[maxn][maxn];
int main()
{
fill(G[0], G[0] + maxn*maxn, INF);
int N, M;
scanf("%d %d", &N, &M);
int v1, v2;
for (int i = 0; i < M; i++)
{
scanf("%d %d", &v1, &v2);
G[v1][v2] = 1;
G[v2][v1] = 1;
}
int K;
scanf("%d", &K);
int n;
set<int> s; bool flag = false;
for (int i = 0; i < K; i++)
{
scanf("%d", &n);
for (int j = 0; j < n; j++)
{
scanf("%d", &a[j]);
s.insert(a[j]);
}
if (n != N + 1 || s.size() != N)
{
printf("NO\n");
}
else
{
int j = 0;
if (n == N + 1 && s.size() == N)
{
for (j = 0; j < n - 1; j++)
{
if (G[a[j]][a[j + 1]] == 1 && a[0] == a[n - 1])
continue;
else
{
printf("NO\n");
break;
}
}
if (j == n - 1)
{
printf("YES\n");
}
}
}
s.clear();
}
return 0;
}