E - Count Simple Paths - Githubissues

https://atcoder.jp/contests/abc284/tasks/abc284_e

問題概要

双方向グラフの頂点0から探索して、同じ頂点を通らない経路は何通りあるか。10**6 以上ある場合はそこで打ち止めして10**6 通りとしてよい。

解法

dfsで探索していく。入力例2のときを考える。

(0), (0, 1), (0, 1, 2), (0, 1, 2, 3), (0, 1, 3) ... という順番で探索できるようにするため、訪問済みフラグを管理する際に、行き止まったらその頂点を未訪問に戻す(バックトラック)する必要がある。バックトラックしないと、(0, 1, 2, 3) のあとに 3が訪問済みのままなので、(0, 1, 3) に行けない。

個人的な理解は、

ある頂点まで行けるかどうかはバックトラック不要
経路数を数え上げるときにはバックトラックが必要

というものだが、合っている？

import sys
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
graph = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    graph[a].append(b)
    graph[b].append(a)

visited = [False] * N
cnt = 0

def dfs(v):
    global cnt

    if cnt == 10 ** 6:
        return

    visited[v] = True
    cnt += 1

    for u in graph[v]:
        if not visited[u]:
            dfs(u)

    # バックトラック
    visited[v] = False

dfs(0)

print(cnt)

提出: https://atcoder.jp/contests/abc284/submissions/51949433

hxrxchang / atcoder

E - Count Simple Paths #19

問題概要

解法