汉密尔顿回路

叶茂林

发布于 2023-07-30 13:28:04

2650

发布于 2023-07-30 13:28:04

文章被收录于专栏：叶子的开发者社区

题目描述

著名的“汉密尔顿（Hamilton）回路问题”是要找一个能遍历图中所有顶点的简单回路（即每个顶点只访问 1 次）。本题就要求你判断任一给定的回路是否汉密尔顿回路。

输入

首先第一行给出两个正整数：无向图中顶点数 N（2<N≤200）和边数 M。随后 M 行，每行给出一条边的两个端点，格式为“顶点1 顶点2”，其中顶点从 1 到N 编号。再下一行给出一个正整数 K，是待检验的回路的条数。随后 K 行，每行给出一条待检回路，格式为：

n V1 V2 ⋯ Vn

其中 n 是回路中的顶点数，Vi 是路径上的顶点编号。

输出

对每条待检回路，如果是汉密尔顿回路，就在一行中输出"YES"，否则输出"NO"。

输入样例1

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

输出样例1

YES NO NO NO YES NO

思路分析

一开始我的想法是用搜索算法像DFS之类把所有路径都探寻出来然后和输入进行比较，但是把所有路径探寻出来太难了，后来改用正向思维，即，先读取所给的回路，用一个队列去存储，然后每次根据队首两个元素去寻找该路径是否存在，以及判断是否存在已访问过再次访问的情况，最后判断是否有元素未被该回路囊括。

程序还进行了一些预先判断，即如果回路节点小于等于图的节点数，那必然不是汉密尔顿回路，我直接输出NO。

AC代码

#include<iostream>
#include<queue>

using namespace std;
const int max_vertex_number = 100;

class Map {
    int vertex_number = 0, edge_number = 0;
    int matrix[max_vertex_number][max_vertex_number];
public:
    Map() {
        cin >> vertex_number >> edge_number;
        int tail, head;
        for (int i = 0; i < edge_number; i++) {
            cin >> tail >> head;
            matrix[tail - 1][head - 1] = matrix[head - 1][tail - 1] = 1;
        }
    }

    void Hamilton() {
        bool visited[max_vertex_number] = {false};
        queue<int> path;
        int vertex;
        cin >> vertex;
        for (int i = 0; i < vertex; i++) {
            int temp;
            cin >> temp;
            path.push(temp);
        }
        if (vertex <= vertex_number) {
            cout << "NO" << endl;
            return;
        }
        for (int i = 0; i < vertex - 1; i++) {
            int head = path.front();
            path.pop();
            int tail = path.front();
            if (matrix[head - 1][tail - 1]&&visited[tail-1]!= true)
                visited[tail - 1] = true;
            else{
                cout<<"NO"<<endl;
                return;
            }
        }
        for (int i = 0; i < vertex_number; i++)
            if (visited[i] == false) {
                cout << "NO" << endl;
                return;
            }
        cout << "YES" << endl;
    }
};

int main() {
    Map test;
    int t;
    cin >> t;
    while (t--)
        test.Hamilton();
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-11-16，如有侵权请联系 cloudcommunity@tencent.com 删除

存储