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 sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    
    class UnionFind():
        def __init__(self, n):
            self.nodes=[-1] * n  

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

        def unite(self, x, y):
            root_x=self.get_root(x)
            root_y=self.get_root(y)
            
            
            
            if root_x != root_y:
                
                if self.nodes[root_x] < self.nodes[root_y]:
                    big_root=root_x
                    small_root=root_y
                else:
                    small_root=root_x
                    big_root=root_y
                self.nodes[big_root] += self.nodes[small_root]
                self.nodes[small_root]=big_root
    
    N = I()
    uf=UnionFind(N)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes
    xlist = []
    ylist = []
    for i in range(N):
        x, y = MI()
        xlist.append((x, i))
        ylist.append((y, i))
    xlist.sort()
    ylist.sort()
    
    edges = [] 
    for i in range(N - 1):
        edges.append((xlist[i+1][0]-xlist[i][0], xlist[i][1],xlist[i+1][1]))
        edges.append((ylist[i+1][0]-ylist[i][0],ylist[i][1], ylist[i + 1][1]))
    edges.sort(reverse=True)

    cnt = 1
    ans=0
    while cnt<N:
        c, a, b = edges.pop()
        if get_root(a) != get_root(b):
            unite(a, b)
            cnt += 1
            ans += c
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
import heapq


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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


n = int(input())
x_list = [(0, 0)] * n
y_list = [(0, 0)] * n
for i in range(n):
    x, y = map(int, input().split())
    x_list[i] = (x, i)
    y_list[i] = (y, i)
x_list.sort()
y_list.sort()
h = []
heapq.heapify(h)
for i in range(n - 1):
    x1, ix1 = x_list[i]
    x2, ix2 = x_list[i + 1]
    y1, iy1 = y_list[i]
    y2, iy2 = y_list[i + 1]
    heapq.heappush(h, (x2 - x1, ix1, ix2))
    heapq.heappush(h, (y2 - y1, iy1, iy2))

ans = 0
uf = UnionFind(n)
while h:
    w, s, t = heapq.heappop(h)
    if not uf.same_check(s, t):
        ans += w
        uf.union(s, t)
print(ans)

Solution (Python):





from heapq import heappush, heappop


class UnionFind(object):

    def __init__(self, N):
        self.tree = [i for i in range(N)]
        self.rank = [0] * (N + 1)

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

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

        
        if self.rank[x] < self.rank[y]:
            self.tree[x] = y
        else:
            self.tree[y] = x

        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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


class Edge(object):

    def __init__(self, src, dst, cost):
        self.src = src
        self.dst = dst
        self.cost = cost


def mst_kruskal():
    """
    kruskalのアルゴリズムによって最小全域木を構成する。

    :return: 最小全域木、つまりMSTに含まれる辺のリスト
    """
    pass


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


edges = list()
V.sort(key=lambda v: v[1])
for i in range(1, N):
    (src_i, src_x, src_y), (dst_i, dst_x, dst_y) = V[i - 1], V[i]
    heappush(edges, (abs(dst_x - src_x), src_i, dst_i))
V.sort(key=lambda v: v[2])
for i in range(1, N):
    (src_i, src_x, src_y), (dst_i, dst_x, dst_y) = V[i - 1], V[i]
    heappush(edges, (abs(dst_y - src_y), src_i, dst_i))

total_cost = 0
uf = UnionFind(N)
while len(edges) != 0:
    cost, src, dst = heappop(edges)
    if uf.find(src) != uf.find(dst):
        uf.unite(src, dst)
        total_cost += cost

print(total_cost)

Solution (Python):
N=int(input())
city=[0]*N
for i in range(N):
    x,y=map(int,input().split())
    city[i]=(i,x,y)
city.sort(key=lambda x:x[1])
data=[(city[i][0],city[i+1][0],city[i+1][1]-city[i][1]) for i in range(N-1)]
city.sort(key=lambda x:x[2])
data+=[(city[i][0],city[i+1][0],city[i+1][2]-city[i][2]) for i in range(N-1)]
data.sort(key=lambda x:x[2])
root=[-1]*N
def search(i):
    global root
    if root[i]>=0:
        root[i]=search(root[i])
        return root[i]
    return i
