AtCoder蟻本 初級編 2-1 全探索 ④特殊な状態の列挙

ABC054 C - One-stroke Path

C - One-stroke Path

概要

与えられた自己ループと二重辺を含まない 頂点辺の重み無し無向グラフについて、
頂点1から始めて全ての頂点を1度だけ訪れるパスは何通りあるかを出力せよ。

制約

方針

訪れる頂点の順番を順列で与え、その通りに行けるかを判定する。
グラフを隣接頂点のvectorで持たせるとREしたので、
mapで持たせている。

解答

Submission #3879066 - AtCoder Beginner Contest 054

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n, m;
	cin >> n >> m;
 
	map<pii, int> mp;
	rep(i, n){
		rep(j, n){
			mp[(pii){i, j}] = 0;
			mp[(pii){j, i}] = 0;
		}
	}
 
	rep(i, m){
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		mp[(pii){a, b}] = 1;
		mp[(pii){b, a}] = 1;
	}
 
	vector<int> v;
	rep(i, n) v.push_back(i);
 
	ll ans = 0;
	do{
		if(v[0] != 0) continue;
 
		bool ok = true;
		for(int i = 0; i < n-1; i++){
			if(!mp[(pii){v[i], v[i+1]}]){
				ok = false;
				break;
			}
		}
		if(ok) ans++;
	}while(next_permutation(v.begin(), v.end()));
 
	cout << ans << endl;
 
}