PAT甲级 1122. Hamiltonian Cycle (25)
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 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 1Sample Output:
YES NO NO NO YES NO
题目的意思是给出n个点m条边,对于每次查询判断是否是哈密顿路径
思路:根据查询,分别判断点数,首尾是否一致,是否每个点都遍历,路径是否联通
若均符合则YES否则NO
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <climits>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;
int mp[500][500];
int a[500];
int main()
{
int n,m,x,y,q,k;
scanf("%d%d",&n,&m);
memset(mp,0,sizeof mp);
for(int i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
mp[x][y]=mp[y][x]=1;
}
scanf("%d",&q);
while(q--)
{
scanf("%d",&k);
for(int i=0;i<k;i++)
scanf("%d",&a[i]);
if(n==1&&k==1)
{
printf("YES\n");
continue;
}
if(k!=n+1||a[0]!=a[k-1])
{
printf("NO\n");
continue;
}
int flag=0;
set<int>s;
s.insert(a[0]);
for(int i=1;i<k;i++)
{
if(mp[a[i]][a[i-1]]==0)
{
flag=1;
break;
}
s.insert(a[i]);
}
if(s.size()!=n)
flag=1;
printf("%s\n",flag==0?"YES":"NO");
}
return 0;
}
推荐阅读
-
PAT 甲级真题 1006 Sign In and Sign Out (25分) python实现
-
PAT 甲级 1122. Hamiltonian Cycle (25)
-
【PAT】1122. Hamiltonian Cycle (25)
-
PAT甲1122 Hamiltonian Cycle(25 分)
-
[Python](PAT)1122 Hamiltonian Cycle(25 分)
-
A1122 Hamiltonian Cycle (25 分| 图论,附详细注释,逻辑分析)
-
PAT 1122 Hamiltonian Cycle
-
PAT (Advanced Level) Practice - 1122 Hamiltonian Cycle(25 分)
-
PAT甲级 1122. Hamiltonian Cycle (25)
-
【PAT甲级】【1002】 A+B for Polynomials (25分)