1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def find(graph: list, x: int) -> int:
    if graph[x] == x:
        return x
    graph[x] = find(graph, graph[x])

def union(graph: list, x: int, y: int) -> None:
    x = find(graph, x)
    y = find(graph, y)
    if x == y:
        return
    graph[y] = x

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Edge:
    def __init__(self, a: int, b: int, cost: int):
        self.parent = a
        self.child = b
        self.cost = cost

def get_parent(graph: list, x: int) -> int:
    if graph[x] == x:
        return x
    graph[x] = get_parent(graph, graph[x])

def union_parent(graph: list, a: int, b: int) -> None:
    a = get_parent(graph, a)
    b = get_parent(graph, b)
    if a < b:
        graph[b] = a
    else:
        graph[a] = b

def find(graph: list, a: int, b: int) -> int:
    a = get_parent(graph, a)
    b = get_parent(graph, b)
    if a == b:
        return True
    else:
        return False

def sort_edge(edge_list: list) -> list:
    return sorted(edge_list, key=lambda x: [x.cost, x.parent, x.child])

def union_edge(graph: list, edge_list: list) -> int:
    cost = 0
    for edge in edge_list:
        if not find(graph, edge.parent, edge.child):
            cost += edge.cost
            union_parent(graph, edge.parent, edge.child)
    return cost