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
fin = sys.stdin.readline
from heapq import heappop, heappush


class UnionFind(object):
    def __init__(self, N):
        self.__root = list(range(N))
    

    def root(self, x):
        if self.__root[x] == x:
            return x
        else:
            
            self.__root[x] = self.root(self.__root[x])
            return self.__root[x]

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


    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if (x == y):
            return
        self.__root[y] = x
        return






def prim(adj, w):
    num_vertices = len(adj)
    
    min_cost = [float('inf')] * num_vertices
    min_cost[0] = 0
    used = [False] * num_vertices
    priority_queue = [(0, 0)]
    total_cost = 0

    while priority_queue:
        cost, vertex = heappop(priority_queue)
        if cost > min_cost[vertex] or used[vertex]:
            continue
        used[vertex] = True
        total_cost += cost

        for neighbor in adj[vertex]:
            cost_v_to_n = w[(vertex, neighbor)]
            if min_cost[neighbor] > cost_v_to_n:
                min_cost[neighbor] = cost_v_to_n
                heappush(priority_queue, (cost_v_to_n, neighbor))

    return total_cost





def kruskal(edges_with_cost, num_vertices):
    
    edges_with_cost.sort(key=lambda x: x[-1])
    uf = UnionFind(num_vertices)
    total_cost = 0
    for source, target, cost in edges_with_cost:
        if not uf.same(source, target):
            uf.unite(source, target)
            total_cost += cost
    
    return total_cost


N = int(fin())
coords = [[int(elem) for elem in fin().split()] + [i] for i in range(N)]





















adj = [set() for _ in range(N)]
w = {}

coords.sort(key=lambda x: x[0])
for i, (x, _, vertex) in enumerate(coords[:-1]):
    next_x, _, next_vertex = coords[i + 1]
    adj[vertex].add(next_vertex)
    adj[next_vertex].add(vertex)
    weight = next_x - x
    if (vertex, next_vertex) not in w or w[(vertex, next_vertex)] > weight:
        w[(vertex, next_vertex)] = weight
    if (next_vertex, vertex) not in w or w[(next_vertex, vertex)] > weight:
        w[(next_vertex, vertex)] = weight


coords.sort(key=lambda x: x[1])
for i, (_, y, vertex) in enumerate(coords[:-1]):
    _, next_y, next_vertex = coords[i + 1]
    adj[vertex].add(next_vertex)
    adj[next_vertex].add(vertex)
    weight = next_y - y
    if (vertex, next_vertex) not in w or w[(vertex, next_vertex)] > weight:
        w[(vertex, next_vertex)] = weight
    if (next_vertex, vertex) not in w or w[(next_vertex, vertex)] > weight:
        w[(next_vertex, vertex)] = weight

print(prim(adj, w))

Solution (Python):
import sys
fin = sys.stdin.readline
from heapq import heappop, heappush


class UnionFind(object):
    def __init__(self, N):
        self.__root = list(range(N))
    

    def root(self, x):
        if self.__root[x] == x:
            return x
        else:
            
            self.__root[x] = self.root(self.__root[x])
            return self.__root[x]

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


    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if (x == y):
            return
        self.__root[y] = x
        return






def prim(adj, w):
    num_vertices = len(adj)
    
    min_cost = [float('inf')] * num_vertices
    min_cost[0] = 0
    used = [False] * num_vertices
    priority_queue = [(0, 0)]
    total_cost = 0

    while priority_queue:
        cost, vertex = heappop(priority_queue)
        if cost > min_cost[vertex] or used[vertex]:
            continue
        used[vertex] = True
        total_cost += cost

        for neighbor in adj[vertex]:
            cost_v_to_n = w[(vertex, neighbor)]
            if min_cost[neighbor] > cost_v_to_n:
                min_cost[neighbor] = cost_v_to_n
                heappush(priority_queue, (cost_v_to_n, neighbor))

    return total_cost





