Editing 2016 Dec Gold Problem 1 Moocast (section)

=== Python ===
<pre>
from sys import stdin
import heapq

def find(curr):
    global parent
    return curr if parent[curr] == curr else find(parent[curr])

def merge(x, y):
    global parent
    parent[find(x)] = find(y)

def main():
    with open("moocast.in", "r") as fin:
        n = int(fin.readline().strip())
        coords = [tuple(map(int, fin.readline().split())) for _ in range(n)]

    parent = list(range(n))
    edges = []

    for i in range(n):
        for j in range(i):
            x1, y1 = coords[i]
            x2, y2 = coords[j]
            distance = (x1 - x2) ** 2 + (y1 - y2) ** 2
            heapq.heappush(edges, (distance, i, j))

    last_weight = 0
    num_components = n

    while num_components > 1:
        weight, i, j = heapq.heappop(edges)
        if find(i) != find(j):
            merge(i, j)
            last_weight = weight
            num_components -= 1

    with open("moocast.out", "w") as fout:
        fout.write(str(last_weight) + "\n")

if __name__ == "__main__":
    main()

</pre>

[[Category:Yearly_2016_2017]]
[[Category:Gold]]
[[Category:Depth-First Search]]
[[Category:Breadth-First Search]]
[[Category:Graph]]
[[Category:Binary Search]]
[[Category:Search]]
[[Category:Union Find]]
[[Category:Flood Fill]]
[[Category:Union-Find]]
[[Category:DFS]]