ログイン
編集不可のページディスカッション情報添付ファイル
akky/cp/graph-search

MMA

問題

グラフの探索問題
https://atcoder.jp/contests/abc054/tasks/abc054_c

概要

自己ループと二重辺を含まないN頂点M辺の重み無し無向グラフが与えられるとき、頂点1を始点として全ての頂点を1度だけ訪れるパスは何通りあるか。

制約

1 <= N <= 8
0 <= M <= N(N-1)/2
1 <= a_i <= b_i <= N

a_i, b_i は頂点

入力

N M
a_1 b_1
a_2 b_2
.
.
a_M b_M

出力

パスの場合の数

コード

深さ優先探索

def dfs(i):
    if all(visited):
        global ans
        ans += 1
        return
    for j in range(N):
        if g[i][j] and not visited[j]:
            visited[j] = True
            dfs(j)
            visited[j] = False

N, M = map(int, input().split())
g = [[False] * N for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    g[a-1][b-1] = True
    g[b-1][a-1] = True

ans = 0
visited = [False] * N
visited[0] = True
dfs(0)
print(ans)

要点

  • グラフは隣接行列で表現
  • 入力は1オリジンなので隣接行列を作るとき1を引く
  • dfsは行き先の頂点番号を引数にとる
  • 関数内部からグローバル変数を変更する際はglobal宣言が必要 (Python)

出典

AtCoder Beginner Contest 054 C問題

TODO

他の実装もする

  • stack
  • queue
  • DP

akky/cp/graph-search (最終更新日時 2019-01-10 22:43:50 更新者 akky)