科学の箱

科学・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

SIGNATE お弁当の需要予測-5

相関の概要を見てみる。これによりどの変数を利用して回帰するかを考える。 sns.heatmap(d_train_w.corr(),cmap=’coolwarm’) Related posts:初めての …

no image

pyperclipを設定する

pyperclipはpip3経由でインストールする。まずはpip3のインストールから。 https://bootstrap.pypa.io/get-pip.pyからget-pip.pyをダウンロードし …

no image

蟻本 P42 硬貨の問題

貪欲法の基本 その時点で最善の手を尽くす 尽くした結果を目的とする値に反映させる。 次善の手になるようにする。 1に戻る 硬貨の問題 A=int(input()) *C,=map(int,input( …

no image

kaggle Titanic Tutorial – 6

さて、今回は年齢について検証する。まずこれまでは中央値を使っていたわけだ。これをもともと年齢分布と中央値を使って更新した後の年齢分布を比較する。 import numpy as nm import p …

no image

flickrapiを使うための手順

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

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

side bar top



アーカイブ

カテゴリー