ABC054 C - One-stroke Path

AtCoder Python3 DFS

備忘録

問題

atcoder.jp

回答

import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def dfs(graph, edges, now, ret):
    edges[now] = True
    if all(edges): ret += 1

    for next in graph[now]:
        if edges[next]: continue
        ret = dfs(graph, edges, next, ret)
    edges[now] = False
    return ret


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    g = {n: [] for n in range(N)}
    for m in range(M):
        a, b = il()
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)

    ret = 0
    edges = [False] * N
    edges[0] = True
    ret = dfs(g, edges, 0, ret)
    print(ret)


if __name__ == '__main__':
    main()

考え方

頂点1からDFS(深さ優先探索)を行い、
全ての頂点に到達するルートを探索する。

無向グラフをデータで表現するために、
keyを頂点、valueを頂点と辺でつながる他の頂点としたデータを整形する。

その後、各頂点を到達したか否かを保持する配列(edges)を作り、 始点(頂点1)を到達済みとしてDFSで探索を行う。
DFSの実装は下記URLを参考に、ほぼまるコピした。

DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【後編】 - Qiita

注意点は、関数dfsで、
ある頂点からつながる他の頂点をすべて探索し終わった後、
始点となった頂点の未探索(edges[now] = False)とすること。