def kruskal(edges_with_cost, num_vertices):
    
    edges_with_cost.sort(key=lambda x: x[-1])
    uf = UnionFind(num_vertices)
    total_cost = 0
    for source, target, cost in edges_with_cost:
        if not uf.same(source, target):
            uf.unite(source, target)
            total_cost += cost
    
    return total_cost


N = int(fin())
coords = [[int(elem) for elem in fin().split()] + [i] for i in range(N)]

edges_with_cost = []

coords.sort(key=lambda x: x[0])
for i, (x, _, vertex) in enumerate(coords[:-1]):
    next_x, _, next_vertex = coords[i + 1]
    weight = next_x - x
    edges_with_cost.append((vertex, next_vertex, weight))
    edges_with_cost.append((next_vertex, vertex, weight))



coords.sort(key=lambda x: x[1])
for i, (_, y, vertex) in enumerate(coords[:-1]):
    _, next_y, next_vertex = coords[i + 1]
    weight = next_y - y
    edges_with_cost.append((vertex, next_vertex, weight))
    edges_with_cost.append((next_vertex, vertex, weight))

print(kruskal(edges_with_cost, N))

Solution (Python):
import sys
fin = sys.stdin.readline
from heapq import heappop, heappush
from operator import itemgetter





def prim(adj, w):
    num_vertices = len(adj)
    
    min_cost = [float('inf')] * num_vertices
    min_cost[0] = 0
    used = [False] * num_vertices
    priority_queue = [(0, 0)]
    total_cost = 0

    while priority_queue:
        cost, vertex = heappop(priority_queue)
        if cost > min_cost[vertex] or used[vertex]:
            continue
        used[vertex] = True
        total_cost += cost

        for neighbor in adj[vertex]:
            cost_v_to_n = w[(vertex, neighbor)]
            if min_cost[neighbor] > cost_v_to_n:
                min_cost[neighbor] = cost_v_to_n
                heappush(priority_queue, (cost_v_to_n, neighbor))

    return total_cost


N = int(fin())
coords = [[int(elem) for elem in fin().split()] + [i] for i in range(N)]

adj = [set() for _ in range(N)]
w = {}



coords.sort(key=itemgetter(0))
for i, (x, _, vertex) in enumerate(coords[:-1]):
    next_x, _, next_vertex = coords[i + 1]
    adj[vertex].add(next_vertex)
    adj[next_vertex].add(vertex)
    weight = next_x - x
    if (vertex, next_vertex) not in w or w[(vertex, next_vertex)] > weight:
        w[(vertex, next_vertex)] = weight
    if (next_vertex, vertex) not in w or w[(next_vertex, vertex)] > weight:
        w[(next_vertex, vertex)] = weight



coords.sort(key=itemgetter(1))
for i, (_, y, vertex) in enumerate(coords[:-1]):
    _, next_y, next_vertex = coords[i + 1]
    adj[vertex].add(next_vertex)
    adj[next_vertex].add(vertex)
    weight = next_y - y
    if (vertex, next_vertex) not in w or w[(vertex, next_vertex)] > weight:
        w[(vertex, next_vertex)] = weight
    if (next_vertex, vertex) not in w or w[(next_vertex, vertex)] > weight:
        w[(next_vertex, vertex)] = weight

print(prim(adj, w))

Solution (Python):
import sys
fin = sys.stdin.readline
from heapq import heappop, heappush






def prim(adj, w):
    num_vertices = len(adj)
    
    min_cost = [float('inf')] * num_vertices
    min_cost[0] = 0
    used = [False] * num_vertices
    priority_queue = [(0, 0)]
    total_cost = 0

    while priority_queue:
        cost, vertex = heappop(priority_queue)
        if cost > min_cost[vertex] or used[vertex]:
            continue
        used[vertex] = True
        total_cost += cost

        for neighbor in adj[vertex]:
            cost_v_to_n = w[(vertex, neighbor)]
            if min_cost[neighbor] > cost_v_to_n:
                min_cost[neighbor] = cost_v_to_n
                heappush(priority_queue, (cost_v_to_n, neighbor))

    return total_cost


