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