Problem:
 Score : 500 points    Problem Statement There are N towns on a plane. The i -th town is located at the coordinates (x_i,y_i) . There may be more than one town at the same coordinates.  You can build a road between two towns at coordinates (a,b) and (c,d) for a cost of min(|a-c|,|b-d|) yen (the currency of Japan). It is not possible to build other types of roads.  Your objective is to build roads so that it will be possible to travel between every pair of towns by traversing roads. At least how much money is necessary to achieve this?      Constraints  2 ≤ N ≤ 10^5  0 ≤ x_i,y_i ≤ 10^9  All input values are integers.         Input Input is given from Standard Input in the following format:  N  x_1  y_1  x_2  y_2 : x_N  y_N       Output Print the minimum necessary amount of money in order to build roads so that it will be possible to travel between every pair of towns by traversing roads.        Sample Input 1 3
1 5
3 9
7 8      Sample Output 1 3  Build a road between Towns 1 and 2 , and another between Towns 2 and 3 . The total cost is 2+1=3 yen.       Sample Input 2 6
8 3
4 9
12 19
18 1
13 5
7 6      Sample Output 2 8

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class UF:
    def __init__(self, N):
        self.state = [-1] * N
        self.rank = [0] * N
        self.num_group = N
    
    def get_parent(self, a):
        p = self.state[a]
        if p < 0:
            return a
        
        q = self.get_parent(p)
        self.state[a] = q
        return q

    def make_pair(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa == pb:
            return

        if self.rank[pa] > self.rank[pb]:
            pa, pb = pb, pa
            a, b = b, a
        elif self.rank[pa] == self.rank[pb]:
            self.rank[pb] += 1

        self.state[pb] += self.state[pa]
        self.state[pa] = pb
        self.state[a] = pb
        self.num_group -= 1
    
    def is_pair(self, a, b):
        return self.get_parent(a) == self.get_parent(b)

    def get_size(self, a):
        return -self.state[self.get_parent(a)]


def main():
    N = int(input())
    X = []
    Y = []
    for i in range(N):
        a, b = read_values()
        X.append((a, i))
        Y.append((b, i))
    
    X.sort()
    Y.sort()

    Q = []
    for i in range(N - 1):
        heapq.heappush(Q, (X[i + 1][0] - X[i][0], (X[i][1], X[i + 1][1])))
        heapq.heappush(Q, (Y[i + 1][0] - Y[i][0], (Y[i][1], Y[i + 1][1])))

    res = 0
    uf = UF(N)
    while uf.num_group != 1:
        c, (a, b) = heapq.heappop(Q)

        if not uf.is_pair(a, b):
            res += c
            uf.make_pair(a, b)

    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
Xs = []
Ys = []
for i in range(N):
    x, y = map(int, input().split())
    Xs.append((x, i))
    Ys.append((y, i))
Xs.sort()
Ys.sort()
Edges = []
for i in range(1, N):
    (x1, v1), (x2, v2) = Xs[i-1], Xs[i]
    Edges.append((abs(x1-x2), v1, v2))
    (y1, v1), (y2, v2) = Ys[i-1], Ys[i]
    Edges.append((abs(y1-y2), v1, v2))

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

import heapq
heapq.heapify(Edges)
uf = UnionFind(N)
ans = 0
while Edges:
    d, a, b = heapq.heappop(Edges)
    if not uf.same(a, b):
        ans += d
        uf.union(a, b)
print(ans)

Solution (Python):

import sys
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X,Y=[],[]
for i in range(N):
    x,y=map(int,input().split())
    X.append((y,i))
    Y.append((x,i))
X.sort(key=lambda t:t[0])
Y.sort(key=lambda t:t[0])
edge=[[] for i in range(N)]
for i in range(N-1):
    edge[X[i][1]].append((abs(X[i][0]-X[i+1][0]),X[i+1][1]))
    edge[X[i+1][1]].append((abs(X[i][0]-X[i+1][0]),X[i][1]))
    edge[Y[i][1]].append((abs(Y[i][0]-Y[i+1][0]),Y[i+1][1]))
    edge[Y[i+1][1]].append((abs(Y[i][0]-Y[i+1][0]),Y[i][1]))

def prim(n,edges):
    used=[False]*n
    used[0]=True
    edgelist=[]
    for edge in edges[0]:
        heappush(edgelist,edge)
    cost=0
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,edge)
        cost+=minedge[0]
    return cost