N = int(fin())
coords = [[int(elem) for elem in fin().split()] + [i] for i in range(N)]

adj = [set() for _ in range(N)]
w = {}


coords.sort(key=lambda x: x[0])
for i, (x, _, vertex) in enumerate(coords[:-1]):
    next_x, _, next_vertex = coords[i + 1]
    adj[vertex].add(next_vertex)
    adj[next_vertex].add(vertex)
    weight = next_x - x
    if (vertex, next_vertex) not in w or w[(vertex, next_vertex)] > weight:
        w[(vertex, next_vertex)] = weight
    if (next_vertex, vertex) not in w or w[(next_vertex, vertex)] > weight:
        w[(next_vertex, vertex)] = weight


coords.sort(key=lambda x: x[1])
for i, (_, y, vertex) in enumerate(coords[:-1]):
    _, next_y, next_vertex = coords[i + 1]
    adj[vertex].add(next_vertex)
    adj[next_vertex].add(vertex)
    weight = next_y - y
    if (vertex, next_vertex) not in w or w[(vertex, next_vertex)] > weight:
        w[(vertex, next_vertex)] = weight
    if (next_vertex, vertex) not in w or w[(next_vertex, vertex)] > weight:
        w[(next_vertex, vertex)] = weight


print(prim(adj, w))

Solution (Python):
from heapq import *
def find(A,x) -> int:
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a

def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

N = int( input())
X = [(0,0)]*N
Y = [(0,0)]*N
E = [(0,0)]*N
for i in range(N):
    x, y = map( int, input().split())
    X[i] = (x,i)
    Y[i] = (y,i)
    E[i] = (x,y)
X.sort()
Y.sort()
H = []
heapify(H)
for i in range(N-1):
    x1, j1 = X[i]
    x2, j2 = X[i+1]
    y1, k1 = Y[i]
    y2, k2 = Y[i+1]
    heappush(H,(x2-x1, j1, j2))
    heappush(H, (y2-y1, k1, k2))
ans = 0
V = [ i for i in range(N)]
while H:
    w,s,t = heappop(H)
    if find(V,s) != find(V,t):
        union(V,s,t)
        ans += w
print(ans)

Solution (Python):
from heapq import *
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a

def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

N = int( input())
X = [(0,0)]*N
Y = [(0,0)]*N
E = [(0,0)]*N
for i in range(N):
    x, y = map( int, input().split())
    X[i] = (x,i)
    Y[i] = (y,i)
    E[i] = (x,y)
X.sort()
Y.sort()
H = []
heapify(H)
for i in range(N-1):
    x1, j1 = X[i]
    x2, j2 = X[i+1]
    y1, k1 = Y[i]
    y2, k2 = Y[i+1]
    heappush(H,(x2-x1, j1, j2))
    heappush(H, (y2-y1, k1, k2))
ans = 0
V = [ i for i in range(N)]
while H:
    w,s,t = heappop(H)
    if find(V,s) != find(V,t):
        union(V,s,t)
        ans += w
print(ans)

Solution (Python):
N = int(input())
z = [tuple(map(int,input().split())) for i in range(N)]
z.sort()
y = [(z[i][1],i) for i in range(N)]
y.sort()
cost = [[] for i in range(N)]
for i in range(N-1):
    j = y[i][1]
    cost[i].append((i-1,min(abs(z[i][0]-z[i-1][0]),abs(z[i][1]-z[i-1][1]))))
    j_ = y[i-1][1]
    cost[j].append((j_,min(abs(y[i][0]-y[i-1][0]),abs(z[j][0]-z[j_][0]))))
    cost[i].append((i+1,min(abs(z[i+1][0]-z[i][0]),abs(z[i+1][1]-z[i][1]))))
    j_ = y[i+1][1]
    cost[j].append((j_,min(abs(y[i+1][0]-y[i][0]),abs(z[j_][1]-z[j][1]))))

