【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
#include <iostream>
#include <algorithm>
using namespace std;
int g[201][201];
int visited[201];
int main()
{
freopen("test.txt","r",stdin);
int n,m,k;
cin>>n>>m;
while(m--){
int x,y;
cin>>x>>y;
g[x][y]=g[y][x]=1;
}
cin>>k;
while (k--){
fill(visited,visited+201,0);
int s,t;
cin>>s;
if (s!=n+1) {
while (s--) cin>>t;
cout<<"NO\n";
}else{
cin>>t;
visited[t]+=1;
--s;
int x,y;
x=t;
while (s--){
cin>>y;
if (g[x][y]==1) visited[y]+=1;
x=y;
}
if (count(visited,visited+201,1)==n-1 && y==t) cout<<"YES\n";
else cout<<"NO\n";
}
}
return 0;
}
上一篇: 算法:1122. Relative Sort Array
下一篇: 返回前端的父子结构
推荐阅读
-
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)
-
1122 Hamiltonian Cycle (25 分)
-
1122 Hamiltonian Cycle (25 分)