print(prim(N,edge))

Solution (Python):


import sys

























from operator import itemgetter              




def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    class UnionFindTree:
        def __init__(self, num_of_elm):
            '''
            0 ... num_of_elem - 1 まで数字で表される (0-index) グループを管理する union find tree を作成する (O(n))
            '''
            self.n = num_of_elm
            self.table = [i for i in range(self.n)]    
            self.rank = [0] * self.n    
            self.group_size = [1] * self.n    
        
        def _find_set(self, x):
            '''
            x の属するグループ番号を O(α(n)) で求める
            '''
            parent = self.table[x]
            if x == parent:
                return x
            else:
                root = self._find_set(parent)
                
                self.table[x] = root
                return root
        
        def is_same(self, x, y):
            '''
            x と y が同じグループに属するか O(α(n)) で判定する
            '''
            return self._find_set(x) == self._find_set(y)
    
        def union(self, x, y):
            '''
            x と y の属するグループを O(α(n)) で統合する
            '''
            shallow_root = self._find_set(x)
            deep_root = self._find_set(y)
            if self.rank[shallow_root] > self.rank[deep_root]:
                shallow_root, deep_root = deep_root, shallow_root
            
            if shallow_root == deep_root:
                return False
            
            else:
                self.table[shallow_root] = deep_root
                self.group_size[deep_root] += self.group_size[shallow_root]
                
                if self.rank[shallow_root] == self.rank[deep_root]:
                    self.rank[deep_root] += 1
                return True
    
        def akin_num(self, x):
            '''
            x の属するグループのサイズを O(1) で計算する
            '''
            x_root = self._find_set(x)
            return self.group_size[x_root]
    
        def print_group_id(self):
            print([self._find_set(x) for x in self.table])

    
    def kruskal(edges, n):
        uf = UnionFindTree(n)
        total_cost = 0
        edges.sort(key=itemgetter(2))
        for e in edges:
            u, v, weight = e
            if uf.union(u, v):
                total_cost += weight
        return total_cost


    n = ii()
    appeared = set()
    L = []
    cnt = 0
    for _ in range(n):
        x, y = mi()
        if (x, y) in appeared:    
            n -= 1
            continue
        L.append([cnt, x, y])
        appeared.add((x, y))
        cnt += 1
    
    edges = []
    s = set()
    L.sort(key=itemgetter(1))    
    for j in range(1, n):
        u, v = L[j][0], L[j-1][0]    
        u, v = min(u, v), max(u, v)
        dist = min(abs(L[j][1] - L[j-1][1]), abs(L[j][2] - L[j-1][2]))
        s.add((u, v))
        edges.append((u, v, dist))
    L.sort(key=itemgetter(2))    
    for j in range(1, n):
        u, v = L[j][0], L[j-1][0]    
        u, v = min(u, v), max(u, v)
        
        if (u, v) not in s:
            dist = min(abs(L[j][1] - L[j-1][1]), abs(L[j][2] - L[j-1][2]))
            edges.append((u, v, dist))
    
    print(kruskal(edges, n))
    




if __name__ == "__main__":
    main()

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N=int(input())
G=[]
for i in range(N):
    x,y=map(int,input().split())
    G.append((x,y,i))

Gx=sorted(G,key=lambda x:x[0])
Gy=sorted(G,key=lambda x:x[1])

