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

Question

概要

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

問題URL

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

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

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

import collections


def dfs(graph, start, num):
    ans = 0
    stack = list()
    f_vertex = graph.get(start)  # 始点と隣接しているノード
    print(graph)

    # 1とつながっている頂点の数だけfor文を回す
    for child in f_vertex:
        stack.append(child)  # dfsしたいノードをstackにappend
        visited = [start]  # visitedをリセット

        # stackの分だけループを回す
        while stack:
            node = stack.pop(0)
            print("node:{}".format(node))
            if node not in visited:
                visited.append(node)  # 訪問済のノードを追加
                print("visited:{}".format(visited))
                stack = graph.get(node) + stack  # 子ノードをstackに追加
                print("stack:{}".format(stack))

        if len(visited) == num:
            ans += 1
            print("ans:{}".format(ans))

    return ans


n, m = map(int, input().split())
tree = collections.defaultdict(list)

# 隣接関係をdict型に保存
for _ in range(m):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

# 今回は始点が1と決まっているためにstartの位置を1と設定
print(dfs(dict(tree), 1, m))

Answer 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通りになるはずなのに、
質問のコードではそうなりません。

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

from collections import defaultdict

def dfs(start, visited):
    if len(visited) == n:
        ans.append(0)
    else:
        for c in graph[start]:
            if c not in visited:
                dfs(c, visited + [c])

n, m = map(int, input().split())
tree = defaultdict(list)
for _ in range(m):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

graph = dict(tree)
ans = []
dfs(1, [1])
print(len(ans))

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

from collections import defaultdict

def dfs(start, visited):
    if len(visited) == n:
        ans.append(visited)
    else:
        for c in graph[start]:
            if c not in visited:
                dfs(c, visited + [c])

n, m = map(int, input().split())
tree = defaultdict(list)
for _ in range(m):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

graph = dict(tree)
ans = []
dfs(1, [1])
print(len(ans))
print(ans)

Comments

[kazuma-s]

追記のコードの path は visited と全く同じものだったので、path を削除しました。

[Elmogawa]

わかりやすいご回答ありがとうございます！
確かに再帰を用いた方が簡単に実装できそうですね，，，
また何かありましたら，お願いします！