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

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




N = I()
data = []
edges = []
for i in range(N):
  x,y = IL()
  data.append([i,x,y])
  
data = sorted(data,key = lambda x:x[1])
for i in range(N-1):
  f = data[i][0]
  t = data[i+1][0]
  c = data[i+1][1]-data[i][1]
  edges.append([f,t,c])
  
data = sorted(data,key = lambda x:x[2])
for i in range(N-1):
  f = data[i][0]
  t = data[i+1][0]
  c = data[i+1][2]-data[i][2]
  edges.append([f,t,c])

edges = sorted(edges,key = lambda x:x[2])

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())
      
U = UnionFind(N)
ans = 0
for f,t,c in edges:
  if not U.same(f,t):
    U.union(f,t)
    ans += c
    
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline
import math
from heapq import heappush, heappop, heapify

def solve(n, nodes):
  xsort_nodes = sorted(nodes, key=lambda n: n[1])
  ysort_nodes = sorted(nodes, key=lambda n: n[2])
  edges = [[] for _ in range(n)]
  for i in range(n-1):
    prev_node = xsort_nodes[i]
    post_node = xsort_nodes[i+1]
    edges[prev_node[0]].append((abs(prev_node[1]-post_node[1]), post_node[0]))
  for i in range(n-1):
    prev_node = ysort_nodes[i]
    post_node = ysort_nodes[i+1]
    edges[prev_node[0]].append((abs(prev_node[2]-post_node[2]), post_node[0]))
  for i in range(1, n):
    prev_node = xsort_nodes[i-1]
    post_node = xsort_nodes[i]
    edges[post_node[0]].append((abs(prev_node[1]-post_node[1]), prev_node[0]))
  for i in range(1, n):
    prev_node = ysort_nodes[i-1]
    post_node = ysort_nodes[i]
    edges[post_node[0]].append((abs(prev_node[2]-post_node[2]), prev_node[0]))
  tree = [0]*n
  tree[0] = 1
  distance = 0
  current_edges = [*edges[0]]
  heapify(current_edges)
  while(len(current_edges)):
    d, x = heappop(current_edges)
    if tree[x]:
      continue
    distance += d
    tree[x] = 1
    for edge in edges[x]:
      heappush(current_edges, edge)
  return distance  

def main():
  n = int(input())
  nodes = []
  for i in range(n):
    x, y = map(int, input().split(' '))
    nodes.append((i, x, y))
  ans = solve(n, nodes)
  print(ans)
  

if __name__=='__main__':
  main()

Solution (Python):
import heapq

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

x=sorted([(i,pts[i][0]) for i in range(n)],key=lambda x:x[1])
y=sorted([(i,pts[i][1]) for i in range(n)],key=lambda x:x[1])

invx=[0]*n
invy=[0]*n

for i in range(n):
    invx[x[i][0]]=i
    invy[y[i][0]]=i

q=[(0,0)]

visit=[0]*n
ans=0

while q:
    cnt,i=heapq.heappop(q)

    if visit[i]==1:
        continue

    visit[i]=1
    ans+=cnt

    xi=invx[i]
    yi=invy[i]

    for delta in [-1,1]:
        nx=xi+delta
        ny=yi+delta
        if 0<=nx<n and visit[x[nx][0]]==0:
            heapq.heappush(q,(abs(x[nx][1]-x[xi][1]),x[nx][0]))
        if 0<=ny<n and visit[y[ny][0]]==0:
            heapq.heappush(q,(abs(y[ny][1]-y[yi][1]),y[ny][0]))

print(ans)

Solution (Python):
import heapq

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

x=sorted([(i,pts[i][0]) for i in range(n)],key=lambda x:x[1])
y=sorted([(i,pts[i][1]) for i in range(n)],key=lambda x:x[1])

invx=[0]*n
invy=[0]*n

for i in range(n):
    cx,_=x[i]
    invx[cx]=i
    cy,_=y[i]
    invy[cy]=i

xi=invx[0]
yi=invy[0]

q=[(0,0)]


visit=[0]*n
ans=0

