Union Find

コードについての説明

Unionf Find は競技プログラミングでは基本的なアルゴリズムなので, 説明は蟻本またはこのスライドにゆずる.
各クエリの計算量は数学的には解析が難しいが, 実用上は定数と考えて問題ない.

(計算量の細かい話)
計算量は $m(\ge n)$ 回の Find 操作, $n$ 回の Union 操作のクエリ列を処理するのに $\O (n + m \alpha(m, n))$ 時間であることが証明されている(後の解析で $\O (n + m \alpha(m + n, n))$ 時間に落ちることがわかっている). ここで $\alpha(m, n)$ はアッカーマン関数 $A(i, j)$ を用いて以下のように定義される.
まず増加の非常に急激な関数であるアッカーマン関数は $A(i, j)$ は以下のように再帰的に定義される.
$A(1, j) = 2^j (j \ge 1)$, $A(i, 1) = A(i - 1, 2) (i \ge 2)$, $A(i, j) = A(i - 1, A(i, j - 1)) (i, j \ge 2)$
このとき $\alpha(m, n) = \min \{ i \ge 1 \mid A(i, 4 \lceil m / n \rceil) > \log n \}$ と定義される. これを見ると $m = \Omega(n \log \log n)$ で $\alpha(m, n) = 1$, $m = \Omega(n \log^* n)$ で $\alpha(m, n) \le 2$ みたいなことが分かり, 要をするにアッカーマン関数の逆関数 $\alpha(m, n)$ は実用上定数と考えてよい..
次に $a(i, n) = \min \{ j \ge 1 \mid A(i, j) > \log n \}$ を定義する. このとき任意の正整数 $k$(定数) について $m (\ge n a(k, n))$ 回の Find 操作, $n$ 回の Union 操作のクエリ列を処理するのにかかる時間は $\O (m)$ time であることも言える($\alpha(n a(k, n), n) \le k$ より). Union Find の計算量の解析の論文としては "Efficiency of a Good But Not Linear Set Union Algorithm" [Tarjan 1975] や "Worst-Case Analysis of Set Union Algorithms" [Tarjan, LEEUWEN 1984] が詳しい.

過去に上記論文の簡易版として Union Find の計算量についての記事を昔書きました. 簡単ではないので興味のある方は読んでみてください.
U-TOKYO AP Advent Calendar 2017 8 日目: Union Find の計算量の話

時間計算量: Find クエリ, Union クエリ ならし $\O (\alpha(m, n))$ ($\alpha(m, n)$ は上記で定義された増加の非常にゆるやかな関数. 実用上は定数と考えて良い.)

コード

class UnionFind:
    def __init__(self, node_size):
        self._node = node_size
        self.par = [i for i in range(self._node)]
        self.size_ = [1] * self._node

    def find(self, ver):
        if self.par[ver] == ver:
            return ver
        else:
            self.par[ver] = self.find(self.par[ver])
            return self.par[ver]

    def unite(self, ver1, ver2):
        ver1, ver2 = self.find(ver1), self.find(ver2)
        if ver1 == ver2:
            return
        if self.size_[ver1] < self.size_[ver2]:
            ver1, ver2 = ver2, ver1
        self.par[ver2] = ver1
        self.size_[ver1] += self.size_[ver2]

    def size(self, ver):
        ver = self.find(ver)
        return self.size_[ver]

    def same(self, ver1, ver2):
        return self.find(ver1) == self.find(ver2)

if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())
    uf = UnionFind(n)
    for i in range(m):
        s, t = map(int, sys.stdin.readline().split())
        uf.unite(s, t)
    q = int(sys.stdin.readline())
    for i in range(q):
        s, t = map(int, sys.stdin.readline().split())
        if uf.same(s, t):
            print("yes")
        else:
            print("no")

verify 用の問題

AOJ : Connected Components 提出コード