PAT (Advanced Level) Practise 1122. Hamiltonian Cycle (25)

2019-11-06 08:36:25

字体：大中小

来源：转载

供稿：网友

1122. Hamiltonian Cycle (25) 时间限制: 400 ms内存限制: 65536 kB代码长度限制: 16000 B判题程序：Standard 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 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 … Vnwhere n is the number of vertices in the list, and Vi’s are the vertices on a path. Output For each query, print in a line “YES” if the path does form a Hamiltonian cycle, or “NO” if not. Examples

Input
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 1
Output
YESNONONOYESNO

Notes 作者 CHEN, Yue

　　符合题意的路径需要满足下列要求。　　1.起点和终点相同。　　2.除了起点和终点，每个点只经过一次。　　3.由以上两个条件，可以知道路径中的点数为N+1 　　4.路径中相邻的两点之间存在连接边。　　　　题目中K的值的范围没有给出，如果K的值预估小了，最后一个测试点可能会错误。PAT中有些题目没有全部给出每个量的范围，可把这些量估计得大一些，或者使用变长数组vector等。　　以下代码是使用邻接表实现的，用邻接矩阵实现会更简单一写。

#include <iostream>#include <algorithm>#include <map>#include <vector>#include <functional>#include <string>#include <cstring>#include <queue>#include <set>#include <stack>#include <cmath>#include <cstdio>#include <sstream>#include <iomanip>using namespace std;#define IOS ios_base::sync_with_stdio(false)#define TIE std::cin.tie(0)#define MIN2(a,b) (a<b?a:b)#define MIN3(a,b) (a<b?(a<c?a:c):(b<c?b:c))#define MAX2(a,b) (a>b?a:b)#define MAX3(a,b,c) (a>b?(a>c?a:c):(b>c?b:c))typedef long long LL;typedef unsigned long long ULL;const int INF = 0x3f3f3f3f;const double PI = 4.0*atan(1.0);const double eps = 1e-6;const int maxn = 205;int n, m, u, v, k, t;int p[1005];bool done[maxn];vector<int> G[maxn];bool adj(int u, int v){ for (int j = 0; j < G[u].size(); j++){ if (G[u][j] == v) return true; } return false;}bool check(){ if (p[0] != p[t - 1] || t != n + 1) return false; int q = 0; for (int i = 1; i <= n; i++) done[i] = false; for (int i = 0; i < t; i++) done[p[i]] = true; for (int i = 1; i <= n; i++) if (!done[i]) return false; while (q < t - 1) { if (!adj(p[q], p[q + 1])) return false; q++; } return true;}int main(){ scanf("%d%d", &n, &m); for (int i = 0; i < m; i++){ scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } scanf("%d", &k); while (k--){ scanf("%d", &t); for (int i = 0; i < t; i++) scanf("%d", &p[i]); printf("%s/n", check() ? "YES" : "NO"); }}

上一篇：leetcode经典编程题（9）

下一篇：LA 5237