哈密顿回路模板

以下是一个基于邻接矩阵的哈密顿回路模板实现，使用深度优先搜索算法：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20;

int n, m;
int g[N][N]; // 邻接矩阵
bool st[N]; // 标记数组

bool dfs(int u, int start, int cnt)
{
    if (cnt == n) return u == start; // 已经遍历完所有点且最后一个点能回到起点

    st[u] = true;
    for (int i = 1; i <= n; i++)
        if (g[u][i] && !st[i])
            if (dfs(i, start, cnt + 1)) return true;

    st[u] = false;
    return false;
}

int main()
{
    cin >> n >> m;

    while (m--)
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = g[b][a] = 1; // 无向图
    }

    if (dfs(1, 1, 1)) puts("Yes");
    else puts("No");

    return 0;
}

其中，输入的第一行为点数 $n$ 和边数 $m$，接下来 $m$ 行为各边的起点和终点。若存在哈密顿回路，输出 "Yes"，否则输出 "No"。