cost=0
for i,j,k in data:
    ri=search(i)
    rj=search(j)
    if ri==rj:
        continue
    elif root[ri]<=root[rj]:
        cost+=k
        root[ri]+=root[rj]
        root[rj]=ri
    elif root[ri]>root[rj]:
        cost+=k
        root[rj]+=root[ri]
        root[ri]=rj
print(cost)

Solution (Python):


import itertools
from collections import Counter
from collections import defaultdict
import collections
from functools import reduce
import bisect
import math
import heapq
import copy


class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]  
        self.size = [1 for _  in range(size)]

    
    def find(self,x):
        while self.table[x] >= 0:
            
            x = self.table[x]
        return x

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

    
    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                    self.size[s1] += self.size[s2]
                else:
                    self.table[s1] = s2
                    self.size[s2] += self.size[s1]
            else:
                
                
                self.table[s1] += -1
                self.table[s2] = s1
                self.size[s1] += self.size[s2]
        return

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

Edge = collections.namedtuple("Edge", "start end weight")


def solve_by_kraskal(n, edges):
    """
        最小全域木を計算してそのルートを返す
        Parameters
        ----------
        n : int
            頂点の数
        edges: [Edge]
            辺のリスト

        Returns
        -------
        route : [Edge]
            最小全域木を構築する辺
    """

    edges.sort(key=lambda edge: edge.weight)
    uf = UnionFind(n)
    route = []

    for edge in edges:
        if not uf.is_same(edge.start, edge.end):
            uf.union(edge.start, edge.end)
            route.append(edge)

    return route


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

    x_dots.sort(key=lambda x: x[1])
    y_dots = copy.copy(x_dots)
    y_dots.sort(key=lambda x: x[2])
    
    

    x_edges = []
    for i in range(N - 1):
        dot = x_dots[i]
        next_dot = x_dots[i + 1]
        x_edges.append(Edge(dot[0], next_dot[0], min(abs(dot[1] - next_dot[1]), abs(dot[2] - next_dot[2]))))
        x_edges.append(Edge(next_dot[0], dot[0], min(abs(dot[1] - next_dot[1]), abs(dot[2] - next_dot[2]))))

    y_edges = []
    for i in range(N - 1):
        dot = y_dots[i]
        next_dot = y_dots[i + 1]
        y_edges.append(Edge(dot[0], next_dot[0], min(abs(dot[1] - next_dot[1]), abs(dot[2] - next_dot[2]))))
        y_edges.append(Edge(next_dot[0], dot[0], min(abs(dot[1] - next_dot[1]), abs(dot[2] - next_dot[2]))))

    route = solve_by_kraskal(N, x_edges + y_edges)
    ans = 0
    for r in route:
        ans += r[2]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind:
    
    def __init__(self, n):
        
        self.par = [-1] * n
        
        self.rank = [0] * 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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x != y:
            
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            
            self.par[x] += self.par[y]
            self.par[y] = x

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

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


from operator import itemgetter

n = int(input())

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

x = sorted(xy,key=itemgetter(1))
y = sorted(xy,key=itemgetter(2))

xx = []
yy = []

for i in range(n-1):
    xx.append([x[i][0],x[i+1][0],x[i+1][1]-x[i][1]])
    yy.append([y[i][0],y[i+1][0],y[i+1][2]-y[i][2]])

xx.sort(key=itemgetter(2))
yy.sort(key=itemgetter(2))
xx.reverse()
yy.reverse()

a = UnionFind(n)

ans = 0

