UnionFindを使う問題(ABC292)でのREの解決法(Python)

Question

提出 #40111509 - AtCoder Beginner Contest 292 https://atcoder.jp/contests/abc292/submissions/40111509?lang=ja

上においてテストケース05_hand_01.txtでのみREが起きてしまいます。(経路圧縮のみ実装したunionfindです。)
コード内のクラスUnionFindのメソッドunionにおいて　
self.par[x] = y
を
self.par[y] = x
に置き換えるとACします。
理由がわかりませんので教えていただきたいです。

Comments

[y_waiwai]

コードを提示しよう

[Zuishin]

コードはありますね。

[Zuishin]

v と w が宣言されていますが、w の方は代入と union のみでその後参照されていません。
最後のループで v が使われていますが、ここで参照されるべきデータの一部は v ではなく w に存在する可能性があります。
問題文から、グラフの形に特に制約がないので、複数の辺を持つ頂点、辺を持たない頂点、自分と自分を繋ぐ辺を持つ頂点が存在する可能性があります。

Answer 1

UnionFind.rootの再帰呼び出しが深すぎるのが原因です。
Pythonでは、再帰呼び出しの深さに上限があり、それを超えるとエラーになります。(公式のsys.setrecursionlimitの説明を参照)

UnionFind上で要素が一直線上に並ぶようにしたデータを渡せば、問題を再現できます。
ご提示のコードに、以下の修正を加えたうえで実行してみてください。

# n,m = map(int,input().split()) 
n,m = 200000,199999
uf = UnionFind(n)
 
v = [0]*m
w = [0]*m
for i in range(m):
    # v[i],w[i] = map(int,input().split())
    # v[i] -= 1
    # w[i] -= 1
    v[i], w[i] = i, i+1
    uf.union(v[i],w[i])

もしくは、以下のようなデータを作成して実行してみてください。

200000 199999
1 2
2 3
...
199998 199999
199999 200000

修正方法は、UnionFind.unionにてサイズの大きい方を親とする修正を加えるか、UnionFind.rootを再帰呼び出しを使わずに実装するか、でしょうか。(再帰呼び出しの最大回数が、プラットフォームが定める最大値を超えているので、sys.setrecursionlimitでは解決しません)

Comments

[saw0614]

解答ありがとうございます。
再帰の回数に上限があることは知りませんでした。
xとyを入れ替えてうまくいったのは偶然このテストケースに対しては再帰の回数が減るような選び方だったというだけなのですね。
サイズも考慮したUnionFindを利用しようと思います。