PAT 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≤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 V2​​ … 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.

题目大意

  哈密顿环问题是寻找一个包含图中所有顶点的简单环，这样的环被称为哈密顿环。
  在这个问题中，你需要判断给定的环是否为哈密顿环。

输入说明
  每个输入文件包含一个测试用例，对于每个测试用例，第一行包含两个正整数N(2<N≤200)，它是顶点的数目，M，一个无向图的边数。接下来的M行，每一行用Vertex1 Vertex2的形式描述了描述了一条无向图的边，顶点是从1到N进行编号。接下来的一行是一个正整数K，它是查询的数目，再接下来是K行查询内容，每一行都有如下形式：
n V​1 V2​​ … V​n
这里面的n是顶点的数目，Vi是路径上的每一个顶点。

输出说明
  对于每一个查询，如果给定的路劲是哈密顿环，则输出YES，否则输出NO。

---

题目分析
  要做这个题，首先得有一定的图论基础。哈密顿环是指经过所有顶点一次且仅一次的回路，若图中顶点的个数是n，那么用顶点表示路径时，必须有n+1个顶点才可能是哈密顿环，而且第0个顶点和第n个顶点必须相同。所以这道题的思路是：先判断顶点的个数是否为n+1，若是，则再判断第0个顶点和第n个顶点是否相同，若相同，再判断是否每个顶点都出现了一次，若是，最后再判断给定的路径是否真的是一条路径，比如给定的路径是1 2 3 4 1，那么就要求1与2之间有边连接，2与3之间有边连接，3与4之间有边连接，4与1之间有边连接.。

源代码

#include <bits/stdc++.h>
using namespace std;
bool G[205][205] = {};  //用邻接矩阵存储图
int n, m;
void Judge(int vNum,int path[]) {
    bool exist[205] = {};
    if (vNum != n + 1 || path[0] != path[vNum - 1]) { //顶点个数不等于n+1或第0个顶点不等于最后一个顶点，肯定不是哈密顿环 
        cout << "NO" << endl;
        return;
    }
    for (int i = 0; i < n; i++) {
        if (exist[path[i]] == true) {   //有顶点重复出现
            cout << "NO" << endl;
            return;
        }
        exist[path[i]] = true;
    }
    for (int i = 0; i < n; i++) {
        if (G[path[i]][path[i + 1]] == false) { //  路径不可达
            cout << "NO" << endl;
            return;
        }
    }  
    cout << "YES" << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    int u, v;
    int num;    //查询的次数
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u >> v;
        G[u][v] = true;
        G[v][u] = true;
    }
    cin >> num;
    while (num--) {
        int vNum;   //每次查询给出的顶点个数
        int path[405];  //存储每一个顶点
        cin >> vNum;
        for (int i = 0; i < vNum; i++) 
            cin >> path[i];
        Judge(vNum, path);
    }
}