i = 0
xxx = xx.pop()
yyy = yy.pop()
while i!=n-1:
    if xxx[2] < yyy[2]:
        if not a.same(xxx[0],xxx[1]):
            a.unite(xxx[0],xxx[1])
            ans += xxx[2]
            i += 1
        if xx:
            xxx = xx.pop()
        else:
            xxx = [0,0,float('inf')]
    else:
        if not a.same(yyy[0],yyy[1]):
            a.unite(yyy[0],yyy[1])
            ans += yyy[2]
            i += 1
        if yy:
            yyy = yy.pop()
        else:
            yyy = [0,0,float('inf')]
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
from scipy.sparse import csr_matrix
import numpy as np

N = int(input())

XY = [[i] + [int(x) for x in input().split()] for i in range(N)]

edge = 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))
    edge.add((i1,i2,d))
    

row,col,value = zip(*edge)
value = np.array(value,dtype=int)
graph = csr_matrix((value,(row,col)),shape=(N,N))


from scipy.sparse.csgraph import minimum_spanning_tree
tree = minimum_spanning_tree(graph, overwrite = True).astype(int)
answer = tree.sum()
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
from scipy.sparse import csr_matrix
import numpy as np

N = int(input())

XY = [[i] + [int(x) for x in input().split()] for i in range(N)]

edge = 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))
    edge.add((i1,i2,d))
    

edge = sorted(list(edge))
row,col,value = zip(*edge)
value = np.array(value,dtype=int)
graph = csr_matrix((value,(row,col)),shape=(N,N))


from scipy.sparse.csgraph import minimum_spanning_tree
tree = minimum_spanning_tree(graph, overwrite = True).astype(int)
answer = tree.sum()
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
from scipy.sparse import csr_matrix
import numpy as np

N = int(input())

XY = [[i] + [int(x) for x in input().split()] for i in range(N)]

edge = [set() for _ in range(N)]
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))
    edge[i1].add((i2,d))
    

col = []
row = []
value = []
for i in range(N):
  for j,v in edge[i]:
    col.append(i)
    row.append(j)
    value.append(v)
value = np.array(value,dtype=int)
graph = csr_matrix((value,(row,col)),shape=(N,N))


from scipy.sparse.csgraph import minimum_spanning_tree
tree = minimum_spanning_tree(graph, overwrite = True).astype(int)
answer = tree.sum()
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
from scipy.sparse import csr_matrix
import numpy as np

N = int(input())

XY = [[i] + [int(x) for x in input().split()] for i in range(N)]

edge = [set() for _ in range(N)]
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))
    edge[i1].add((i2,d))
    

indptr = []
indrow = []
value = []
ptr = 0
for i in range(N):
  indptr.append(ptr)
  for j,v in edge[i]:
    indrow.append(j)
    value.append(v)
    ptr += 1
indptr.append(ptr)
value = np.array(value,dtype=int)
graph = csr_matrix((value,indrow,indptr),shape=(N,N))


from scipy.sparse.csgraph import minimum_spanning_tree
tree = minimum_spanning_tree(graph, overwrite = True).astype(int)
answer = tree.sum()
print(answer)

Solution (Python):
from heapq import heappush, heappop

def prim(ad): 
    N = len(ad)
    used = [0]*N
    hq = []
    for ad_i in ad[0]:
        heappush(hq, ad_i)
    used[0] = 1
    res = 0
    while hq:
        w, v = heappop(hq)
        if used[v]: continue
        used[v] = 1
        for nw, nv in ad[v]:
            if used[nv]: continue
            heappush(hq, (nw, nv))
        res += w
    return res

N = int(input())
X = []
Y = []

for i in range(N):
    x, y = map(int,input().split())
    X.append((x,i))
    Y.append((y,i))

X.sort()
Y.sort()

ad = [[] for _ in range(N)]

for t in range(N-1):
    a, i = X[t]
    c, j = X[t+1]
    wx = abs(a-c)
    ad[i].append((wx,j))
    ad[j].append((wx,i))
    b, k = Y[t]
    d, l = Y[t+1]
    wy = abs(b-d)
    ad[k].append((wy,l))
    ad[l].append((wy,k))

ans = prim(ad)
print(ans)

Solution (Python):
N = int(input())