newG=[]
for i in range(N-1):
    now=Gx[i]
    next=Gx[i+1]
    dist=abs(now[0]-next[0])
    newG.append((dist,now[2],next[2]))

for i in range(N-1):
    now=Gy[i]
    next=Gy[i+1]
    dist=abs(now[1]-next[1])
    newG.append((dist,now[2],next[2]))

newG.sort()

uf=UnionFind(N)
count=N
ans=0
for c,i,j in newG:
    if count==0:
        break

    if not uf.same(i,j):
        ans+=c
        uf.union(i,j)
        count-=1

print(ans)

Solution (Python):
class UF():
  def __init__(self, N):
    self.par = [-1]*N

  def find(self, x):
    if self.par[x] < 0:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]

  def union(self, x,y):
    p1,p2 = self.find(x),self.find(y)
    if p1 == p2: return
    if p1 > p2:
      p1,p2 = p2,p1
    self.par[p1] += self.par[p2]
    self.par[p2] = p1

  def same(self, x,y):
    return self.find(x) == self.find(y)

N = int(input())
coordinates = []
for i in range(N):
  x,y = list(map(int, input().split()))
  coordinates.append((i,x,y))

edges = []

sort_x = sorted(coordinates, key=lambda x: x[1])
for i in range(N-1):
  u,v = sort_x[i][0], sort_x[i+1][0]
  edges.append([u,v,abs(sort_x[i][1] - sort_x[i+1][1])])

sort_y = sorted(coordinates, key=lambda x: x[2])
for i in range(N-1):  
  u,v = sort_y[i][0], sort_y[i+1][0]
  edges.append([u,v,abs(sort_y[i][2] - sort_y[i+1][2] )])

edges.sort(key=lambda x: x[2])
uf = UF(N)
res = 0
for u,v,c in edges:
  if not uf.same(u,v):
    uf.union(u,v)
    res += c

print(res)

Solution (Python):
from operator import itemgetter


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same(self, x, y):
        if self.find(x) == self.find(y):
            return True
        else:
            return False


def kruskal(n, edges):
    uf = UnionFind(n)
    edges.sort()
    res = 0
    for d, s, t in edges:
        if not uf.same(s, t):
            uf.unite(s, t)
            res += d
    return res

n = int(input())

xy = [[i] + list(map(int, input().split())) for i in range(n)] 

edges = set()
for key in [itemgetter(1), itemgetter(2)]:
    xy.sort(key = key)
    for i in range(n-1):
        i1, x1, y1 = xy[i]
        i2, x2, y2 = xy[i+1]
        d = min(abs(x1 - x2), abs(y1 - y2))
        edges.add((d, i1, i2))

edges = list(edges)
print(kruskal(n, edges))

Solution (Python):
n = int(input())
plots = []
for i in range(n):
    x, y = map(int, input().split())
    plots.append((x, y, i))
edges = []
plots.sort(key=lambda x: x[0])
for k in range(n-1):
    x0, _, i = plots[k]
    x1, _, j = plots[k+1]
    edges.append((x1 - x0, i, j))

plots.sort(key=lambda x: x[1])
for k in range(n-1):
    _, y0, i = plots[k]
    _, y1, j = plots[k+1]
    edges.append((y1 - y0, i, j))



par = [i for i in range(n)]
size = [1 for _ in range(n)]
rank = [0 for _ in range(n)]
def find(x):  
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] > rank[y]:
        par[y] = x
        size[x] += size[y]
    else:
        par[x] = y
        size[y] += size[x]
        if rank[x] == rank[y]:
            rank[y] += 1
def same(x, y):
    return find(x) == find(y)


def kruskal():
    edges.sort()

    res = 0
    for i in range(len(edges)):
        cost, u, v = edges[i]
        if not same(u, v):
            unite(u, v)
            res += cost

    return res

print(kruskal())

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

