UnionFindにおけるfind()もしくはroot()はルート(グループの根)を見つける処理である。
記述方法としては2種類ある。
- whileループを回す
- 再帰処理
それぞれについて動きを確認してみた。この時に各要素の親も一緒に更新するようにする。
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]
とりあえず再帰処理を利用する。