while q:
    cnt,i=heapq.heappop(q)

    if visit[i]==1:
        continue

    visit[i]=1
    ans+=cnt

    xi=invx[i]
    yi=invy[i]

    if xi>0 and visit[x[xi-1][0]]==0:
        heapq.heappush(q,(x[xi][1]-x[xi-1][1],x[xi-1][0]))
    if xi<n-1 and visit[x[xi+1][0]]==0:
        heapq.heappush(q,(x[xi+1][1]-x[xi][1],x[xi+1][0]))

    if yi>0 and visit[y[yi-1][0]]==0:
        heapq.heappush(q,(y[yi][1]-y[yi-1][1],y[yi-1][0]))
    if yi<n-1 and visit[y[yi+1][0]]==0:
        heapq.heappush(q,(y[yi+1][1]-y[yi][1],y[yi+1][0]))
    
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())
uf = UnionFind(N)
XY = [list(map(int,input().split()))+[i] for i in range(N)]

X = sorted(XY, key=lambda i:i[0])
Y = sorted(XY, key=lambda i:i[1])

side = [[] for _ in range(len(X)+len(Y)-2)]
j = 0
for i in range(N-1):
  side[j] += [X[i+1][0]-X[i][0],X[i][2],X[i+1][2]]
  side[j+1] += [Y[i+1][1]-Y[i][1],Y[i][2],Y[i+1][2]]
  j += 2

ans = 0
side.sort()

for i,j,k in side:
  if uf.same(j,k):
    continue
  uf.union(j,k)
  ans += i

print(ans)

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

  
X=sorted(town,key=lambda x:x[0])

Y=sorted(town,key=lambda x:x[1])
es=[]
for i in range(1,n):
  es.append((min(abs(X[i][0]-X[i-1][0]),abs(X[i][1]-X[i-1][1])),X[i][2],X[i-1][2]))
  
  es.append((min(abs(Y[i][0]-Y[i-1][0]),abs(Y[i][1]-Y[i-1][1])),Y[i][2],Y[i-1][2]))
  
es.sort(key=lambda x:x[0])




par=[i for i in range(n)]
deep=[1]*n
size=[1]*n


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


def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if deep[x]<deep[y]:
    par[x]=y
    size[y]+=size[x]
  else:
    par[y]=x
    size[x]+=size[y]
    if deep[x]==deep[y]:
      deep[x]+=1


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


def group_count(x):
  return size[find(x)]
  



def kruskal(n,es):
  ans=0
  for to in es:
    if not same(to[1],to[2]):
      ans+=to[0]
      unite(to[1],to[2])
  return ans

      
  
print(kruskal(n,es))

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

  
X=sorted(town,key=lambda x:x[0])

Y=sorted(town,key=lambda x:x[1])
es=[]
for i in range(1,n):
  es.append((min(abs(X[i][0]-X[i-1][0]),abs(X[i][1]-X[i-1][1])),X[i][2],X[i-1][2]))
  es.append((min(abs(X[i][0]-X[i-1][0]),abs(X[i][1]-X[i-1][1])),X[i-1][2],X[i][2]))
  es.append((min(abs(Y[i][0]-Y[i-1][0]),abs(Y[i][1]-Y[i-1][1])),Y[i][2],Y[i-1][2]))
  es.append((min(abs(Y[i][0]-Y[i-1][0]),abs(Y[i][1]-Y[i-1][1])),Y[i-1][2],Y[i][2]))
es.sort(key=lambda x:x[0])




par=[i for i in range(n)]
deep=[1]*n
size=[1]*n


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


def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if deep[x]<deep[y]:
    par[x]=y
    size[y]+=size[x]
  else:
    par[y]=x
    size[x]+=size[y]
    if deep[x]==deep[y]:
      deep[x]+=1


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


def group_count(x):
  return size[find(x)]
  



def kruskal(n,es):
  ans=0
  for to in es:
    if not same(to[1],to[2]):
      ans+=to[0]
      unite(to[1],to[2])
  return ans

      
  
