質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.02%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

PythonでDFSする際にexit status 139が出てしまう

kk_22
kk_22

総合スコア3

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

1回答

0グッド

0クリップ

361閲覧

投稿2022/11/20 10:44

前提

アルゴ式の
https://algo-method.com/tasks/974
の問題を解いている際に一つだけランタイムエラーになってしまいました。

発生している問題・エラーメッセージ

exit status 139

該当のソースコード

Python3

1import sys 2sys.setrecursionlimit(10 ** 8) 3n = int(input()) 4G = [[] for _ in range(n)] 5for _ in range(n - 1): 6 a, b = map(int, input().split()) 7 G[a].append(b) 8 G[b].append(a) 9 10dist = [-1 for _ in range(n)] 11visited = [False for _ in range(n)] 12dist[0] = 0 13 14 15def dfs(v): 16 visited[v] = True 17 for nv in G[v]: 18 if visited[nv]: 19 continue 20 dist[nv] = dist[v] + 1 21 dfs(nv) 22 23 24dfs(0) 25ans = max(dist) 26print(ans)

試したこと

解説のもののコピペはうまく動作しました。
解説の記事と同じアルゴリズムのはずなのですがエラーになってしまいます。

エラーの消し方がわかりません。
よろしくお願いします。

以下のような質問にはグッドを送りましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

グッドが多くついた質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

kk_22

2022/11/20 10:53

間違えました、解説はBFSでやってるので同じではないです が、エラーになるのはよくわかりません

回答1

0

ベストアンサー

再帰呼び出しが深すぎてクラッシュしているものと思われます。

公式のsys.setrecursionlimitの説明に、以下の記述があります。

limit の最大値はプラットフォームによって異なります。深い再帰処理が必要な場合にはプラットフォームがサポートしている範囲内でより大きな値を指定することができますが、この値が大きすぎればクラッシュするので注意が必要です。

つまり、sys.setrecursionlimitにいくら大きい値を設定しても、プラットフォームがサポートしている上限を超える再帰呼び出しはできない(やろうとするとクラッシュする)ということです。

実際、以下のようにコード先頭部分を改変して実行してみたところ(問題の制限内で、再帰呼び出し回数最大となる入力を生成)、Segmentation Faultが発生しました。

python

1import sys 2sys.setrecursionlimit(10 ** 8) 3n = 100000 4G = [[] for _ in range(n)] 5for i in range(n - 1): 6 G[i].append(i + 1) 7 G[i + 1].append(i)

投稿2022/11/20 11:51

編集2022/11/20 11:54
actorbug

総合スコア1767

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

回答へのコメント

kk_22

2022/11/20 15:12

ありがとうございます。ということはAtCoder含めPythonで再帰をやる時にはsys.setrecursion()で回数を決める前に制限について考える必要がありそうですね。

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.02%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。