ABC 54 C問題

問題概要

• 自己ループと二重辺を含まない\(N\)頂点\(M\)辺の重み無し無向グラフが与えられる。
• \(i\)番目の辺は頂点\(a_i\)と頂点\(b_i\)を結ぶ。
• 頂点1を始発として、全ての頂点を１度だけ訪れるパスは何通りあるか求めよ。

制約

• \(2 ≤ N ≤ 8\)
• \(0 ≤ M ≤ N(N-1)/2\)
• \(1 ≤ a_i ≤ b_i ≤ N\)
• 与えられるグラフは自己ループと二重辺を含まない

考えたこと

• \(N ≤ 8\) なので、\(O(N!)\)十分計算可能
• 深さ優先探索で1から始まる全ての道を探索する。
• 全ての頂点を訪問済みであれば答えに1をたす

#include<bits/stdc++.h>
using namespace std;
const int nmax=8;
bool graph[nmax][nmax];

int dfs(int v, int n, bool visited[nmax]) {
  bool all_visited = true;
  for(int i = 0; i < n; ++i) {
    if(visited[i] == false) all_visited = false;
  }

  if(all_visited) return 1;

  int ret = 0;
  for(int i = 0; i < n; ++i) {
    // 入力によってはgraphが存在しないので、スキップ
    if(graph[v][i] == false) continue;
    if(visited[i]) continue;
    visited[i] = true;
    ret += dfs(i, n, visited);
    visited[i] = false;
  }

  return ret;
}

int main() {
  int n, m; cin >> n >> m;
  for(int i =0; i < m; ++i) {
    int a, b; cin >> a >> b;
    graph[a-1][b-1] = graph[b-1][a-1] = true;
  }
  
  bool visited[n];
  for(int i = 0; i < n; ++i){
    visited[i] = false;
  }
  // 1を出発点にする
  visited[0] = true;

  cout << dfs(0, n, visited) << endl;

  return 0;
}