mitosoupのブログ

何かあれば、お気軽にご連絡ください。twitter:@mitsoup

AtCoder Beginner Contest 054 C One stroke pass

問題

https://beta.atcoder.jp/contests/abc054/tasks/abc054_c

無向グラフについて、一筆書きの経路が有るかを判定する。

 

やった方法

節点の数が少ないので、今回は深さ優先探索を行った。

 

コード

簡単な部分について、内包表記を少しずつ取り入れるようにしています。

n,m = map(int,input().split())
H = [[0 for _ in range(n)] for _ in range(n) ]

for _ in range(m):
    a, b = map(int,input().split())
    H[a-1][b-1] = 1
    H[b-1][a-1] = 1
    
l = [0 for _ in range(n)]
ans = 0

def dfs(node,visited):
    global ans
    if visited.count(0) == 0:
        ans += 1 
        return 0
    else:
        visited[node] = 1
        for node_,edge_ in enumerate(H[node]):
            if edge_ == 1 and visited[node_] != 1:
                visited[node_] = 1
                visited[node] = 1
                dfs(node_,visited)

                visited[node_] = 0
dfs(0,l)
print(ans)