n!通りの全探索を学ぶ

#AtCoder 版！蟻本 (初級編)
今日からAtCoder 版！蟻本 (初級編)の記事を読み進めましょう！
蟻本とはプログラミングコンテストチャレンジブックの事です。
この本を読み進めてAtCoderに類似する問題があれば挑戦していきます。

##特殊な状態の列挙
n! 通りの全探索を行う事です。
C++には「next_permutation」があります。

###サンプル１

C++

#define MAX_N 100
bool used[MAX_N];
int perm[MAX_N];

void permutation(int pos, int n){
    if(pos == n){
        /* ここにpermの処理を書く */
        
        return;
    }
    
    for(int i=0; i<n; i++){
        if(!used[i]){
            perm[pos] = i;
            used[i] = true;
            permutation(pos+1, n);
            used[i] = false;
        }
    }
}

###サンプル2

C++

#include<algorithm>
int perm[MAX_N];

void permutation(int n){
    for(int i=0; i<n; i++){
        perm[i]=i;
    }
    do{
        /* ここにpermの処理を書く */
    }while(next_permutation(perm, perm+n));
}

##枝刈り
探索しなくても解が存在しない条件がある分岐からは処理を行わない。

#問題

###ABC 054 C One-stroke Path
問題文はAtCoderを参照してください。

• 無向グラフを使います。

C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384

using namespace std;
using ll =long long;
using P = pair<int,int>;

#include<algorithm>
#define MAX_N 8
bool G[MAX_N][MAX_N] = {false};
int order[MAX_N];

void permutation(int n){
    for(int i=0; i<n; i++){
        order[i]=i;
    }
    
    int res=0;
    do{
        if(order[0] != 0) continue;
        bool ok=true;
        /* ここにpermの処理を書く */
        for(int i=0; i+1<n; i++){
            int from = order[i];
            int to = order[i+1];
            
            if(!G[from][to]) ok=false;
        }
        if(ok) res++;
    }while(next_permutation(order, order+n));
    
    cout << res << endl;
}

int main(int argc, const char * argv[]) {
    int n, m;
    cin >> n >> m;
    
    rep(i, m){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a][b]=true;
        G[b][a]=true;
    }
    
    permutation(n);
    
    return 0;
}