1122. Hamiltonian Cycle (25)

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 V₁ V₂ ... V_n

where n is the number of vertices in the list, and V_i'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.

6 106 23 41 52 53 14 11 66 31 24 567 5 1 4 3 6 2 56 5 1 4 3 6 29 6 2 1 6 3 4 5 2 64 1 2 5 17 6 1 3 4 5 2 67 6 1 2 5 4 3 1Sample Output:
YESNONONOYESNO
#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;}