科学の箱

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

automated the boring

まずは肩慣らし print(‘Hello world!’) print(‘What is your name?’) # ask for their na …

no image

空の配列を生成

numpy.empty()を使うと要素が初期化されていない配列を生成できる。要素に入る値はその時により変わるので必ず初期化後には明示的に値を設定する必要がある。 numpy.empty print(n …

no image

seleniumでWebElement object is not iterableが出るときの対処方法

iterableなオブジェクトを想定して要素を取得、forループに取り込むと下記のようなWebElement object is not iterableが出る。 結論としては勘違い。 Seleniu …

no image

seabornで線形解析を実施する

seabornを使えば線形解析も簡単に実行できる。   import seaborn as sns tips = sns.load_dataset(‘tips’) sns.lmplot(x= …

no image

データ分析で理解しておくべきPythonのデータ構造

Pythonでデータ分析を行う際には基本のデータ構造を理解しておく必要がある。 scikit-learnなどのフレームワークは特定のデータ構造を入力とすることを前提にしている。用意したデータがフレーム …

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

side bar top



アーカイブ

カテゴリー