from itertools import permutations
n = int(input())
list_XY = []
list_CO = []
for i in range(n):
    x, y = map(int, input().split())
    list_XY.append([x, y, i])

list_XY.sort(key=lambda x:x[0])
for i in range(n-1):
    list_CO.append([list_XY[i][2], list_XY[i+1][2], abs(list_XY[i][0]-list_XY[i+1][0])])

list_XY.sort(key=lambda x:x[1])
for i in range(n-1):
    list_CO.append([list_XY[i][2], list_XY[i+1][2], abs(list_XY[i][1]-list_XY[i+1][1])])

list_CO.sort(key=lambda x:x[2])
uf = UnionFind(n)
ans = 0

for i, j, cost in list_CO:
    if not uf.same(i, j):
        uf.union(i, j)
        ans += cost
    if uf.size(0) == n:
        break

print(ans)

Solution (Python):
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
        else:
            self.parents[xRoot] = yRoot
            if self.size[xRoot] == self.size[yRoot]:
                self.size[yRoot]+=1

N = int(input())
edges = []
nodes = []
for i in range(N):
    x,y = map(int,input().split())
    nodes.append((i,x,y))
nodes.sort(key=lambda x: x[1])
for i in range(1,N):
    w = nodes[i][1]-nodes[i-1][1]
    edges.append((w,nodes[i][0],nodes[i-1][0]))
nodes.sort(key=lambda x: x[2])
for i in range(1,N):
    w = nodes[i][2] - nodes[i-1][2]
    edges.append((w,nodes[i][0],nodes[i-1][0]))
edges.sort()
tree = UnionFind(N)
cost = 0
for w,a,b in edges:
    if tree.find(a) != tree.find(b):
        tree.unite(a,b)
        cost += w
print(cost)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n = int(input())
graphx = []
graphy = []

for i in range(n):
    x,y = map(int,input().split())
    graphx.append((x,y,i))
    graphy.append((x,y,i))
graphx = sorted(graphx, key=lambda x:x[0])
graphy = sorted(graphy, key=lambda x:x[1])
graph = []


for k in range(n-1):
    i,j = graphx[k][2], graphx[k+1][2]
    x0,x1 = graphx[k][0],graphx[k+1][0]
    m = abs(x0-x1)
    graph.append((m,i,j))

for k in range(n-1):
    i,j = graphy[k][2], graphy[k+1][2]
    y0,y1 = graphy[k][1],graphy[k+1][1]
    m = abs(y0-y1)
    graph.append((m,i,j))


graph.sort()


ans = 0
uf = UnionFind(n)
for c,i,j in graph:
    if not uf.same(i,j):
        ans += c
        uf.union(i,j)
print(ans)

Solution (Python):
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix

N = int(input())
A = []
for i in range(N):
    x, y = map(int, input().split())
    A.append((i, x, y))

length, frm, to = [], [], []
path_set = set()


def path(axis):
    A.sort(key=lambda x: x[axis])
    for i in range(N - 1):
        if (A[i][0], A[i + 1][0]) in path_set:
            continue
        length.append(min(abs(A[i][1] - A[i + 1][1]),
                          abs(A[i][2] - A[i + 1][2])))
        frm.append(A[i][0])
        to.append(A[i + 1][0])
        path_set.add((A[i][0], A[i + 1][0]))


path(1)
path(2)
matr = csr_matrix((length, (frm, to)), shape=(N, N))

T = minimum_spanning_tree(matr).astype(int)
print(sum(T.data))

Solution (Python):

