蟻本初級編攻略 - 2-1 特殊な状態の列挙
蟻本ではちゃんと例題めいたものが載っていなかった話題。
Pythonだとitertools.permutationなどで簡単に実装できる。
ABC054C - One-stroke Path
重み無し無向グラフを、特定の始点「1」からはじめてすべての頂点を一回だけ訪れるパスを数える問題。
「1」以外の頂点を並べる順番をすべて列挙してから始点に「1」を加え、隣同士のペアがすべて辺の集合に含まれているかを調べる。
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))
ちなみに始点「1」を加えるのに、AtCoderで使えるPython3のバージョンが3.4なので(1,)+p
としている。
Python3.5からはUnpacking SyntaxがPEP448で拡張されて'(1, *p)'と書ける。