i = N-1
j = y[i][1]
cost[i].append((i-1,min(abs(z[i][0]-z[i-1][0]),abs(z[i][1]-z[i-1][1]))))
j_ = y[i-1][1]
cost[j].append((j_,min(abs(y[i][0]-y[i-1][0]),abs(z[j][0]-z[j_][0]))))


import heapq

def prim(cost):
    V = len(cost)
    res = 0
    mincost = [float('inf')]*V
    used = [False]*V
    hq = []
    mincost[0] = 0
    heapq.heappush(hq,(0,0))
    while hq:
        weight,u = heapq.heappop(hq)
        if not used[u]:
            used[u] = True
            res += weight
            mincost[u] = weight
            for v, v_cost in cost[u]:
                if not used[v]:
                    heapq.heappush(hq,(v_cost,v))
    return res

print(prim(cost))

Solution (Python):
N = int(input())
z = [tuple(map(int,input().split())) for i in range(N)]
z.sort()
y = [(z[i][1],i) for i in range(N)]
y.sort()
cost = [[] for i in range(N)]
for i in range(N-1):
    j = y[i][1]
    cost[i].append((i-1,min(abs(z[i][0]-z[i-1][0]),abs(z[i][1]-z[i-1][1]))))
    j_ = y[i-1][1]
    cost[j].append((j_,min(abs(y[i][0]-y[i-1][0]),abs(z[j][0]-z[j_][0]))))
    cost[i].append((i+1,min(abs(z[i+1][0]-z[i][0]),abs(z[i+1][1]-z[i][1]))))
    j_ = y[i+1][1]
    cost[j].append((j_,min(abs(y[i+1][0]-y[i][0]),abs(z[j_][1]-z[j][1]))))

i = N-1
j = y[i][1]
cost[i].append((i-1,min(abs(z[i][0]-z[i-1][0]),abs(z[i][1]-z[i-1][1]))))
j_ = y[i-1][1]
cost[j].append((j_,min(abs(y[i][0]-y[i-1][0]),abs(z[j][0]-z[j_][0]))))


import heapq

def prim(cost):
    V = len(cost)
    res = 0
    mincost = [float('inf')]*V
    used = [False]*V
    hq = []
    mincost[0] = 0
    heapq.heappush(hq,(0,0))
    done = 0
    while hq:
        weight,u = heapq.heappop(hq)
        if not used[u]:
            used[u] = True
            done += 1
            res += weight
            mincost[u] = weight
            for v, v_cost in cost[u]:
                if not used[v]:
                    heapq.heappush(hq,(v_cost,v))
            if done == V:
                break
    return res

print(prim(cost))

Solution (Python):
import heapq
import sys

sys.setrecursionlimit(10**5)

def add(i,pj,T):
    if T[i]!=i:
        add(T[i],pj,T)
    T[i]=pj
    
def parent(i,T):
    if T[i]!=i:
        T[i]= parent(T[i],T)
        return T[i]
    else:
        return i

N=int(input())
town=[]
for i in range(N):
    x,y=list(map(int,input().split()))
    town.append([i,x,y])
townX=sorted(town,key=lambda x:x[1])
townY=sorted(town,key=lambda x:x[2])
road=[]
for i in range(1,N):
    heapq.heappush(road,[townX[i][1]-townX[i-1][1],townX[i-1][0],townX[i][0]])
for i in range(1,N):
    heapq.heappush(road,[townY[i][2]-townY[i-1][2],townY[i-1][0],townY[i][0]])

