【AtCorder】ABC054 C One-stroke Pathの問題について

概要

AtCorderでアルゴリズムを学び始めた初心者です．
タイトルのようにABC054 C One-stroke Pathの問題にてWAとなるので
どこか間違えているかを教えていただきたいです．

状況としては最初の５問はACとなるのですが，それ以降は全てWAとなります．
初心者なので，至らない部分もあると思いますが，ご教授してもらえると幸いです．
よろしくお願いします．

アルゴリズムとプログラム

プログラムの概要としては，まず始点が1なので1の隣接ノードの数だけfor文を回します．
そして，始点の子ノードに深さ優先探索を用いて，全探索を行い，全てノードを訪れることができれば，
パスの数をインクリメントしているという感じです．
※printは中身がわかりやすいように追加しているだけです．

Python
1import collections
2
3
4def dfs(graph, start, num):
5    ans = 0
6    stack = list()
7    f_vertex = graph.get(start)  # 始点と隣接しているノード
8    print(graph)
9
10    # 1とつながっている頂点の数だけfor文を回す
11    for child in f_vertex:
12        stack.append(child)  # dfsしたいノードをstackにappend
13        visited = [start]  # visitedをリセット
14
15        # stackの分だけループを回す
16        while stack:
17            node = stack.pop(0)
18            print("node:{}".format(node))
19            if node not in visited:
20                visited.append(node)  # 訪問済のノードを追加
21                print("visited:{}".format(visited))
22                stack = graph.get(node) + stack  # 子ノードをstackに追加
23                print("stack:{}".format(stack))
24
25        if len(visited) == num:
26            ans += 1
27            print("ans:{}".format(ans))
28
29    return ans
30
31
32n, m = map(int, input().split())
33tree = collections.defaultdict(list)
34
35# 隣接関係をdict型に保存
36for _ in range(m):
37    a, b = map(int, input().split())
38    tree[a].append(b)
39    tree[b].append(a)
40
41# 今回は始点が1と決まっているためにstartの位置を1と設定
42print(dfs(dict(tree), 1, m))
43

行動規範の内容に同意します

回答1件

ベストアンサー

print(dfs(dict(tree), 1, m)) で、dfs の num に m を渡していますが、
m は辺の数です。
if len(visited) == num: で、訪問した頂点の数を辺の数と比較するのは変です。

他にも変なところがありますが、次の入力データを試してデバッグしてみてください。
4 5
1 2
1 3
1 4
2 4
3 4
この場合、[1, 2, 4, 3] または [1, 3, 4, 2] の 2通りになるはずなのに、
質問のコードではそうなりません。

私なら次のようなコードを書きます。

Python
1from collections import defaultdict
2
3def dfs(start, visited):
4    if len(visited) == n:
5        ans.append(0)
6    else:
7        for c in graph[start]:
8            if c not in visited:
9                dfs(c, visited + [c])
10
11n, m = map(int, input().split())
12tree = defaultdict(list)
13for _ in range(m):
14    a, b = map(int, input().split())
15    tree[a].append(b)
16    tree[b].append(a)
17
18graph = dict(tree)
19ans = []
20dfs(1, [1])
21print(len(ans))

追記
次のようにすると、見つかったすべてのパスを表示できます。

Python
1from collections import defaultdict
2
3def dfs(start, visited):
4    if len(visited) == n:
5        ans.append(visited)
6    else:
7        for c in graph[start]:
8            if c not in visited:
9                dfs(c, visited + [c])
10
11n, m = map(int, input().split())
12tree = defaultdict(list)
13for _ in range(m):
14    a, b = map(int, input().split())
15    tree[a].append(b)
16    tree[b].append(a)
17
18graph = dict(tree)
19ans = []
20dfs(1, [1])
21print(len(ans))
22print(ans)