li = [ [int(it) for it in input().split() ] for i in range(N) ]

lix = [0]*N
liy = [0]*N
for i in range(N):
  lix[i] = (i,li[i][0])
  liy[i] = (i,li[i][1])
lix.sort( key=lambda x:x[1] )
liy.sort( key=lambda x:x[1] )

edge = [0]*(2*(N-1))
c = 0
for i in range(N-1):
  edge[c] = ( lix[i][0],lix[i+1][0], lix[i+1][1] - lix[i][1] )
  c +=1
  edge[c] = ( liy[i][0],liy[i+1][0], liy[i+1][1] - liy[i][1] )
  c +=1

edge.sort ( key = lambda x:x[2] )

class Union():
  def __init__(me,N):
    me.N = N
    me.up = [-1]*N
    me.down = [ [] for i in range(N) ]
  def union(me,a,b):
    ua = me.up[a] if me.up[a]!=-1 else a
    ub = me.up[b] if me.up[b]!=-1 else b
    if (ua == ub):
      return
    if ( len(me.down[ua]) < len(me.down[ub]) ):
      ub,ua = ua,ub
    for v in me.down[ub]:
      me.up[v] = ua
    me.down[ua].extend( me.down[ub] )
    me.down[ub] = []
    me.up[ub] = ua
    me.down[ua].append( ub )
  def count(me,a):
    ua = me.up[a] if me.up[a]!=-1 else a
    return len(me.down[ua])+1
  
u = Union(N)

cost = 0
for a,b,c in edge:
  ua = u.up[a] if u.up[a]!=-1 else a
  ub = u.up[b] if u.up[b]!=-1 else b
  if ( ua != ub ):
    u.union(ua,ub)
    cost += c
print ( cost )

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

def MST(n, E):
    def par(m):
        if UF[m] == m:
            return m
        ret = par(UF[m])
        UF[m] = ret
        return ret
    
    UF = [i for i in range(n)]
    E = sorted(E, key=lambda x: x[2])
    ans = 0
    for i, j, d in E:
        if par(i) != par(j):
            ans += d
            UF[par(i)] = par(j)
    return ans

N = int(input())

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

F = []
Y = sorted(X, key = lambda x: x[1])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][1]-Y[i][1])))

Y = sorted(X, key = lambda x: x[2])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][2]-Y[i][2])))

print(MST(N, F))

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

def MST(n, E):
    def par(m):
        if UF[m] == m:
            return m
        ret = par(UF[m])
        UF[m] = ret
        return ret
    
    UF = [i for i in range(n)]
    E = sorted(E, key=lambda x: x[2])
    ans = 0
    for i, j, d in E:
        if par(i) != par(j):
            ans += d
            UF[par(i)] = par(j)
    return ans

N = int(input())

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

F = []
Y = sorted(X, key = lambda x: x[1])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][1]-Y[i][1])))

Y = sorted(X, key = lambda x: x[2])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][2]-Y[i][2])))

print(MST(N, F))

Solution (Python):
import sys
sys.setrecursionlimit(100000)

def unite(i, j):
    j = get_par(j)
    par[j] = get_par(i)
    return

def get_par(p):
    if par[p] is None:
        return p
    par[p] = get_par(par[p])
    return par[p]

N = int(input())
points = []
edges = []
for i in range(N):
    x,y = map(int, input().split())
    points.append([x,y,i])
points.sort()
for i in range(N-1):
    edges.append((abs(points[i][0] - points[i+1][0]), points[i][2], points[i+1][2]))
points.sort(key=lambda x:x[1])
for i in range(N-1):
    edges.append((abs(points[i][1] - points[i+1][1]), points[i][2], points[i+1][2]))
edges.sort(key=lambda x:x[0], reverse=True)

par = [None] * N
cost = 0
count = 0
points.sort()
while count < N - 1:
    c, i, j = edges.pop()
    if get_par(i) == get_par(j):
        continue
    unite(i, j)
    cost += c
    count += 1
print(cost)

Solution (Python):
from operator import itemgetter