print(kruskal(n,es))

Solution (Python):
from collections import defaultdict
import heapq

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

    def getParent(self):
        return [self.find(i) for i in range(N)]

    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 unite(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if (root_x == root_y):
            return
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x

        elif self.rank[root_y] > self.rank[root_x]:
            self.parent[root_x] = root_y

        else:
            self.parent[root_x] = root_y
            self.rank[root_y] += 1

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

    def memsInGroup(self, x):
        """
        O(N)かかります
        """
        root = self.find(x)
        return [i for i in range(N) if root == self.find(i)]

    def sizeOfGroup(self, x):
        return len(self.memsInGroup(x))

class Edge:

    def __init__(self, u, v, cost):
        self.u = u
        self.v = v
        self.cost = cost

N = int(input())
vertex = {}
for i in range(N):
    x, y = map(int, input().split())
    vertex[i] = (x, y)

sortX = sorted(vertex.items(), key=lambda x:x[1][0])
sortY = sorted(vertex.items(), key=lambda x:x[1][1])

edges = []

for i in range(N-1):
    v1 = sortX[i]
    v2 = sortX[i+1]
    edges.append(Edge(v1[0]-1, v2[0]-1, abs(v1[1][0] - v2[1][0])))

for i in range(N-1):
    v1 = sortY[i]
    v2 = sortY[i+1]
    edges.append( Edge(v1[0]-1, v2[0]-1, abs(v1[1][1] - v2[1][1]) ) )

edges.sort(key = lambda x: x.cost)
uf = UnionFind(N)

res = 0
for e in edges:
    if not uf.isSame(e.u, e.v):
        uf.unite(e.u, e.v)
        res += e.cost

print(res)

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())
XYi = []
for i in range(N):
    tmp = list(map(int,input().split()))
    XYi.append(tmp+[i])

edges = []
E = 0

XYi.sort(key=lambda x:x[0])
for i in range(N-1):
    A,B,ind1 = XYi[i]
    C,D,ind2 = XYi[i+1]
    edges.append((min(abs(A-C),abs(B-D)), ind1, ind2))
    E+=1

XYi.sort(key=lambda x:x[1])
for i in range(N-1):
    A,B,ind1 = XYi[i]
    C,D,ind2 = XYi[i+1]
    edges.append((min(abs(A-C),abs(B-D)), ind1, ind2))
    E+=1

edges.sort()
def kruskal(n, edges):
    U = UnionFind(n)
    res = 0
    for e in edges:
        w, s, t = e
        if not U.same(s, t):
            res+=w
            U.union(s, t)
    return res
print(kruskal(N, edges))

Solution (Python):
def main():
    n = int(input())
    x, y = [], []
    for i in range(n):
        xi, yi = map(int, input().split())
        x.append((xi, i))
        y.append((yi, i))

    x.sort()
    y.sort()

    
    x_ind = [0] * n
    y_ind = [0] * n
    for i in range(n):
        x_ind[x[i][1]] = i
        y_ind[y[i][1]] = i

    from heapq import heapify, heappush, heappop

    ans = 0
    seen = [True] * n
    heap = [(0, 0)]
    heapify(heap)
    while len(heap) > 0:
        cost, city = heappop(heap)

        if seen[city]:
            ans += cost
            seen[city] = False

            xi = x_ind[city]
            if xi > 0 and seen[x[xi-1][1]]:
                heappush(heap, (x[xi][0] - x[xi-1][0], x[xi-1][1]))
            if xi < n-1 and seen[x[xi+1][1]]:
                heappush(heap, (x[xi+1][0] - x[xi][0], x[xi+1][1]))
            yi = y_ind[city]
            if yi > 0 and seen[y[yi-1][1]]:
                heappush(heap, (y[yi][0] - y[yi-1][0], y[yi-1][1]))
            if yi < n-1 and seen[y[yi+1][1]]:
                heappush(heap, (y[yi+1][0] - y[yi][0], y[yi+1][1]))
    
    print(ans)

main()

