【AtCoder版！蟻本】ABC054 C - One-stroke Path【順列全探索】

AtCoder版！蟻本について順列全探索の類題としてあげられているAtCoder Beginner Contest 054 C - One-stroke PathをPythonで解いていきます。

リンク

C - One-stroke Path

AtCoder Beginner Contest 054 C - One-stroke Path

問題文

自己ループと二重辺を含まない N 頂点 M 辺の重み無し無向グラフが与えられます。
i(1 ≦ i ≦ M) 番目の辺は頂点 ai と頂点 bi を結びます。
ここで、自己ループは ai=bi(1 ≦ i ≦ M) となる辺のことを表します。
また、二重辺は ai=aj かつ bi=bj(1 ≦ i < j ≦ M) となる辺のことを表します。
頂点 1 を始点として、全ての頂点を1度だけ訪れるパスは何通りありますか。
ただし、パスの始点と終点の頂点も訪れたものとみなします。

制約

・2≦N≦8
・0≦M≦N(N−1)/2
・1≦ai

解答例

import itertools

n, m = map(int,input().split())

graph = [[0]*n for _ in range(n)]
for i in range(m):
    a, b = map(int,input().split())
    a -= 1
    b -= 1
    graph[a][b] = 1
    graph[b][a] = 1

ans = 0
for num in itertools.permutations(range(n)):
    if num[0] == 0:
        count = 0
        for i in range(n-1):
            if graph[num[i]][num[i+1]] == 1:
                count += 1
        if count == n-1:
            ans += 1

print(ans)

解説

N頂点 M辺の無向グラフにおいて、頂点1からスタートしてすべての頂点を1度だけ通る経路の数を答える問題です。

制約から頂点の数は8個までなので順列を用いて全探索していきました。

Pythonと順列についての過去記事はこちら
ebisuke33.hatenablog.com

itertoolsモジュールをインポートして0からn-1までの範囲で作成した順列をnumとして探索しました。
始点は頂点1からなのでnumの最初の要素が0（頂点1）のときのみ探索を進めます。
count変数は進むことのできた頂点の数です。
辺で結ばれた頂点の情報は配列graphに格納してありますので次の頂点とのgraphの値が1ならば移動できることを意味します。
したがってcount変数を1増加させていき、値がn-1になれば求める条件を満たすことになりますのでans変数を増加させました。

ループを抜けた後にansを出力すればOKです！

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク