AtCoder が提供しているABC（AtCoder Beginner Contest）054 C問題をC++で解いてみました。ABC054は、2017年2月11日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 One-stroke Path（Difficulty : 1244）
問題の詳細は、リンク先をご覧ください。
順列全探索を行う典型問題です。AtCoder Problems による Difficulty は 1244 でした。
解答案
C++ プログラム例（ABC054C）
すべての頂点を一度だけ訪れるパスを調べます。C++ では、すべての順列を得るために next_permutation が使えます。
プログラムを補足します。
- 頂点間の辺の有無を2次元配列
pathに格納します（8ー14行目）。 - 配列
pに 1 から $n$ までを格納します（16ー19行目）。 - 配列
pから順列を生成して、条件を満たすか確認します。条件を満たす場合は、resultの値を一つ増やします。 - 最後に
resultを出力します。
以下が、C++プログラムです。再利用できそうな行の背景色を変更しました。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<vector<bool>> path(n + 1, vector<bool>(n + 1, false));
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
path[a][b] = true;
path[b][a] = true;
}
vector<int> p(n);
for (int i = 0; i < n; ++i) {
p[i] = i + 1;
}
int result = 0;
do {
bool is_OK = true;
if (p[0] != 1) {
is_OK = false;
} else {
for (int i = 1; i < n; ++i) {
if (!path[p[i - 1]][p[i]]) {
is_OK = false;
}
}
}
if (is_OK) {
++result;
}
} while (next_permutation(p.begin(), p.end()));
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
最後に
昔のABCの方が、典型的な問題が多い気がします。この問題も順列の実装を学ぶのによい問題でした。
引き続き ABC の問題を紹介していきます。