Solution (Python):
N=int(input())
A=[]
for i in range(N):
  x,y=map(int,input().split())
  A.append((x,y,i))
A=sorted(A)
B=sorted(A,reverse=False, key=lambda x: x[1]) 

E=[[]for i in range(N)]
for i in range(N-1):
  x1,x2=A[i][2],A[i+1][2]
  y1,y2=B[i][2],B[i+1][2]
  E[x1].append((x2,A[i+1][0]-A[i][0]))
  E[x2].append((x1,A[i+1][0]-A[i][0]))
  E[y1].append((y2,B[i+1][1]-B[i][1]))
  E[y2].append((y1,B[i+1][1]-B[i][1]))
G=E



from heapq import heappush, heappop, heapify
used = [0]*N
que = [(c, w) for w, c in G[0]]
used[0] = 1
heapify(que)

ans=0
while que:
    cv,v=heappop(que)
    if used[v]:
        continue
    used[v]=1
    ans+=cv
    for w,c in G[v]:
        if used[w]:
            continue
        heappush(que,(c,w))
print(ans)

Solution (Python):
N=int(input())
A=[]
for i in range(N):
  x,y=map(int,input().split())
  A.append((x,y,i))
A=sorted(A)
B=sorted(A,reverse=False, key=lambda x: x[1]) 

E=[]
for i in range(N-1):
  E.append(((A[i+1][0]-A[i][0]),A[i][2],A[i+1][2]))
  E.append(((B[i+1][1]-B[i][1]),B[i][2],B[i+1][2]))
edge=E

def kruskal():
    cost=0
    edge.sort()
    for c,u,v in edge:
        if same(u,v):
            continue
        union(u,v)
        cost+=c
    return cost

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

def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x
    return True

def same(x, y):
    return find(x) == find(y)
par=[-1]*N
print(kruskal())

Solution (Python):
N=int(input())
A=[]
for i in range(N):
  x,y=map(int,input().split())
  A.append((x,y,i))
A=sorted(A)
B=sorted(A,reverse=False, key=lambda x: x[1]) 

E=[]
for i in range(N-1):
  E.append(((A[i+1][0]-A[i][0]),A[i][2],A[i+1][2]))
  E.append(((B[i+1][1]-B[i][1]),B[i][2],B[i+1][2]))
edge=E

def kruskal():
    cost=0
    edge.sort()
    for c,u,v in edge:
        if same(u,v):
            continue
        union(u,v)
        cost+=c
    return cost

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

def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x
    return True

def same(x, y):
    return find(x) == find(y)
par=[-1]*N
print(kruskal())

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
XYI = [tuple(map(int,input().split() + [i])) for i in range(N)]
sx = sorted(XYI, key=lambda x:x[0])
sy = sorted(XYI, key=lambda x:x[1])

es = []
for (x0,_,i0),(x1,_,i1) in zip(sx,sx[1:]):
    es.append((x1-x0, i0, i1))
for (_,y0,i0),(_,y1,i1) in zip(sy,sy[1:]):
    es.append((y1-y0, i0, i1))
es.sort(key=lambda x:x[0])

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * 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._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]
uf = UnionFind(N)

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

Solution (Python):
N = int(input())
X = []
Y = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((x, y, i))
    Y.append((y, x, i))
X.sort()
Y.sort()
Edges = list([] for _ in range(N))
for k in range(N-1):
    xk, yk, ik = X[k]
    xk_, yk_, ik_ = X[k+1]
    Edges[ik].append((ik_, min(abs(xk-xk_), abs(yk-yk_))))
    Edges[ik_].append((ik, min(abs(xk-xk_), abs(yk-yk_))))
    yk, xk, ik = Y[k]
    yk_, xk_, ik_ = Y[k+1]
    Edges[ik].append((ik_, min(abs(xk-xk_), abs(yk-yk_))))
    Edges[ik_].append((ik, min(abs(xk-xk_), abs(yk-yk_))))
    