from heapq import *
def solve():
    N = int(input())
    A = [list(map(int, input().split()))+[i] for i in range(N)]
    edge = [[] for _ in range(N)]
    A.sort()
    for i in range(N-1):
        w = A[i+1][0]-A[i][0]
        edge[A[i][2]].append((w,A[i+1][2]))
        edge[A[i+1][2]].append((w,A[i][2]))
    A.sort(key=lambda x:x[1])
    for i in range(N-1):
        w = A[i+1][1]-A[i][1]
        edge[A[i][2]].append((w,A[i+1][2]))
        edge[A[i+1][2]].append((w,A[i][2]))
    bridges = []
    heapify(bridges)
    used = [False]*N
    used[0] = True
    ans = 0
    for w,v in edge[0]:
        heappush(bridges,(w,v))
    while len(bridges)>0:
        w,v = heappop(bridges)
        if used[v]==False:
            ans += w
            used[v] = True
            for w,u in edge[v]:
                if used[u]==False:
                    heappush(bridges,(w,u))
    return ans
print(solve())

Solution (Python):

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
                x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def nums(self,x):
        return abs(self.parents[self.find(x)])

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N = int(input())
A = [list(map(int, input().split()))+[i] for i in range(N)]
edge = []
A.sort()
for i in range(N-1):
    w = A[i+1][0]-A[i][0]
    edge.append((w,A[i][2],A[i+1][2]))
A.sort(key=lambda x:x[1])
for i in range(N-1):
    w = A[i+1][1]-A[i][1]
    edge.append((w,A[i][2],A[i+1][2]))

edge.sort()

uf = UnionFind(N)
ans = 0
for i in range(len(edge)):
    u,x,y = edge[i]
    if not uf.same(x,y):
        uf.union(x,y)
        ans += u
print(ans)

Solution (Python):

from heapq import *
def solve():
    N = int(input())
    A = [list(map(int, input().split()))+[i] for i in range(N)]
    edge = [[] for _ in range(N)]
    A.sort()
    for i in range(N-1):
        w = min(abs(A[i+1][0]-A[i][0]),abs(A[i+1][1]-A[i][1]))
        edge[A[i][2]].append((w,A[i+1][2]))
        edge[A[i+1][2]].append((w,A[i][2]))
    A.sort(key=lambda x:x[1])
    for i in range(N-1):
        w = min(abs(A[i+1][0]-A[i][0]),abs(A[i+1][1]-A[i][1]))
        edge[A[i][2]].append((w,A[i+1][2]))
        edge[A[i+1][2]].append((w,A[i][2]))
    bridges = []
    heapify(bridges)
    used = [False]*N
    used[0] = True
    ans = 0
    for w,v in edge[0]:
        heappush(bridges,(w,v))
    while len(bridges)>0:
        w,v = heappop(bridges)
        if used[v]==False:
            ans += w
            used[v] = True
            for w,u in edge[v]:
                if used[u]==False:
                    heappush(bridges,(w,u))
    return ans
print(solve())

Solution (Python):
import sys;sys.setrecursionlimit(10**9)
class UnionFind:
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
    self.siz=n
  def find_root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.find_root(self.n[x])
      return self.n[x]
  def unite(self,x,y):
    x=self.find_root(x)
    y=self.find_root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:
      self.n[x]+=self.n[y]
      self.n[y]=x
    else:
      self.n[y]+=self.n[x]
      self.n[x]=y
      if self.r[x]==self.r[y]:
        self.r[y]+=1
    self.siz-=1
  def root_same(self,x,y):
    return self.find_root(x)==self.find_root(y)
  def count(self,x):
    return -self.n[self.find_root(x)]
  def size(self):
    return self.siz

n=int(input())
xy=[list(map(int,input().split()))+[i]for i in range(n)]
xy.sort()
edge=[]
for j in range(1,n):
  sx,sy,si=xy[j-1]
  tx,ty,ti=xy[j]
  edge.append((min(abs(sx-tx),abs(sy-ty)),si,ti))
xy.sort(key=lambda x:x[1])
for j in range(1,n):
  sx,sy,si=xy[j-1]
  tx,ty,ti=xy[j]
  edge.append((min(abs(sx-tx),abs(sy-ty)),si,ti))
u=UnionFind(n)
ans=0
edge.sort()
for c,x,y in edge:
  if u.root_same(x,y):continue
  u.unite(x,y)
  ans+=c
