ATC 001 B Union Find
人間は愚か。えぬわいです。
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の問題に、フーリエ変換の問題があって面白そうだなと思った。(やってない)周波数特性求めるのにしか使ってないので、現実的な問題に即して使えるんだなぁという感じがした。あとでやりたい。