科学の箱

科学・IT・登山の話題

AtCoder Python

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

投稿日:

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

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

  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]

 

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

メタ情報

inarticle



メタ情報

inarticle



-AtCoder, Python

執筆者:


comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

関連記事

no image

flickrapiを使うための手順

https://stuvel.eu/flickrapiで提供されるflickrapiを利用するにあたり、エラーが出てインストールできない。 condaでは提供されていない pipはSSLError(S …

no image

numpyで配列を抜き出す方法

numpyで配列を抜き出す まず基本となるやり方 arr = np.arange(50).reshape(5,10) arr[1:1,] arr[1:2,]   np.arange(50)で …

no image

カテゴリデータのビジュアル

カテゴリ別データのビジュアル 参考)https://www.kaggle.com/omarelgabry/a-journey-through-titanic?scriptVersionId=44779 …

no image

selectorとxpathを手軽に取得する方法

スクレイピングをするプログラムを開発するときに対象となる項目を取得するためにselector/xpathで指定する。 Google Chromeではselector/xpath値を簡単に取得できる。 …

no image

グラフの軸を操作する

概要 ここでは以下の項目について取り扱う 軸にラベルを設定する ー xlabel, ylabel 軸の最小値、最大値を設定する ー xlim, ylim, xaxis 軸にメモリを設定する ー xti …

2020年10月
« 9月   1月 »
 1234
567891011
12131415161718
19202122232425
262728293031  

side bar top



アーカイブ

カテゴリー