print(ans)

Solution (Python):
class Kruskal():
    def __init__(self,n):
        self.e = []
        self.par = [i for i in range(n+1)]  
        self.rank = [0]*(n+1)
    def add(self,u,v,d):  
        self.e.append([u,v,d])
    def find(self,x):  
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self,x,y):  
        return self.find(x) == self.find(y)
    def unite(self,x,y):  
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1
    def Kruskal(self):
        edges = sorted(self.e,key=lambda x: x[2])  
        a = 0
        for e in edges:
            if not self.same_check(e[0],e[1]):
                self.unite(e[0],e[1])
                a += e[2]
        return a

N = int(input())
A = [list(map(int,input().split())) for i in range(N)]

G = Kruskal(N)

X = []
Y = []
for i in range(N):
    X.append((A[i][0], i))
    Y.append((A[i][1], i))

X = sorted(X)
Y = sorted(Y)



for i in range(N - 1):
    G.add(X[i][1], X[i + 1][1], X[i + 1][0] - X[i][0])
    G.add(Y[i][1], Y[i + 1][1], Y[i + 1][0] - Y[i][0])

print(G.Kruskal())

Solution (Python):
from sys import stdin, setrecursionlimit
from operator import itemgetter

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


class UnionFind:
    
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)


N = int(input())
P = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    P[i] = (i, x, y)

edges = []
for i in (1, 2):
    P.sort(key=itemgetter(i))
    for j in range(N - 1):
        edges.append((P[j][0], P[j + 1][0], P[j + 1][i] - P[j][i]))

edges.sort(key=itemgetter(2))
uf = UnionFind(N)
ans = 0
cities = 1
for i, j, c in edges:
    if not uf.same(i, j):
        uf.union(i, j)
        ans += c
        cities += 1
        if cities == N:
            break

print(ans)

Solution (Python):
from sys import stdin, setrecursionlimit
from operator import itemgetter

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


class UnionFind:
    
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)


N = int(input())
P = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    P[i] = (i, x, y)

edges = []
for i in (1, 2):
    P.sort(key=itemgetter(i))
    for j in range(N - 1):
        edges.append((P[j][0], P[j + 1][0], P[j + 1][i] - P[j][i]))

edges.sort(key=itemgetter(2))
uf = UnionFind(N)
ans = 0
cities = 1
for i, j, c in edges:
    if not uf.same(i, j):
        uf.union(i, j)
        ans += c
        cities += 1
        if cities == N:
            break

print(ans)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)


N = int(input())
x, y = [], []
for i in range(N):
    a, b = map(int, input().split())
    x.append([a, i])
    y.append([b, i])
x.sort()
y.sort()

e = []
for i in range(N-1):
    e.append([abs(x[i][0]-x[i+1][0]), x[i][1], x[i+1][1]])
    e.append([abs(y[i][0]-y[i+1][0]), y[i][1], y[i+1][1]])

e.sort()

uft = UnionFind(N)

ans = 0
for w, s, t in e:
    if not uft.same(s, t):
        uft.union(s, t)
        ans += w

print(ans)

Solution (Python):

import numpy as np
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix
from operator import itemgetter
def resolve():
    N = int(input())
    XY = [[i] + [int(x) for x in input().split()] for i in range(N)]

    G = set()
    for key in [itemgetter(1), itemgetter(2)]:
        XY.sort(key=key)
        for i in range(N - 1):
            i1, x1, y1 = XY[i]
            i2, x2, y2 = XY[i + 1]
            d = min(abs(x1 - x2), abs(y1 - y2))
            G.add((i1, i2, d))    

    A, B, W = zip(*G)
    csr = csr_matrix((W, (A, B)), shape=(N, N))
    mst = minimum_spanning_tree(csr).astype(int)
    print(mst.sum())

if __name__ == "__main__":
    resolve()