回答編集履歴
2
再現方法の明示
test
CHANGED
|
@@ -2,6 +2,7 @@
|
|
|
2
2
|
Pythonでは、再帰呼び出しの深さに上限があり、それを超えるとエラーになります。(公式の[sys.setrecursionlimit](https://docs.python.org/ja/3/library/sys.html#sys.setrecursionlimit)の説明を参照)
|
|
3
3
|
|
|
4
4
|
UnionFind上で要素が一直線上に並ぶようにしたデータを渡せば、問題を再現できます。
|
|
5
|
+
ご提示のコードに、以下の修正を加えたうえで実行してみてください。
|
|
5
6
|
```python
|
|
6
7
|
# n,m = map(int,input().split())
|
|
7
8
|
n,m = 200000,199999
|
|
@@ -10,12 +11,20 @@
|
|
|
10
11
|
v = [0]*m
|
|
11
12
|
w = [0]*m
|
|
12
13
|
for i in range(m):
|
|
13
|
-
|
|
14
|
+
# v[i],w[i] = map(int,input().split())
|
|
14
|
-
|
|
15
|
+
# v[i] -= 1
|
|
15
|
-
|
|
16
|
+
# w[i] -= 1
|
|
16
|
-
# uf.union(v[i],w[i])
|
|
17
17
|
v[i], w[i] = i, i+1
|
|
18
18
|
uf.union(v[i],w[i])
|
|
19
19
|
```
|
|
20
|
+
もしくは、以下のようなデータを作成して実行してみてください。
|
|
21
|
+
```
|
|
22
|
+
200000 199999
|
|
23
|
+
1 2
|
|
24
|
+
2 3
|
|
25
|
+
...
|
|
26
|
+
199998 199999
|
|
27
|
+
199999 200000
|
|
28
|
+
```
|
|
20
29
|
|
|
21
30
|
修正方法は、`UnionFind.union`にてサイズの大きい方を親とする修正を加えるか、`UnionFind.root`を再帰呼び出しを使わずに実装するか、でしょうか。(再帰呼び出しの最大回数が、プラットフォームが定める最大値を超えているので、sys.setrecursionlimitでは解決しません)
|
1
別の修正方法を追記
test
CHANGED
|
@@ -18,4 +18,4 @@
|
|
|
18
18
|
uf.union(v[i],w[i])
|
|
19
19
|
```
|
|
20
20
|
|
|
21
|
-
修正する
|
|
21
|
+
修正方法は、`UnionFind.union`にてサイズの大きい方を親とする修正を加えるか、`UnionFind.root`を再帰呼び出しを使わずに実装するか、でしょうか。(再帰呼び出しの最大回数が、プラットフォームが定める最大値を超えているので、sys.setrecursionlimitでは解決しません)
|