科学の箱

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

StringIOを使ってread_csvのテストをしてみる

pandasで操作できるファイルは様々なあるが、csvはJSONと並んで取り扱うことが多いファイルである。ちょっとしたコードの検証をしたいときに毎回csvを用意して、read_csv()で読み込むのは …

no image

wordpress-xmlrpc

WordPressへPythonから投稿してみる。 まずは設定から。説明はこちらにある。 https://python-wordpress-xmlrpc.readthedocs.io/en/lates …

no image

model.coef_の確認

重回帰分析で重みを確認するには下記を利用する。 model.coef_ ただしこれだと有効桁数が分かりにくいので有効桁数を3桁にして、さらに指数を展開する。 np.set_printoptions(p …

no image

kaggle Titanic Tutorial – 8

前回の結果がいまいちだった。これまではAgeは平均値でNullを埋めていた。平均値では明らか実際のデータと差異が出ると考えられる。そのためAgeがない情報についてより正確なAgeで補完するようにした。 …

no image

numpyで三角関数の数値計算をしてみる

numpyで三角関数の数値計算をしてみる。 ここでは以下を説明する。 三角関数 逆三角関数 角度とラジアンの変換 三角関数 numpyでサイン、コサイン、タンジェントの計算をするためにはnumpy.s …

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

side bar top



アーカイブ

カテゴリー