UnionFind

今までSpaghetti Source - 各種アルゴリズムの C++ による実装を コピって使っていたので、改めてアルゴリズムを勉強しなおした。

• Spaghetti Source - Union Find
• Union find(素集合データ構造)
• 互いに素な集合 Union Find| データ構造ライブラリ | Aizu Online Judge

class UnionFind:
    def __init__(self, n):
        self.data = [-1 for i in range(n)]

    def union_set(self, a, b):
        a = self.root(a)
        b = self.root(b)
        if a != b:
            if self.data[b] < self.data[a]:
                a, b = b, a
            self.data[a] += self.data[b]
            self.data[b] = a
        return a != b

    def find_set(self, a, b):
        return self.root(a) == self.root(b)

    def root(self, a):
        if self.data[a] < 0:
            return a
        else:
            self.data[a] = self.root(self.data[a])
            return self.data[a]

Pythonでそのまま書き直しただけ。 dataは非負数は親ノード、負数は木のランクを表しているのか。かしこいなぁ