import heapq
def prim(Edges, V):
    mst = []
    included = [False]*V
    heap = []
    included[0] = True
    for v, d in Edges[0]:
        heapq.heappush(heap, (d, 0, v)) 
    while heap:
        d, pre_v, cur_v = heapq.heappop(heap)
        if included[cur_v]:
            continue
        included[cur_v] = True
        mst.append((pre_v, cur_v, d))
        for next_v, dist in Edges[cur_v]:
            if not included[next_v]:
                heapq.heappush(heap, (dist, cur_v, next_v))
    return mst

mst = prim(Edges, N)
ans = 0
for v1, v2, d in mst:
    ans += d
    
print(ans)

Solution (Python):
N = int(input())
X = []
Y = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((x, y, i))
    Y.append((y, x, i))
X.sort()
Y.sort()
Edges = list([] for _ in range(N))
for k in range(N-1):
    xk, yk, ik = X[k]
    xk_, yk_, ik_ = X[k+1]
    Edges[ik].append((ik_, min(abs(xk-xk_), abs(yk-yk_))))
    Edges[ik_].append((ik, min(abs(xk-xk_), abs(yk-yk_))))
    yk, xk, ik = Y[k]
    yk_, xk_, ik_ = Y[k+1]
    Edges[ik].append((ik_, min(abs(xk-xk_), abs(yk-yk_))))
    Edges[ik_].append((ik, min(abs(xk-xk_), abs(yk-yk_))))
    
import heapq
def prim(Edges, V):
    mst = []
    included = [False]*V
    heap = []
    included[0] = True
    for v, d in Edges[0]:
        heapq.heappush(heap, (d, 0, v)) 
    while heap:
        d, pre_v, cur_v = heapq.heappop(heap)
        if included[cur_v]:
            continue
        included[cur_v] = True
        mst.append((pre_v, cur_v, d))
        for next_v, dist in Edges[cur_v]:
            if not included[next_v]:
                heapq.heappush(heap, (dist, cur_v, next_v))
    return mst

mst = prim(Edges, N)
ans = 0
for v1, v2, d in mst:
    ans += d
    
print(ans)

Solution (Python):

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
                
    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]


N=int(input())
towns=[]
for i in range(N):
    x,y=map(int,input().split())
    towns.append((x,y,i))
    
path=[]
A=sorted(towns,key=lambda x:x[0])
for i in range(N-1):
    path.append((A[i][2],A[i+1][2],min(abs(A[i][0]-A[i+1][0]),abs(A[i][1]-A[i+1][1]))))
A=sorted(towns,key=lambda x:x[1])
for i in range(N-1):
    path.append((A[i][2],A[i+1][2],min(abs(A[i][0]-A[i+1][0]),abs(A[i][1]-A[i+1][1]))))

path.sort(key=lambda x:x[2], reverse=True)
uf=UnionFind(N)
res=0
path_num=0
while 1:
    i,j,c=path.pop()
    if not uf.is_same_group(i,j):
        uf.unite(i,j)
        path_num+=1
        res+=c
    if path_num==N-1:
        break
print(res)

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

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.parent[x] = y

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

N = int(input())
X = []
Y = []
for i in range(N):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    X.append((x, y, i))
    Y.append((y, x, i))
X.sort()
Y.sort()
G = []
for i in range(1, N):
    d = abs(X[i][0]-X[i-1][0])
    a, b = X[i][2], X[i-1][2]
    G.append((d, a, b))
    d = abs(Y[i][0]-Y[i-1][0])
    a, b = Y[i][2], Y[i-1][2]
    G.append((d, a, b))
G.sort()
un = UnionFind(N)
ans = 0
for d, a, b in G:
    if not un.same(a, b):
        un.unite(a, b)
        ans += d
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0]*size
    def find(self, x):
        if self.parent[x] == x:
            return x
        
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        
        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(self, x, y):
        return self.find(x) == self.find(y)

