ATC 001 B Union Find

人間は愚か。えぬわいです。

qiita.com

atcoder.jp

Union-find木の講座用の問題らしい。

Union-Find木とは

• グループの併合と判定ができるアルゴリズム
• 併合するのは、グループ同士、判定できるのは、ノード。つまり、グループは木で表される。

初期化

はじめに N 個のノードを用意する。はじめは、辺はない。

併合

片方の木の根からもう片方の木の根に接続する。

判定

それぞれのノードの根を辿り、同じノードだと同じグループ。違かったら別のグループ。

木のランク

ここでは、木を構成する最大段数を意味する。

以下実装。

MAX_N = 100000
par = [0 for i in range(MAX_N)] # par[i] は、ノード i の親ノードの番号
rank = [0 for i in range(MAX_N)] # rank: ノード単体の時が 0

def init(n):
    global par, rank
    for i in range(n):
        par[i] = i # 親は自分自身
        rank[i] = 0 # 単体のとき、rank は 0

# 判定: ノード x の根を求める
def find(x):
    global par
    if par[x] == x: # 根のノードは自分自身が親
        return x
    # return find(par[x]) この場合、縦に連なる場合で最悪ケースになるので改良する
    else:
        par[x] = find(par[x]) # 辿ったノードを根に付け替える
        return par[x]

# 併合: ノード x と ノード y を同じグループにする。考えとしては、根を見つけてつなぐ。

def unite(x, y):
    global rank, par
    root_x = find(x)
    root_y = find(y)
    if root_x == root_y: # そもそも同じグループだった
        return
    if rank[root_x] < rank[root_y]:
        par[root_x] = root_y # ランクの大きい方の根に小さい方の木の根をつなぐ
    elif rank[root_y] < rank[root_x]:
        par[root_y] = root_x
    else:
        par[root_y] = x
        rank[root_x] += 1 # ランクが同じ時だけランクが増える

def same(x, y):
    return find(x) == find(y)

N, Q = map(int, input().split())
init(N)
for i in range(Q):
    p, a, b = map(int, input().split())
    if p == 0:
        unite(a, b)
    else:
        print('Yes' if same(a, b) else 'No')

前蟻本読んだ時より、すんなり入ってきた感じがする。理解深まった感がある。 あと、同じATCの問題に、フーリエ変換の問題があって面白そうだなと思った。(やってない)周波数特性求めるのにしか使ってないので、現実的な問題に即して使えるんだなぁという感じがした。あとでやりたい。