vi=0
ans=0
tree=[i for i in range(N)]
rank=[0 for i in range(N)]
while vi<N-1:
    d,u,v = heapq.heappop(road)
    pu=parent(u,tree)
    pv=parent(v,tree)
    ru=rank[pu]
    rv=rank[pv]
    if pu == pv:
        continue
    elif ru<rv:
        add(u,pv,tree)
    elif ru==rv:
        add(u,pv,tree)
        rank[pu]+=1
    else:
        add(v,pu,tree)
    vi+=1
    ans+=d
print(ans)

Solution (Python):

"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq
import sys
input = sys.stdin.readline

n = int(input())
a = [[] for _ in range(n)]
b = [[] for _ in range(n)]
for i in range(n): 
    xy = list(map(int, input().split()))
    a[i]=[xy[0],i]
    b[i]=[xy[1],i]

a.sort()
b.sort()




adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])


    


visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
totalcost = 0 
while h:
    cost, node = heapq.heappop(h)
    
    if visited[node] != True:        
        
        visited[node] = True
        totalcost += cost
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]]:
                continue
            heapq.heappush(h, edge)
            

print(totalcost)

Solution (Python):
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N)]

xs = []
ys = []
for i,(x,y) in enumerate(src):
    xs.append((x,i))
    ys.append((y,i))
xs.sort()
ys.sort()

es = []
for (x1,i1),(x2,i2) in zip(xs,xs[1:]):
    es.append((x2-x1, i1, i2))
for (y1,i1),(y2,i2) in zip(ys,ys[1:]):
    es.append((y2-y1, i1, i2))
es.sort()

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

ans = 0
uf = UnionFind(N)
for d,a,b in es:
    if uf.is_same(a,b): continue
    uf.unite(a,b)
    ans += d
print(ans)

Solution (Python):
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

class UnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x:int, y:int) -> bool:
        if self.isSame(x,y):
            
            return False
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
                
        return True
                
    
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)
    
    

def kruskal(edges: list, node_num: int) -> int:
    edges.sort(key=lambda x:x[0])
    
    uf = UnionFind(node_num)
    rem = node_num-1
    ans = 0
    
    for cost, prev, nex in edges:
        if uf.find(prev) != uf.find(nex):
            uf.unite(prev, nex)
            ans += cost
            rem -= 1
            
        if rem == 0:
            break
        
    return ans

n = ni()
city = []

for i in range(n):
    city.append([i] + list(li()))


edges = []

city.sort(key=lambda x:x[1])
for i in range(n-1):
    edges.append((city[i+1][1] - city[i][1], city[i][0], city[i+1][0]))

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


ans = kruskal(edges, n)

print(ans)

Solution (Python):
class UnionFind(object):
  def __init__(self,n):
    *self.par,=range(n+1)
    self.rank=[0]*(n+1)

  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 union(self,x,y):
    x=self.find(x)
    y=self.find(y)
    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

n=int(input())
x=[[0,0] for _ in range(n)]
y=[[0,0] for _ in range(n)]

for i in range(n):
  x[i][0],y[i][0]=map(int,input().split())
  x[i][1],y[i][1]=i+1,i+1

dx,dy=[],[]
x,y=sorted(x),sorted(y)
for i in range(n-1):
  dx.extend([(abs(x[i][0]-x[i+1][0]),x[i][1],x[i+1][1])])
  dy.extend([(abs(y[i][0]-y[i+1][0]),y[i][1],y[i+1][1])])

target=sorted(dx+dy)
tree=UnionFind(n)
cnt,cost,i=0,0,0

while cnt<n-1:
  c,a,b=target[i]
  if tree.find(a)!=tree.find(b):
    cost+=c
    tree.union(a,b)
    cnt+=1
  i+=1

print(cost)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        
        self.par = [i for i in range(n)]
        
        self.rank = [0] * 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 same(self, x, y):
        
        return self.find(x) == self.find(y)

    def union(self, x, y):
        
        
        x = self.find(x)
        y = self.find(y)
        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
