回答編集履歴
3
path と visited は同じなので、path を削除
answer
CHANGED
|
@@ -41,13 +41,13 @@
|
|
|
41
41
|
```Python
|
|
42
42
|
from collections import defaultdict
|
|
43
43
|
|
|
44
|
-
def dfs(start, visited
|
|
44
|
+
def dfs(start, visited):
|
|
45
45
|
if len(visited) == n:
|
|
46
|
-
ans.append(
|
|
46
|
+
ans.append(visited)
|
|
47
47
|
else:
|
|
48
48
|
for c in graph[start]:
|
|
49
49
|
if c not in visited:
|
|
50
|
-
dfs(c, visited + [c]
|
|
50
|
+
dfs(c, visited + [c])
|
|
51
51
|
|
|
52
52
|
n, m = map(int, input().split())
|
|
53
53
|
tree = defaultdict(list)
|
|
@@ -58,7 +58,7 @@
|
|
|
58
58
|
|
|
59
59
|
graph = dict(tree)
|
|
60
60
|
ans = []
|
|
61
|
-
dfs(1, [1]
|
|
61
|
+
dfs(1, [1])
|
|
62
62
|
print(len(ans))
|
|
63
63
|
print(ans)
|
|
64
64
|
```
|
2
説明の修正
answer
CHANGED
|
@@ -9,7 +9,7 @@
|
|
|
9
9
|
1 4
|
|
10
10
|
2 4
|
|
11
11
|
3 4
|
|
12
|
-
この場合、[1, 2,
|
|
12
|
+
この場合、[1, 2, 4, 3] または [1, 3, 4, 2] の 2通りになるはずなのに、
|
|
13
13
|
質問のコードではそうなりません。
|
|
14
14
|
|
|
15
15
|
私なら次のようなコードを書きます。
|
1
パスを表示するコードを追加
answer
CHANGED
|
@@ -35,4 +35,30 @@
|
|
|
35
35
|
ans = []
|
|
36
36
|
dfs(1, [1])
|
|
37
37
|
print(len(ans))
|
|
38
|
+
```
|
|
39
|
+
**追記**
|
|
40
|
+
次のようにすると、見つかったすべてのパスを表示できます。
|
|
41
|
+
```Python
|
|
42
|
+
from collections import defaultdict
|
|
43
|
+
|
|
44
|
+
def dfs(start, visited, path):
|
|
45
|
+
if len(visited) == n:
|
|
46
|
+
ans.append(path)
|
|
47
|
+
else:
|
|
48
|
+
for c in graph[start]:
|
|
49
|
+
if c not in visited:
|
|
50
|
+
dfs(c, visited + [c], path + [c])
|
|
51
|
+
|
|
52
|
+
n, m = map(int, input().split())
|
|
53
|
+
tree = defaultdict(list)
|
|
54
|
+
for _ in range(m):
|
|
55
|
+
a, b = map(int, input().split())
|
|
56
|
+
tree[a].append(b)
|
|
57
|
+
tree[b].append(a)
|
|
58
|
+
|
|
59
|
+
graph = dict(tree)
|
|
60
|
+
ans = []
|
|
61
|
+
dfs(1, [1], [1])
|
|
62
|
+
print(len(ans))
|
|
63
|
+
print(ans)
|
|
38
64
|
```
|