ABC054

だいぶ久しぶりの投稿…。全然習慣化できてないなー。

C問題をやってみて解けなかったっていうのもある。

今回は解答例を丸写しなのでご容赦を(__)

#include <bits/stdc++.h>
using namespace std;

const int nmax = 8;
bool graph[nmax][nmax];

int dfs(int v,int n,bool visited[nmax]){
 bool all_visited =true;

 for(int i=0;i<n;i++){
   if(visited[i]==false)
     all_visited =false;
 }
 if(all_visited){
   return 1;
 }

 int ret =0;

 for(int i=0;i<n;i++){
   if(graph[v][i]==false) continue;
   if(visited[i]) continue;

   visited[i]= true;
   ret += dfs(i,n,visited);
   visited[i]=false;
 }
 return ret;
}

int main(){
 int n,m;
 cin >> n >> m;

 for(int i=0;i<m;i++){
   int a, b;
   cin >> a >> b;
   graph[a-1][b-1] = graph[b-1][a-1] = true;
 }

 bool visited[nmax];
 for(int i=0;i<n;i++){
   visited[i]=false;
 }

 visited[0]=true;
 cout << dfs(0,n,visited) << endl;
 return 0;

}

言われてみると、あー、ってなるんだけど、DFSってまだ慣れない。

頂点同士の関係と通過済みかどうかをそれぞれboolで管理して、っていう流れを、もうそういうパターンとして引き出せるようにするしかないな。

下の部分、探索を進めていって行き詰った後に、通過済み(visited)をfalseに戻すっていうのが、個人的なるほどポイント！

あとは、探索した結果、すべて通過済みにならなければ、retをそのまま0で返す、このretを0で返すのを書き忘れてしまいそう…。

 int ret =0;

 for(int i=0;i<n;i++){
   if(graph[v][i]==false) continue;
   if(visited[i]) continue;

   visited[i]= true;
   ret += dfs(i,n,visited);
   visited[i]=false;
 }
 return ret;

丸写しでも毎日投稿！数をこなす！精進あるのみ！

わかりやすく華麗に解説もできるようになれたらいいな。

以上！