科学の箱

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

kaggle Titanic Tutorial – 3

DecitionTreeのパラメータを調整する。 まずはMaxDepthから from sklearn.model_selection import LeaveOneOut from sklearn. …

no image

タプルの操作

タプルはPythonで提供されているデータ構造の一つ。タプルは固定長で変更できない複数の値の集合である。 タプルオブジェクト (tuple object) — Python 3.8.0 ドキュメント …

no image

pyplotでx軸のラベルを90度回転させる

pyplotでx軸にラベルを記載するとラベル文字数が長すぎるためにお互いにオーバーラップしてみにくい。 このよう場合にはpyplot.xticksを実行する際にrotationを指定すればよい。 Ro …

no image

配列を利用した四則演算とuniversal関数

四則演算 import numpy as np arr = np.arange(1,11) arr arr + arr arr * arr arr – 100 arr – arr [/cde] np. …

no image

特定のパッケージのためのgitignoreを作成したい

https://gitignore.ioを開く パッケージ名を入力 Createをクリック Related posts:automated the boring – day9kaggle Titani …

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

side bar top



最近の投稿

アーカイブ

カテゴリー