ABC 054 C One-Stroke Path

• 単純グラフ
• DFS

atcoder.jp

問題概要

N頂点M辺の無向グラフが与えられる.
全ての頂点を丁度一回づつ通る経路は何通りあるかを求めよ.
始点は頂点1とする.

解答

今回の問題はDFSを用いて解くことができる.
しっかり書いたコードは下に置いておき擬似コードを示す.

  public static void DFS ( int pos ) {
1    pos を 訪れたことにする
2    if ( pos から始まる道が存在 && 道の行き先がまだ訪れていない  )
             DFS ( 行き先 );
3    pos を 訪れていないことにする
  }

悩んだこと

訪れた場所をどこで更新するかに苦戦しました.if分の中で書いたほうがいいのか,if文の外で書いたほうがよかったのか.解いている最中は理解できませんでした.
DFS()関数内の最初に訪れたことにして,関数の終わりに訪れていなかったことにするとうまくいくことがわかった.

書いたDFS

public static void DFS(int pos) {
        visited[pos] = true;
        boolean comp = true;
        for (int i = 1; i < n + 1; i++) {
            if (!visited[i]) {
                comp = false;
                break;
            }
        }
        if (comp) {
            ans++;
            visited[pos] = false;
            return;
        }
        for (int i = 0; i < m; i++) {
            if (pos == a[i] && !visited[b[i]]) {
                DFS(b[i]);
            }
        }
        for (int i = 0; i < m; i++) {
            if (pos == b[i] && !visited[a[i]]) {
                DFS(a[i]);
            }
        }
        visited[pos] = false;
        return;
    }