UnionFindのfindについて処理を考える。

UnionFindにおけるfind()もしくはroot()はルート（グループの根）を見つける処理である。

記述方法としては２種類ある。

1. whileループを回す
2. 再帰処理

それぞれについて動きを確認してみた。この時に各要素の親も一緒に更新するようにする。

whileループを利用した処理

こちらのほうが再帰よりメモリ使用量は少ない。しかし更新方法に誤りがあるせいか、親の更新は予想通りに実施されない。

par=[0,2,3,4,5,5]
def find(x):
    while par[x]!=x:
        print(x,par)
        x=par[x]
        par[x]=par[par[x]]
        print(x,par)
    return(x)
find(1)

# 結果が安定しない
# 1 [0, 2, 3, 4, 5, 5]
# 2 [0, 2, 4, 4, 5, 5]
# 2 [0, 2, 4, 4, 5, 5]
# 4 [0, 2, 4, 4, 5, 5]
# 4 [0, 2, 4, 4, 5, 5]
# 5 [0, 2, 4, 4, 5, 5]

再帰を利用した処理

par=[0,2,3,4,5,5]
def find(x,n):
    if x==par[x]:return(x)
    else:
        print(n,x,par)
        par[x]=find(par[x],n+1)
        print(n,x,par)
        return(par[x])
find(1,0)

# 結果が安定する
# 0 1 [0, 2, 3, 4, 5, 5]
# 1 2 [0, 2, 3, 4, 5, 5]
# 2 3 [0, 2, 3, 4, 5, 5]
# 3 4 [0, 2, 3, 4, 5, 5]
# 3 4 [0, 2, 3, 4, 5, 5]
# 2 3 [0, 2, 3, 5, 5, 5]
# 1 2 [0, 2, 5, 5, 5, 5]
# 0 1 [0, 5, 5, 5, 5, 5]

とりあえず再帰処理を利用する。