class UnionFindTree():
    def __init__(self, N):
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def __root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.__root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.__root(a)
        r2 = self.__root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.__root(a) == self.__root(b)

    def size(self, a):
        return self.__size[self.__root(a)]

    def groups(self):
        groups = {}
        for k in self.__parent_of.keys():
            r = self.__root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N = int(input())
    X = [None] * N
    Y = [None] * N
    for i in range(N):
        x, y = map(int, input().split())
        X[i] = (x, i)
        Y[i] = (y, i)
    X.sort(key=itemgetter(0))
    Y.sort(key=itemgetter(0))
    adj = [None] * (2*N - 2)
    for i in range(N-1):
        adj[2*i] = (X[i+1][0] - X[i][0], X[i][1], X[i+1][1])
        adj[2*i+1] = (Y[i+1][0] - Y[i][0], Y[i][1], Y[i+1][1])
    adj.sort(key=itemgetter(0))
    uft = UnionFindTree(N)
    ans = 0
    for pair in adj:
        cost, a, b = pair
        if not uft.is_same(a, b):
            uft.unite(a, b)
            ans += cost
        if uft.size(a) == N:
            break
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from heapq import*
from collections import*

input=sys.stdin.readline


p=defaultdict(lambda: -1)
class UNION_FIND(object):
    def __init__(self,n):
        
        self.parent=defaultdict(lambda: -1)

    def root(self,x):
        if type(self.parent[x])!=tuple:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])
            return self.parent[x]
 
    def size(self,x):
        return -self.parent[self.root(x)]
    def union(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]
        self.parent[y]=x
        return True
def compute_mst_kruskal(max_v, edges, flip):
    edges.sort(key=lambda x: x[2],reverse=flip)
    
    uf = UNION_FIND(max_v)
    mst = []
    for (a,b,c) in edges:
        if uf.root(a)!= uf.root(b):
            uf.union(a,b)
            mst.append(c)
    return mst


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

x=sorted(points,key=lambda x:x[0])
y=sorted(points,key=lambda x:x[1])



edges = []
for i in range(1,n):
    (a,b),(c,d)=x[i-1],x[i]
    (e,f),(g,h)=y[i-1],y[i]
    heappush(edges,((a,b),(c,d),abs(a-c)))
    heappush(edges,((e,f),(g,h),abs(f-h)))

mst = compute_mst_kruskal(n, edges , 0) 
print(sum(mst))

Solution (Python):

import functools
import sys
from heapq import*
from collections import*

input=sys.stdin.readline


p=defaultdict(lambda: -1)
@functools.lru_cache(maxsize=None)
class UNION_FIND(object):
    def __init__(self,n):
        
        self.parent=defaultdict(lambda: -1)

    def root(self,x):
        if type(self.parent[x])!=tuple:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])
            return self.parent[x]
 
    def size(self,x):
        return -self.parent[self.root(x)]
    def union(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]
        self.parent[y]=x
        return True
def compute_mst_kruskal(max_v, edges, flip):
    edges.sort(key=lambda x: x[2],reverse=flip)
    
    uf = UNION_FIND(max_v)
    mst = []
    for (a,b,c) in edges:
        if uf.root(a)!= uf.root(b):
            uf.union(a,b)
            mst.append(c)
    return mst


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

x=sorted(points,key=lambda x:x[0])
y=sorted(points,key=lambda x:x[1])



edges = []
for i in range(1,n):
    (a,b),(c,d)=x[i-1],x[i]
    (e,f),(g,h)=y[i-1],y[i]
    heappush(edges,((a,b),(c,d),abs(a-c)))
    heappush(edges,((e,f),(g,h),abs(f-h)))

mst = compute_mst_kruskal(n, edges , 0) 
print(sum(mst))

Solution (Python):
import sys
sys.setrecursionlimit(100000)
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
xy.sort()
path = []

def get_par(n):
    if par[n] is None:return n
    par[n] = get_par(par[n])
    return par[n]

