素敵なデータ構造：Union-Find木 by Python

データ構造の説明

Union-Find木とは、
・根付き木の構造を用いて
・グループ分けを効率的に管理するデータ構造
なようです。

UnionFind.py

class UnionFind():
    par = []
    siz = []
    
    def __init__(self, x):
        self.par = [-1 for n in range(x)]
        self.siz = [1 for n in range(x)]
    
    def root(self, x):
        if self.par[x] == -1:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]
    
    def issame(self, x, y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.siz[x] < self.siz[y]:
            x, y = y, x
        self.par[y] = x
        self.siz[x] += self.siz[y]
        return True
    
    def size(self, x):
        return self.siz[self.root(x)]
        
uf = UnionFind(7)
uf.unite(2, 3)
uf.issame(2, 3)

# 出力 True

アルゴリズムへの適用

連結成分個数カウント

CountConnectedComponent.py

# アルゴリズム定義
# Union-Find木を用いた連結成分個数カウント
def CountConnectedComponent(uf, N):
    res = 0
    for i in range(N):
        if uf.root(i) == i:
            res += 1

    print(res)

# 入力受取
# 頂点数、辺数
N, M = map(int, input().split())

# Union-Find木の生成
# Nで初期化
uf = UnionFind(N)

# グラフの生成
# 各辺の情報をUnion-Find木に追加
for i in range(M):
    a, b = map(int, input().split())
    uf.unite(a, b)

# アルゴリズム実行
# Union-Find木を用いた連結成分個数カウント
CountConnectedComponent(uf, N)

# 入力
# 13 14
# 0 1
# 0 2
# 0 3
# 1 4
# 2 4
# 3 5
# 2 6
# 6 7
# 5 8
# 7 8
# 10 11
# 11 12
# 4 5
# 1 6

# 出力
# 3

クラスカル法

Kruskal.py

# アルゴリズム定義
# クラスカル法
def Kruskal(N, M):
    res = 0    
    uf = UnionFind(N)
    for i in range(M):
        w = edges[i][0]
        u = edges[i][1][0]
        v = edges[i][1][1]

        if uf.issame(u, v):
            continue

        res += w
        uf.unite(u, v)

    print(res)

# 入力受取
# 頂点数、辺数
N, M = map(int, input().split())

# グラフの生成
# 辺(u,v)と重みwの集合
edges = ["" for i in range(M)]
for i in range(M):
    u, v, w = map(int, input().split())
    edges[i] = [w, [u, v]]

# グラフの並び替え
# 重みの小さい順に並び替え
edges.sort()

# アルゴリズム実行
# クラスカル法
Kruskal(N, M)

# 入力
# 4 6
# 0 1 10
# 1 2 20
# 2 3 30
# 3 0 40
# 1 3 15
# 0 2 45

# 出力
# 45