PAT-A 真题 – 1122 Hamiltonian Cycle

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 \leq 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^{1}$ $V^{2}$ ... $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.

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 <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int main(){
  const int maxn = 205, inf = 0x7fffffff;
  int G[maxn][maxn];  //定义图 
  fill(G[0], G[0] + maxn * maxn, inf);  //初始化图 
  int pcnt, icnt;
  cin >> pcnt >> icnt;
  for(int i = 0; i < icnt; i++){  //读入图 
    int l, r;
    cin >> l >> r;
    G[l][r] = G[r][l] = 0;
  }
  int qcnt;
  cin >> qcnt;
  for(int _ = 0; _ < qcnt; _++){  //读入查询 
    int cnt, frist, flag = 1;
    cin >> cnt >> frist;
    int last = frist;
    int Exist[maxn] = {0};
    for(int i = 1; i < cnt; i++){
      int tmp;
      cin >> tmp;
      if(G[last][tmp] == inf) flag = 0;  //路不通，ban 
      last = tmp;  //记录本次所在点，判断下一个路通不通 
      Exist[tmp]++;
    }
    for(int i = 1; i <= pcnt; i++) 
      if(Exist[i] != 1) flag = 0;  //有的点没有经过，或者有的点经过了多次，ban 
    if(flag) cout << "YES" << endl;
    else cout << "NO" << endl;
  }
  return 0;
}

斐斐のBlog