163AC - ABC054C: One-stroke Path

ABC54-C (300 points)

問題

与えられた 頂点 辺の単純無向グラフについて, 頂点 を始点として全ての頂点を 度だけ訪れるパスを数え上げる.

• 
• 
• 

方針

• DFSで列挙.

# input
N, M = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(M)]
edges = [set() for _ in range(N)]

for a, b in G:
    edges[a - 1].add(b - 1)
    edges[b - 1].add(a - 1)

def dfs(start, edges, path):
    path.append(start)
    if len(path) == N:
        path.pop()
        return 1
    ans = 0
    for u in edges[start]:
        if u in path:
            continue
        ans += dfs(u, edges, path)
    path.pop()
    return ans    

print(dfs(0, edges, []))