def same(i,j):
    return get_par(i) == get_par(j)

def unite(i,j):
    j = get_par(j)
    par[j] = get_par(i)
    return

for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    path.append((abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    path.append((abs(y-y2),i,j))
path.sort(key = lambda x:x[0],reverse=True)
par = [None]*N
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = path.pop()
    if same(i,j):continue
    unite(i,j)
    ans += c
    cnt += 1
print(ans)

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

xy.sort(key=lambda x:x[1])
edge  = []
for i in range(n-1):
    i1,x1,y1 = xy[i]
    i2,x2,y2 = xy[i+1]
    edge.append((x2-x1,i1,i2))

xy.sort(key=lambda x:x[2])
for i in range(n-1):
    i1,x1,y1 = xy[i]
    i2,x2,y2 = xy[i+1]
    edge.append((y2-y1,i1,i2))
class UnionFind():
    def __init__(self, N):
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [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:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def size(self, x):
        x = self.find(x)
        return self.counter[x]

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


uf = UnionFind(n)
edge.sort()
ans = 0
edge_cnt = 0
i = 0
while edge_cnt < n-1:
    cost,i1,i2 = edge[i]
    if not uf.same(i1,i2):
        ans += cost
        uf.unite(i1,i2)
        edge_cnt += 1
    i += 1
print(ans)

Solution (Python):
class Kruskal_UnionFind():
    def __init__(self, N):
        self.edges = []
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

    def add(self, u, v, d):
        """
        :param u: 始点
        :param v: 終点
        :param d: コスト
        """
        self.edges.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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def size(self, x):
        x = self.find(x)
        return self.counter[x]

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

    def Kruskal(self):
        """
        :return: 最小全域木のコストの和
        """
        edges = sorted(self.edges, key=lambda x: x[2])  
        res = 0
        for e in edges:
            if not self.same(e[0], e[1]):
                self.unite(e[0], e[1])
                res += e[2]
        return res


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

graph = Kruskal_UnionFind(N)
XY = sorted(XY, key=lambda x: x[1])
X_costs = [[XY[i-1][0], XY[i][0], abs(XY[i-1][1] - XY[i][1])] for i in range(1, N)]
XY = sorted(XY, key=lambda x: x[2])
Y_costs = [[XY[i-1][0], XY[i][0], abs(XY[i-1][2] - XY[i][2])] for i in range(1, N)]

for i in range(N-1):
    x0, x1, d = X_costs[i]
    graph.add(x0, x1, d)
    y0, y1, d = Y_costs[i]
    graph.add(y0, y1, d)

print(graph.Kruskal())

Solution (Python):
class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.size_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.size_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        parent = self.root()
        return parent.group_id_

    def size(self):
        parent = self.root()
        return parent.size_

    def unite(self, unite_node):
        parent = self.root()
        unite_parent = unite_node.root()

        if parent.group_id_ != unite_parent.group_id_:
            if parent.size() > unite_parent.size():
                unite_parent.parent_ = parent
                parent.size_ = parent.size_ + unite_parent.size_
            else:
                parent.parent_ = unite_parent
                unite_parent.size_ = parent.size_ + unite_parent.size_
    def is_group(self,other):
        return self.root()==other.root()

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

X = sorted([[i, xy[0]] for i, xy in P], key=lambda x: x[1])
Y = sorted([[i, xy[1]] for i, xy in P], key=lambda y: y[1])

Xe = [[X[i][0], X[i+1][0], abs(X[i][1]-X[i+1][1])] for i in range(N-1)]
Ye = [[Y[i][0], Y[i+1][0], abs(Y[i][1]-Y[i+1][1])] for i in range(N-1)]
E = sorted(Xe + Ye, key=lambda e: e[2])

U=[UnionFindNode(i) for i in range(N)]
i=0
ans=0
count=1
while(count<N):
    v1,v2,cost=E[i]
    if not U[v1].is_group(U[v2]):
        U[v1].unite(U[v2])
        ans+=cost
        count+=1
    i+=1
print(ans)