import numpy as np

#Kruskal Algorithm
parent = dict()
rank = dict()

def make_singleton_set(v) :
    parent[v] = v
    rank[v] = 1

def find(v) :
    if(parent[v] != v) :
        parent[v] = find(parent[v])
    return parent[v]

def union(r1, r2) :
    if(r1 != r2) :
        if(rank[r1] > rank[r2]) :
            parent[r2] = r1
            rank[r1] += rank[r2]
        else :
            parent[r1] = r2
            if(rank[r1] == rank[r2]) :
                rank[r2] += rank[r1]

def Kruskal(graph) :
    #n =  정점의 수 / m = 엣지의 수
    n = len(graph['vertices'])
    m = len(graph['edges'])

    #엣지를 전부 찾은 후 비내림차순으로 정렬한다.
    edge_list = list(graph['edges'])
    edge_list.sort()

    #초기화한다
    for v in graph['vertices'] :
        make_singleton_set(v)

    F = set()

    index = 0
    while len(F) < n - 1 :
        e = edge_list[index]

        p = find(e[1])
        q = find(e[2])

        if(p == q) :
            union(p, q)
            F.add(e)
            index += 1

    return F

graph = {
        'vertices': ['A', 'B', 'C', 'D', 'E'],
        'edges': set([
            (1, 'A', 'B'),
            (3, 'A', 'C'),
            (3, 'B', 'C'),
            (6, 'B', 'D'),
            (4, 'C', 'D'),
            (2, 'C', 'E'),
            (5, 'D', 'E'),
            ])
        }

mst = Kruskal(graph)
print(mst)