グラフの探索を頑張る問題。現代の AtCoder であまり見ないけど、教育的な全探索問題！！！

問題概要

頂点数 $N$ 、辺数 $M$ の無向グラフが与えられる。このグラフ上で頂点 1 から出発するハミルトンパスが何本あるかを数え上げよ。

なおハミルトンパスとは、グラフの各頂点をちょうど一度ずつ通るパスのことである。

制約

$2 \le N \le 8$

解法 1：DFS

とにかく頂点 1 からスタートして各頂点を一度ずつ通るようなパスを全探索しよう！！！！！！以下の記事に書いたような DFS で頑張ることができる。

qiita.com

再帰関数の終端条件としては、「 すべての頂点を探索したことがわかったら答えをインクリメントした上でリターンする」としている。

#include <iostream>
#include <vector>
using namespace std;

using Graph = vector<vector<int> >;
Graph G;

void dfs(int v, vector<bool> &seen, int &res) {
    bool end = true;
    for (int i = 0; i < seen.size(); ++i) if (!seen[i] && i != v) end = false;
    if (end) {
        ++res;
        return;
    }

    seen[v] = true;
    for (auto nv : G[v]) {
        if (seen[nv]) continue;
        dfs(nv, seen, res);
    }
    seen[v] = false;
}

int main() {
    int N, M; cin >> N >> M;
    G.assign(N, vector<int>());
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    vector<bool> seen(N, false);
    int res = 0;
    dfs(0, seen, res);
    cout << res << endl;
}

解法 2：next_permutaion

この問題は本質的に $N!$ 通りの全探索をする問題であるといえる。このように順列を全探索する方法として、next_permutaion を使う方法がある。

そして各順列に対して、その順番に辺が存在するかどうかを判定して、最後まで行き着くことができたら答えをインクリメントすれば OK。

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

// グラフを隣接行列で管理する
bool G[10][10];

int main() {
    int N, M; cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int a, b; cin >> a >> b; --a, --b;
        G[a][b] = G[b][a] = true;
    }

    // 順列
    vector<int> ord(N);
    for (int i = 0; i < N; ++i) ord[i] = i;

    // 順列を全部試すa
    int res = 0;
    do {
        if (ord[0] != 0) break;

        bool ok = true;
        for (int i = 0; i + 1 < N; ++i) {
            int from = ord[i];
            int to = ord[i+1];
            if (!G[from][to]) ok = false;
        }
        if (ok) ++res;
    } while (next_permutation(ord.begin(), ord.end()));

    cout << res << endl;
}