N = int(input())
towns = [[i] + list(map(int, input().split())) for i in range(N)]
roads = []
towns.sort(key = lambda x: x[1])
for i in range(N - 1):
    num1, x1, y1 = towns[i]
    num2, x2, y2 = towns[i + 1]
    dist = min(abs(x1 - x2), abs(y1 - y2))
    roads.append([dist, num1, num2])
towns.sort(key = lambda x: x[2])
for i in range(N - 1):
    num1, x1, y1 = towns[i]
    num2, x2, y2 = towns[i + 1]
    dist = min(abs(x1 - x2), abs(y1 - y2))
    roads.append([dist, num1, num2])
roads.sort()
ans = 0
tree = UnionFind(N)
for road in roads:
    d, s, t = road
    if not tree.same(s, t):
        ans += d
        tree.union(s, t)

print(ans)

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

recx = sorted(rec, key=lambda s: s[1])
recy = sorted(rec, key=lambda s: s[2])

G = []
for i in range(1, N):
    costx = min(abs(recx[i][1] - recx[i - 1][1]), abs(recx[i][2] - recx[i - 1][2]))
    costy = min(abs(recy[i][1] - recy[i - 1][1]), abs(recy[i][2] - recy[i - 1][2]))
    G.append((recx[i][0], recx[i - 1][0], costx))
    G.append((recy[i][0], recy[i - 1][0], costy))

