アルゴリズムメモ

What is アルゴリズム

ja.wikipedia.org

アルゴリズム力を試すいい場所になるのがAtCoder。 筆者もAtCoderで奮闘中。

メモ

UnionFind

用途

グラフ問題で利用する。競プロ外ではDisjointSetというらしい。

• 閉路を検出したい時

• 異なる2点が同一の島にいるか確認したい時

がつかいどき。特に閉路検出目的で使うことが多い気がする。 木のバランシングなど教育的な要素があるので一度は自前で実装したいところ。

コード

class UnionFind:
    def __init__(self, node_num) -> None:
        self.parent = [i for i in range(node_num+1)]
        self.rank = [1 for i in range(node_num+1)]

    def isSame(self, a, b):
        return self.__getRoot(a) == self.__getRoot(b)
    
    def unite(self, a, b) -> bool:
        if self.isSame(a, b):
            return False

        self.__merge(a, b)
        return True 
    
    def __getRoot(self, a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.__getRoot(self.parent[a])
            return self.parent[a]
    
    def __getRank(self, a):
        return self.rank[self.__getRoot(a)]
    

    def __merge(self, a, b):
        if self.__getRank(a) < self.__getRank(b):
            self.parent[self.__getRoot(a)] = self.__getRoot(b)
        else:
            if self.__getRank(a) == self.__getRank(b):
                self.rank[self.__getRoot(a)] += 1
            self.parent[self.__getRoot(b)] = self.__getRoot(a)

エラトステネスのふるい

内容

n以下の素数を高速に求めることができる。 計算量はO(nloglogn)

コード

def getPrimeListLessThan(n) -> list:
    prime_flag = [True for i in range(n+1)]
    prime_flag[0] = False
    prime_flag[1] = False

    i = 2
    while i*i <= n:
        index = i+i
        if prime_flag[i]:
            while index <= n:
                prime_flag[index] = False
                index += i
        i += 1
    
    prime_list = []

    print(prime_flag)
    for i in range(n+1):
        if prime_flag[i]:
            prime_list.append(i)

    return prime_list.copy()

参考リンク

manabitimes.jp