atcoder ABC177＿D pythonでREが発生してしまう

Question

前提・実現したいこと

表題についてpythonで下記の問題のコードを提出したところ、いくつかREが出てしまいました。
どこのロジックが問題なのか全く分からず、途方に暮れています。
どなたかご教授頂けますでしょうか？

対象の問題のＵＲＬ

方針：UnionFindを用いて、連結関係を作成⇒Counterを用いて、連結関係の中で最も最大のものを抽出

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

5つのパターンでREが発生してます

エラーメッセージ

該当のソースコード

from collections import Counter

N,M = map(int,input().split())
par = [i for i in range(N+1)]

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def same(x,y):
    return find(x) == find(y)

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y

for _ in range(M):
    A,B = map(int,input().split())
    if not same(A,B):
        unite(A,B)

for i in range(1,N+1):
    find(i)

S = Counter(par)
answer = max(S.values())

print(answer)

試したこと

ここに問題に対して試したことを記載してください。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Comments

[actorbug]

ABC177にはA-Fの6問ありますが、どれのことでしょうか。
質問を編集して、問題のURLを載せてください。

[pawapoke]

対象の問題のURLを追加しました。
ご指摘本当にありがとうございます。

Answer 1

以下のような入力を与えれば、ローカルでREが再現できると思います。

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

Pythonは再帰呼び出し回数に上限があります。
上記データでfind(1)の再帰呼び出しが何回になるか数えてみてください。

Comments

[pawapoke]

この場合だと再起呼び出しは199998回になりますね。。
pythonは再帰呼び出し回数にdefaultで制限があるのですね。

ひとまず、方針を二つ考えました。
①再帰呼び出し回数の上限を更新する
②クエリの処理のタイミングで、木が深くならないような処理を作る
UnionFindについて理解が浅いと思うので、②の方についてもう少し考えてみようと思います。

actorbugさん、ご回答ありがとうございました。

[pawapoke]

無事、AC通すことが出来ました。
木が深くならないよる考え方があるのですね。勉強になりました。

改めてありがとうございました。