if __name__ == "__main__":
    N = int(input())
    vs = []
    for i in range(N):
        x,y = map(int,input().split())
        vs.append((x,y,i))
    vs.sort()
    edges = []
    for k in range(1, N):
        x,y,i = vs[k]
        a,b,j = vs[k-1]
        edges.append((i, j, min(abs(x-a),abs(y-b))))
    vs.sort(key=lambda x:x[1])
    for k in range(1, N):
        x,y,i = vs[k]
        a,b,j = vs[k-1]
        edges.append((i, j, min(abs(x-a),abs(y-b))))
    uf = UnionFind(N)
    edges.sort(key=lambda x:x[2])
    ans = 0
    for i,j,w in edges:
        if not uf.same(i,j):
            uf.unite(i,j)
            ans += w
    print(ans)

Solution (Python):
class Union():
    def __init__(self, n):
        self.para = [-1] * n
    
    def find(self, n):
        if self.para[n] < 0:
            return n
        
        else:
            self.para[n] = self.find(self.para[n])
            return self.para[n]
    
    def union(self, n, m):
        n = self.find(n)
        m = self.find(m)
        if n == m:
            return False
        else:
            if self.para[n] > self.para[m]:
                n, m = m, n
            
            self.para[n] += self.para[m]
            self.para[m] = n
    
    def same(self, n, m):
        return self.find(n) == self.find(m)

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()
ALL = []
for i in range(len(X)-1):
    ALL.append((X[i+1][0]-X[i][0], X[i][1], X[i+1][1]))
    ALL.append((Y[i+1][0]-Y[i][0], Y[i][1], Y[i+1][1]))
ALL.sort()
ut = Union(N)
cnt = 0
for a in ALL:
    n = a[1]
    m = a[2]
    if not ut.same(n,m):
        ut.union(n,m)
        cnt += a[0]
print(cnt)

Solution (Python):
n=int(input())
xy=[]
for i in range(n):
  xy.append(list(map(int,input().split()))+[i])
  
x_sort=sorted(xy,key=lambda x:x[0])
y_sort=sorted(xy,key=lambda x:x[1])
edge=[]
for i in range(1,n):
  edge.append([min(abs(x_sort[i][1]-x_sort[i-1][1]),abs(x_sort[i][0]-x_sort[i-1][0])),x_sort[i][2],x_sort[i-1][2]])
  edge.append([min(abs(y_sort[i][1]-y_sort[i-1][1]),abs(y_sort[i][0]-y_sort[i-1][0])),y_sort[i][2],y_sort[i-1][2]])
edge.sort(key=lambda x:x[0])



par=[i for i in range(n)]
deep=[1 for i in range(n)]
size=[1 for i in range(n)]
def find(x):
  if par[x]==x:
    return x
  else:
    return find(par[x])

def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if deep[x]<deep[y]:
    par[x]=y
    size[y]+=size[x]
  else:
    par[y]=x
    size[x]+=size[y]
    if deep[x]==deep[y]:
      deep[x]+=1

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



def kruskal(n,edge):
  res=0
  
  for w,s,t in edge:
    if not same(s,t):
      unite(s,t)
      res+=w
  return res




print(kruskal(n,edge))

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = list(range(n))
        self.rank = [1]*n
        self.size = [1]*n
        
    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 union(self, x, y):
        px = self.find(x)
        py = self.find(y)

        if px == py:
            return
        else:
            if self.rank[px] < self.rank[py]:
                self.parents[px] = py
                self.size[py] += self.size[px]
            else:
                self.parents[py] = px
                self.size[px] += self.size[py]
                
                if self.rank[px] == self.rank[py]:
                    self.rank[px] += 1

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

town = sorted(town, key=lambda x: x[1])
for i in range(1,N):
    px,nx = town[i-1][1], town[i][1]
    root.append([town[i-1][0], town[i][0], nx-px])

town = sorted(town, key=lambda x: x[2])
for i in range(1,N):
    py,ny = town[i-1][2], town[i][2]
    root.append([town[i-1][0], town[i][0], ny-py])

root = sorted(root, key=lambda x: x[2])
ufpc = UnionFindPathCompression(N)
ans = 0
for pp,np,cost in root:
    if ufpc.find(pp) != ufpc.find(np):
        ufpc.union(pp,np)
        ans += cost
        
print(ans)