rank = [0] * N
par = [i for i 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
    else:
        par[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1


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


G = sorted(G, key=lambda s: s[2])
num = 0
for e in G:
    if not same(e[0], e[1]):
        unite(e[0], e[1])
        num += e[2]

print(num)

Solution (Python):
import sys
from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

readline = sys.stdin.readline

N = int(readline())
town = [None] * N
for i in range(N):
    x, y = map(int, readline().split())
    town[i] = (i, x, y)

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(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 union(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[y] = x

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


def Kruskal(edges):
    edge = []
    total = 0

    uf = UnionFind(N)
    Q = sorted(edges, reverse=True)

    while len(edge) < N - 1 and Q:
        cost, e = Q.pop()
        if uf.find(e[0]) != uf.find(e[1]):
            total += cost
            edge.append(edge)
            uf.union(*e)
    return total


edges = []
for xy in [1, 2]:
    town = sorted(town, key=itemgetter(xy))
    for i in range(N - 1):
        t1, t2 = town[i], town[i + 1]
        d = t2[xy] - t1[xy]
        edges.append((d, (t1[0], t2[0])))
print(Kruskal(edges))

Solution (Python):
import heapq

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
ixy = [(i, x, y) for i, (x, y) in enumerate(xy)]


edges = [[] for i in range(n)]
for x_or_y in [1, 2]:
    xy_sorted = sorted(ixy, key = lambda a: a[x_or_y])
    for i in range(n-1):
        i1 = xy_sorted[i][0]
        i2 = xy_sorted[i+1][0]
        cost = xy_sorted[i+1][x_or_y] - xy_sorted[i][x_or_y]
        edges[i1].append((i2, cost))
        edges[i2].append((i1, cost))


distinct = [False]*n
ans = 0
pque = []
heapq.heappush(pque, (0, 0))
while len(pque) > 0:
    
    cost, v = heapq.heappop(pque)
    if distinct[v]: continue
    
    ans += cost
    distinct[v] = True

    for v_next, cost_next in edges[v]:
        if not distinct[v_next]:
            heapq.heappush(pque, (cost_next, v_next))

print(ans)

Solution (Python):
from operator import itemgetter
from heapq import heappush,heappop
N = int(input())
table=[]
for i in range(N):
    a,b = map(int,input().split())
    table.append([a,b,i])
A = sorted(table,key=itemgetter(0))
B = sorted(table,key=itemgetter(1))

graph=[]
for k in range(N):
    graph.append((min(abs(A[k][0]-A[k-1][0]),abs( A[k][1]-A[k-1][1])),A[k][2],A[k-1][2]))
for k in range(N):
    graph.append((min(abs(B[k][0]-B[k-1][0]),abs( B[k][1]-B[k-1][1])),B[k][2],B[k-1][2]))

class Unionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)

    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 union(self,x,y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
        else:
            self.par[py]=px
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):
        return self.find(x)==self.find(y)

kei = Unionfindtree(N)
graph.sort()
dist =0
for d,i,j in graph:
    if not kei.connect(i,j):
        kei.union(i,j)
        dist +=d
print(dist)

Solution (Python):
from operator import itemgetter
from heapq import heappush,heappop
N = int(input())
table=[]
for i in range(N):
    a,b = map(int,input().split())
    table.append([a,b,i])
A = sorted(table,key=itemgetter(0))
B = sorted(table,key=itemgetter(1))

graph=[]
for k in range(N):
    graph.append((min(abs(A[k][0]-A[k-1][0]),abs( A[k][1]-A[k-1][1])),A[k][2],A[k-1][2]))
for k in range(N):
    graph.append((min(abs(B[k][0]-B[k-1][0]),abs( B[k][1]-B[k-1][1])),B[k][2],B[k-1][2]))

class Unionfindtree:
    def __init__(self,number):
        self.par = [i for i in range(number)]
        self.rank = [0]*(number)

    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 union(self,x,y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
        else:
            self.par[py]=px
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):
        return self.find(x)==self.find(y)

kei = Unionfindtree(N)
graph.sort()
dist =0
for d,i,j in graph:
    if not kei.connect(i,j):
        kei.union(i,j)
        dist +=d
print(dist)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Prim(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = list(set(V))

    used = set([])
    q = []
    heapq.heappush(q, (0, V[0]))

    ret = 0
    while q:
        c, v = heapq.heappop(q)

        if v in used:
            continue
        used.add(v)
        ret += c
        for u in g[v]:
            heapq.heappush(q, (g[v][u], u))
    return ret


@mt
def slv(N, XY):
    g = defaultdict(dict)
    V = [(i, x, y) for i, (x, y) in enumerate(XY)]
    V.sort(key=lambda x: x[1])
    for i in range(1, N):
        v = V[i][0]
        u = V[i-1][0]
        d = min(abs(XY[v][0] - XY[u][0]), abs(XY[v][1] - XY[u][1]))
        g[v][u] = d
        g[u][v] = d

    V.sort(key=lambda x: x[2])
    for i in range(1, N):
        v = V[i][0]
        u = V[i-1][0]
        d = min(abs(XY[v][0] - XY[u][0]), abs(XY[v][1] - XY[u][1]))
        g[v][u] = d
        g[u][v] = d

    return Prim(g)


def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]

    print(slv(N, XY))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Prim(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = list(set(V))

    used = set([])
    q = []
    heapq.heappush(q, (0, V[0]))

    ret = 0
    while q:
        c, v = heapq.heappop(q)

        if v in used:
            continue
        used.add(v)
        ret += c
        for u in g[v]:
            heapq.heappush(q, (g[v][u], u))
    return ret


@mt
def slv(N, XY):
    g = defaultdict(dict)
    V = [(i, x, y) for i, (x, y) in enumerate(XY)]
    V.sort(key=lambda x: x[1])
    for i in range(1, N):
        v = V[i][0]
        u = V[i-1][0]
        d = min(abs(XY[v][0] - XY[u][0]), abs(XY[v][1] - XY[u][1]))
        g[v][u] = d
        g[u][v] = d

    V.sort(key=lambda x: x[2])
    for i in range(1, N):
        v = V[i][0]
        u = V[i-1][0]
        d = min(abs(XY[v][0] - XY[u][0]), abs(XY[v][1] - XY[u][1]))
        g[v][u] = d
        g[u][v] = d

    return Prim(g)


def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]

    print(slv(N, XY))


if __name__ == '__main__':
    main()