読者です 読者をやめる 読者になる 読者になる

紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

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