蟻本初級編攻略 - 2-1 特殊な状態の列挙

蟻本ではちゃんと例題めいたものが載っていなかった話題。

Pythonだとitertools.permutationなどで簡単に実装できる。

ABC054C - One-stroke Path

abc054.contest.atcoder.jp

abc054.contest.atcoder.jp

重み無し無向グラフを、特定の始点「１」からはじめてすべての頂点を一回だけ訪れるパスを数える問題。

「１」以外の頂点を並べる順番をすべて列挙してから始点に「１」を加え、隣同士のペアがすべて辺の集合に含まれているかを調べる。

from itertools import permutations

n, m = map(int, input().split())
edges = set()
for _ in range(m):
    a, b = map(int, input().split())
    edges.add((a, b))
    edges.add((b, a))

orderings = ((1,) + p for p in permutations(range(2, n+1)))
print(sum(all(move in edges for move in zip(p, p[1:])) for p in orderings))

ちなみに始点「１」を加えるのに、AtCoderで使えるPython3のバージョンが3.4なので(1,)+pとしている。

Python3.5からはUnpacking SyntaxがPEP448で拡張されて'(1, *p)'と書ける。