ABC054_C

階乗して並び変えたもののうち島1から始まるPATHを数える.
グラフを隣接リストから隣接行列に変形する.
はじめから島1が最初になるようにvector<> islandを作ったためnext_permutatino()しても時間的に問題ない.

#include <bits/stdc++.h>
using namespace std;
template <class ForwardIterator, class T>
  void iota (ForwardIterator first, ForwardIterator last, T val)
{
  while (first!=last) {
    *first = val;
    ++first;
    ++val;
  }
}
int g[11][11]={0};
int main()
{
    int n,m,x,y,res=0;
    cin>>n>>m;
    vector<int> island(n);
    iota(island.island(),island.end(),0);
    
    for(int i=0;i<m;i++){//隣接行列
        cin>>x>>y;
        g[x-1][y-1] = g[y-1][x-1] = 1;
    }
    do{
        bool flag = true;
        if(island[0])break;//始点が0の時のみ考える
        for(int i=1;i<n;i++){//始点からのつながりを見ていく
            if(!g[island[i-1]][island[i]])flag=false;//つながってない
        }
        if(flag)res++;
    }while(next_permutation(island.begin(),island.end()));
    cout<<res<<endl;
    return 0;
}


iota()を使う場合

template <class ForwardIterator, class T>
  void iota (ForwardIterator first, ForwardIterator last, T val)
{
  while (first!=last) {
    *first = val;
    ++first;
    ++val;
  }
}


vector<int> a(10);
iota(a.begin(),a.end(),0);
for(int i=0;i<10;i++)cout<<a<<" ";
//0 1 2 3 4 5 6 7 8 9