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

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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())


def main():
    from operator import itemgetter
    import heapq

    n = int(readline())
    cities = [list(map(int, readline().split())) + [i] for i in range(n)]
    uf = UnionFind(n)

    cx = sorted(cities, key=itemgetter(0))
    cy = sorted(cities, key=itemgetter(1))

    edge = []

    for i in range(1, n):
        dx = cx[i][0] - cx[i - 1][0]
        heapq.heappush(edge, (dx, cx[i][2], cx[i - 1][2]))

    for i in range(1, n):
        dy = cy[i][1] - cy[i - 1][1]
        heapq.heappush(edge, (dy, cy[i][2], cy[i - 1][2]))

    ans = 0
    while edge:
        cost, u, v = heapq.heappop(edge)
        if not uf.same(u, v):
            uf.union(u, v)
            ans += cost

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






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

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

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

        if x == y:
            return

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

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

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

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

N = getN()
query = []
for i in range(N):
    a, b = getNM()
    query.append([a, b, i])

q_a = sorted(query, key = lambda i: i[0])
q_b = sorted(query, key = lambda i: i[1])
edges = []

a1 = q_a[0]
b1 = q_b[0]
for i in range(1, N):
    a2 = q_a[i]
    b2 = q_b[i]
    edges.append([abs(a1[0] - a2[0]), a1[2], a2[2]])
    edges.append([abs(b1[1] - b2[1]), b1[2], b2[2]])
    a1, b1 = a2, b2
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)
        if U.size(0) == N:
            break
    return res
print(kruskal(N, edges))

Solution (Python):
def find(x):
    if par[x] < 0:
        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 False
    else:
        if deep[x] > deep[y]:
            par[x] += par[y]
            par[y] = x
        elif deep[x] < deep[y]:
            par[y] += par[x]
            par[x] = y
        else:
            par[x] += par[y]
            par[y] = x
            deep[x] += 1
        return True
def same(x,y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
n = int(input())
par = [-1]*n
deep = [1]*n
p = []
edge = []
for i in range(n):
    x,y = map(int,input().split())
    p.append([x,y,i])
p.sort(key=lambda x:x[0])
for i in range(n-1):
    x_0,_,j=p[i]
    x_1,_,k=p[i+1]
    edge.append([x_1-x_0,j,k])
p.sort(key=lambda x:x[1])
for i in range(n-1):
    _,y_0,j=p[i]
    _,y_1,k=p[i+1]
    edge.append([y_1-y_0,j,k])
edge.sort()
ans = 0
for i in range(len(edge)):
    cost,u,v = edge[i]
    if not same(u,v):
        unite(u,v)
        ans+=cost
print(ans)

Solution (Python):
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x,y):
    parx = find(x)
    pary = find(y)
    if parx == pary:
        return False
    else:
        par[parx] += par[pary]
        par[pary] = x
        return True
def same(x,y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
n = int(input())
par = [-1]*n
p = []
edge = []
for i in range(n):
    x,y = map(int,input().split())
    p.append([x,y,i])
p.sort(key=lambda x:x[0])
for i in range(n-1):
    x_0,_,j=p[i]
    x_1,_,k=p[i+1]
    edge.append([x_1-x_0,j,k])
p.sort(key=lambda x:x[1])
for i in range(n-1):
    _,y_0,j=p[i]
    _,y_1,k=p[i+1]
    edge.append([y_1-y_0,j,k])
edge.sort()
ans = 0
for i in range(len(edge)):
    cost,u,v = edge[i]
    if not same(u,v):
        unite(u,v)
        ans+=cost
print(ans)

Solution (Python):
def find(x):
    if par[x] < 0:
        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 False
    else:
        par[x] += par[y]
        par[y] = x
        return True
def same(x,y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
n = int(input())
par = [-1]*n
p = []
edge = []
for i in range(n):
    x,y = map(int,input().split())
    p.append([x,y,i])
p.sort(key=lambda x:x[0])
for i in range(n-1):
    x_0,_,j=p[i]
    x_1,_,k=p[i+1]
    edge.append([x_1-x_0,j,k])
p.sort(key=lambda x:x[1])
for i in range(n-1):
    _,y_0,j=p[i]
    _,y_1,k=p[i+1]
    edge.append([y_1-y_0,j,k])
edge.sort()
ans = 0
for i in range(len(edge)):
    cost,u,v = edge[i]
    if not same(u,v):
        unite(u,v)
        ans+=cost
print(ans)

Solution (Python):
def find(x):
    if par[x] < 0:
        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 False
    else:
        par[x] += par[y]
        par[y] = x
        return True
def same(x,y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
n = int(input())
par = [-1]*n
p = []
edge = []
for i in range(n):
    x,y = map(int,input().split())
    p.append([x,y,i])
p.sort(key=lambda x:x[0])
for i in range(n-1):
    x_0,_,j=p[i]
    x_1,_,k=p[i+1]
    edge.append([x_1-x_0,j,k])
p.sort(key=lambda x:x[1])
for i in range(n-1):
    _,y_0,j=p[i]
    _,y_1,k=p[i+1]
    edge.append([y_1-y_0,j,k])
edge.sort()
ans = 0
for i in range(len(edge)):
    cost,u,v = edge[i]
    if not same(u,v):
        unite(u,v)
        ans+=cost
print(ans)

Solution (Python):
class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)


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

l.sort()
for i in range(N-1):
    x1, y1, s = l[i]
    x2, y2, t = l[i+1]
    q.append((abs(x1-x2), s, t))

l.sort(key=lambda x:x[1])
for i in range(N-1):
    x1, y1, s = l[i]
    x2, y2, t = l[i+1]
    q.append((abs(y1-y2), s, t))

uft = UnionFind(N)
ans = 0
q.sort()

for cost, s, t in q:
    if not uft.isunited(s, t):
        ans += cost
        uft.unite(s, t)

print(ans)

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


class UnionFind:
    def __init__(self, num_of_node):
        self.roots = [-1] * num_of_node
        self.groups = num_of_node

    def get_root(self, node):
        root = self.roots[node]
        if root == -1:
            return node

        else:
            root = self.get_root(root)
            self.roots[node] = root
            return root

    def is_same_group(self, node1, node2):
        return self.get_root(node1) == self.get_root(node2)

    def unite(self, node1, node2):
        self.groups -= 1
        root1, root2 = self.get_root(node1), self.get_root(node2)
        self.roots[root2] = root1


def main():
    n = int(buf.readline())
    XY = map(int, buf.read().split())
    Xs = []
    Ys = []
    for i, (x, y) in enumerate(zip(XY, XY)):
        Xs.append((x-1, i))
        Ys.append((y-1, i))

    Xs.sort()
    Ys.sort()

    edges = []
    for i in range(n-1):
        x1, node1 = Xs[i]
        x2, node2 = Xs[i+1]
        y1, node3 = Ys[i]
        y2, node4 = Ys[i+1]
        edges.append((x2-x1, node1, node2))
        edges.append((y2-y1, node3, node4))

    edges.sort(reverse=True)

    ans = 0
    uf = UnionFind(n)
    while uf.groups != 1:
        d, node1, node2 = edges.pop()
        if uf.is_same_group(node1, node2):
            continue
        uf.unite(node1, node2)
        ans += d

    print(ans)


if __name__ == "__main__":
    main()

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


class UnionFind:
    def __init__(self, num_of_node):
        self.roots = [-1] * num_of_node
        self.groups = num_of_node

    def get_root(self, node):
        root = self.roots[node]
        if root == -1:
            return node

        else:
            root = self.get_root(root)
            self.roots[node] = root
            return root

    def is_same_group(self, node1, node2):
        return self.get_root(node1) == self.get_root(node2)

    def unite(self, node1, node2):
        self.groups -= 1
        root1, root2 = self.get_root(node1), self.get_root(node2)
        self.roots[root2] = root1


def main():
    n = int(buf.readline())
    XY = map(int, buf.read().split())
    Xs = []
    Ys = []
    for i, (x, y) in enumerate(zip(XY, XY)):
        Xs.append((x-1, i))
        Ys.append((y-1, i))

    Xs.sort()
    Ys.sort()

    edges = []
    for i, ((x, node), (nx, new_node)) in enumerate(zip(Xs[:-1], Xs[1:])):
        edges.append((nx-x, node, new_node))

    for i, ((y, node), (ny, new_node)) in enumerate(zip(Ys[:-1], Ys[1:])):
        edges.append((ny-y, node, new_node))

    edges.sort(reverse=True)

    ans = 0
    uf = UnionFind(n)
    while uf.groups != 1:
        d, node1, node2 = edges.pop()
        if uf.is_same_group(node1, node2):
            continue
        uf.unite(node1, node2)
        ans += d

    print(ans)


if __name__ == "__main__":
    main()

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


class UnionFind:
    def __init__(self, num_of_node):
        self.roots = [-1] * num_of_node
        self.ranks = [1] * num_of_node
        self.groups = num_of_node

    def get_root(self, node):
        root = self.roots[node]
        if root == -1:
            return node

        else:
            root = self.get_root(root)
            self.roots[node] = root
            return root

    def is_same_group(self, node1, node2):
        return self.get_root(node1) == self.get_root(node2)

    def unite(self, node1, node2):
        self.groups -= 1
        root1, root2 = self.get_root(node1), self.get_root(node2)
        rank1, rank2 = self.ranks[root1], self.ranks[root2]
        if rank1 < rank2:
            root1, root2 = root2, root1

        self.roots[root2] = root1
        self.ranks[root2] += self.ranks[root1]


def main():
    n = int(buf.readline())
    XY = map(int, buf.read().split())
    Xs = []
    Ys = []
    for i, (x, y) in enumerate(zip(XY, XY)):
        Xs.append((x-1, i))
        Ys.append((y-1, i))

    Xs.sort()
    Ys.sort()

    edges = []
    for i, ((x, node), (nx, new_node)) in enumerate(zip(Xs[:-1], Xs[1:])):
        edges.append((nx-x, node, new_node))

    for i, ((y, node), (ny, new_node)) in enumerate(zip(Ys[:-1], Ys[1:])):
        edges.append((ny-y, node, new_node))

    edges.sort(reverse=True)

    ans = 0
    uf = UnionFind(n)
    while uf.groups != 1:
        d, node1, node2 = edges.pop()
        if uf.is_same_group(node1, node2):
            continue
        uf.unite(node1, node2)
        ans += d

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from heapq import heappush, heappop
buf = sys.stdin.buffer


def main():
    n = int(buf.readline())
    XY = map(int, buf.read().split())
    Xs = []
    Ys = []
    for i, (x, y) in enumerate(zip(XY, XY)):
        Xs.append((x-1, i))
        Ys.append((y-1, i))

    Xs.sort()
    Ys.sort()

    edges = [[] for _ in range(n)]
    for i, ((x, node), (nx, new_node)) in enumerate(zip(Xs[:-1], Xs[1:])):
        edges[node].append((nx-x, new_node))
        edges[new_node].append((nx-x, node))

    for i, ((y, node), (ny, new_node)) in enumerate(zip(Ys[:-1], Ys[1:])):
        edges[node].append((ny-y, new_node))
        edges[new_node].append((ny-y, node))

    seen = [False] * n
    dist = [float('INF')] * n
    todo = [(0, 0)]

    while todo:
        d, node = heappop(todo)
        if seen[node]:
            continue
        seen[node] = True
        dist[node] = d

        while edges[node]:
            edge = edges[node].pop()
            nd, to = edge
            if dist[to] <= nd:
                continue
            heappush(todo, (nd, to))

    print(sum(dist))


if __name__ == "__main__":
    main()

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


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

Xs.sort()
Ys.sort()

edges = [[] for _ in range(n)]
for i in range(n-1):
    x, node = Xs[i]
    nx, new_node = Xs[i+1]
    edges[node].append((nx-x, new_node))
    edges[new_node].append((nx-x, node))

for i in range(n-1):
    y, node = Ys[i]
    ny, new_node = Ys[i+1]
    edges[node].append((ny-y, new_node))
    edges[new_node].append((ny-y, node))

seen = [False] * n
dist = [float('INF')] * n
todo = [(0, 0)]

while todo:
    d, node = heapq.heappop(todo)
    if seen[node]:
        continue
    seen[node] = True
    dist[node] = d

    for edge in edges[node]:
        nd, to = edge
        if dist[to] <= nd:
            continue
        heapq.heappush(todo, (nd, to))

print(sum(dist))

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    XY = [[int(i) for i in input().split()] for j in range(N)]
    X = sorted([(xy[0], xy[1], i) for i, xy in enumerate(XY)])
    Y = sorted(X, key=lambda p: p[1])
    edges = []
    for i in range(N-1):
        (x1, y1, a) = X[i]
        (x2, y2, b) = X[i+1]
        cost = min(abs(x1-x2), abs(y1-y2))
        edges.append((cost, a, b))

    for i in range(N-1):
        (x1, y1, a) = Y[i]
        (x2, y2, b) = Y[i+1]
        cost = min(abs(x1-x2), abs(y1-y2))
        edges.append((cost, a, b))

    par = [i for i in range(N)]
    rank = [1 for i in range(N)]

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

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

    def unite(x, y):
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            x, y = y, x
        rank[x] += rank[y]
        par[y] = x

    def size(x):
        return rank[find_root(x)]

    edges.sort()

    ans = 0
    for (c, a, b) in edges:
        if find_root(a) != find_root(b):
            ans += c
            unite(a, b)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines




class UnionFind(object):
    def __init__(self, n = 1):
        self.link = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

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

        
        
        self.link[x] = self.find(self.link[x])
        return self.link[x]

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

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

        if self.size[x] < self.size[y]:
            x, y = y, x
        self.link[y] = x
        self.size[x] += self.size[y]
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]


N = int(input())

townsX = [0] * N
townsY = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    townsX[i] = (x - 1, y - 1, i)
    townsY[i] = (y - 1, x - 1, i)
townsX = sorted(townsX)
townsY = sorted(townsY)

edges = []
for i in range(1, N):
    a = townsX[i]
    b = townsX[i - 1]
    c = townsY[i]
    d = townsY[i - 1]
    e1 = (abs(a[0] - b[0]), a[2], b[2])
    e2 = (abs(c[0] - d[0]), c[2], d[2])
    edges.append(e1)
    edges.append(e2)
edges = sorted(edges)

u = UnionFind(N)


ans = 0
for e in edges:
    w, s, t = e
    if u.is_same(s, t):
        continue
    u.unite(s, t)
    ans += w
print(ans)

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines




class UnionFind(object):
    def __init__(self, n = 1):
        self.link = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

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

        
        
        self.link[x] = self.find(self.link[x])
        return self.link[x]

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

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

        if self.size[x] < self.size[y]:
            x, y = y, x
        self.link[y] = x
        self.size[x] += self.size[y]
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]


N = int(input())

townsX = [0] * N
townsY = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    townsX[i] = (x - 1, y - 1, i)
    townsY[i] = (y - 1, x - 1, i)
townsX = sorted(townsX)
townsY = sorted(townsY)

edges = []
for i in range(1, N):
    a = townsX[i]
    b = townsX[i - 1]
    c = townsY[i]
    d = townsY[i - 1]
    e1 = (abs(a[0] - b[0]), a[2], b[2])
    e2 = (abs(c[0] - d[0]), c[2], d[2])
    edges.append(e1)
    edges.append(e2)
edges = sorted(edges)

u = UnionFind(N)


ans = 0
for e in edges:
    w, s, t = e
    if u.is_same(s, t):
        continue
    u.unite(s, t)
    ans += w
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
n = int(input())
xy = []
for i in range(n):
    x, y = map(int, input().split())
    xy.append((i, x, y))
xx = sorted(xy, key=lambda x:x[1])
yy = sorted(xy, key=lambda x:x[2])
li = []
for i in range(n-1):
    li.append((xx[i][0], xx[i+1][0], xx[i+1][1]-xx[i][1]))
    li.append((yy[i][0], yy[i+1][0], yy[i+1][2]-yy[i][2]))
li.sort(key=lambda x:x[2])
class UnionFind():
    def __init__(self, li):
        self.li = li
    def root(self, x):
        if self.li[x]==x:
            return x
        self.li[x] = self.root(self.li[x])
        return self.li[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx==ry:
            return
        self.li[ry] = rx
    def same(self, x, y):
        return self.root(x)==self.root(y)
uf = UnionFind(list(range(n)))
ans = 0
for x, y, cost in li:
    if uf.same(x, y):
        continue
    uf.unite(x, y)
    ans += cost
print(ans)

Solution (Python):
from collections import defaultdict
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
N = int(input())
xy = [list(map(int,input().split())) for i in range(N)]
x,y = zip(*xy)






def Prim(g,cost):
    h = []
    N = len(g.keys())
    visited = [False]*(N+1)
    visited[1] = True
    v = 1
    for nv in g[v]:
        heappush(h, (cost[(v,nv)], (v,nv)))
    res = []
    d = 0
    while True:
        c, (v,nv) = heappop(h)
        if visited[nv]:
            continue
        res.append((v,nv))
        d += c
        if len(res) == N-1:
            break
        visited[nv] = True
        for nnv in g[nv]:
            if not visited[nnv]:
                heappush(h, (cost[(nv,nnv)], (nv,nnv)))
    return res, d

xi = [(x,i+1) for i,x in enumerate(x)]
yi = [(y,i+1) for i,y in enumerate(y)]

xi.sort()
yi.sort()

diffx = [(x1-x0,i0,i1) for (x0,i0),(x1,i1) in zip(xi,xi[1:])]
diffy = [(y1-y0,i0,i1) for (y0,i0),(y1,i1) in zip(yi,yi[1:])]

g = defaultdict(set)
cost = defaultdict(lambda : 10**10)
for d,i0,i1 in diffx:
    g[i0].add(i1)
    g[i1].add(i0)
    cost[(i0,i1)] = min(cost[(i0,i1)],d)
    cost[(i1,i0)] = min(cost[(i0,i1)],d)
for d,i0,i1 in diffy:
    g[i0].add(i1)
    g[i1].add(i0)
    cost[(i0,i1)] = min(cost[(i0,i1)],d)
    cost[(i1,i0)] = min(cost[(i0,i1)],d)

res,ans = Prim(g,cost)
print(ans)

Solution (Python):


import sys
input=sys.stdin.readline
import heapq

class UnionFind:
    def __init__(self, n):
        self.p=[-1]*n
        self.size=[1]*n
    def root(self, x):
        st=set()
        while(self.p[x]>=0):
            st.add(x)
            x=self.p[x]
        for y in st:
            self.p[y]=x
        return x
    def find(self, x, y):
        return self.root(x)==self.root(y)
    def union(self, x, y):
        r1=self.root(x)
        r2=self.root(y)
        if r1==r2:
            return
        p1=self.p[r1]
        p2=self.p[r2]
        if p1<=p2:
            self.p[r2]=r1
            self.size[r1]+=self.size[r2]
            if p1==p2:
                self.p[r1]-=1
        else:
            self.p[r1]=r2
            self.size[r2]+=self.size[r1]

def main():
    N=int(input())
    r=[tuple([i]+list(map(int,input().split()))) for i in range(N)]
    rx=sorted(r,key=lambda x:x[1])
    ry=sorted(r,key=lambda x:x[2])
    pq=[]
    for i in range(1,N):
        dx=abs(rx[i][1]-rx[i-1][1])
        heapq.heappush(pq,(dx,rx[i][0],rx[i-1][0]))
        dy=abs(ry[i][2]-ry[i-1][2])
        heapq.heappush(pq,(dy,ry[i][0],ry[i-1][0]))
    uft=UnionFind(N)
    ans=0
    while(uft.size[uft.root(0)]<N):
        e=heapq.heappop(pq)
        if not(uft.find(e[1],e[2])):
            ans+=e[0]
            uft.union(e[1],e[2])
    print(ans)
    
if __name__=="__main__":
    main()

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in 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

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

import copy
N = int(input())
A = [0] * N
for i in range(N):
  a, b = map(int, input().split())
  A[i] = [i, a, b]

B = copy.deepcopy(A)  
A = sorted(A, key = lambda x:x[1])
B = sorted(B, key = lambda x:x[2])




A2 = [0] * (N - 1)
for i in range(1, N):
  l = abs(A[i][1] - A[i - 1][1])
  A2[i - 1] = [A[i][0], A[i - 1][0], l]

B2 = [0] * (N - 1)
for i in range(1, N):
  l = abs(B[i][2] - B[i - 1][2])
  B2[i - 1] = [B[i][0], B[i - 1][0], l]  
Len = A2 + B2
Len = sorted(Len, key = lambda x:x[2])


data = UnionFind(N + 1)
cost = 0
for i in range(len(Len)):
    if not data.same_check(Len[i][0], Len[i][1]):
      data.union(Len[i][0], Len[i][1])
      cost += Len[i][2]

  
print(cost)

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
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy


class UnionFind:

    def __init__(self, n: int):
        self._n = n
        self._parents = [i for i in range(n)]
        self._rank = [1 for _ in range(n)]

    def unite(self, x: int, y: int) -> None:
        px = self.find(x)
        py = self.find(y)

        
        if px != py:
            self._link(px, py)

    def _link(self, x: int, y: int):
        if self._rank[x] < self._rank[y]:
            self._parents[x] = y
        elif self._rank[x] > self._rank[y]:
            self._parents[y] = x
        else:
            self._parents[x] = y
            self._rank[y] += 1

    def same(self, x: int, y: int) -> bool:
        px = self.find(x)
        py = self.find(y)
        return px == py

    def find(self, x: int) -> int:
        if self._parents[x] == x:
            return x

        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]


N = int(input())
ps = [list(map(int, input().split())) + [i] for i in range(N)]
ps.sort(key=lambda t: t[0])
xs = []
for i in range(N - 1):
    xs.append((ps[i + 1][0] - ps[i][0], ps[i][2], ps[i + 1][2]))

ps.sort(key=lambda t: t[1])
ys = []
for i in range(N - 1):
    ys.append((ps[i + 1][1] - ps[i][1], ps[i][2], ps[i + 1][2]))

xs += [(1<< 40, -1, -1)]
ys += [(1<< 40, -1, -1)]

xs.sort()
ys.sort()

xc, yc = 0, 0
uf = UnionFind(N)

ans = 0
while xc < N - 1 and yc < N - 1:
    if xs[xc][0] < ys[yc][0]:
        if not uf.same(xs[xc][1], xs[xc][2]):
            uf.unite(xs[xc][1], xs[xc][2])
            ans += xs[xc][0]
        xc += 1
    else:
        if not uf.same(ys[yc][1], ys[yc][2]):
            uf.unite(ys[yc][1], ys[yc][2])
            ans += ys[yc][0]
        yc += 1

print(ans)

Solution (Python):
n = int(input())
machi = []
li_x = []
li_y = []
for i in range(n):
    x, y = map(int, input().split())
    li_x.append((x, i))
    li_y.append((y, i))
    machi.append((x, y, i))
li_x.sort()
li_y.sort()
edge = [[] for _ in range(n)]
for i in range(n-1):
    edge[li_x[i][1]].append((li_x[i+1][0]-li_x[i][0], li_x[i+1][1]))
    edge[li_x[i+1][1]].append((li_x[i+1][0]-li_x[i][0], li_x[i][1]))
    edge[li_y[i][1]].append((li_y[i+1][0]-li_y[i][0], li_y[i+1][1]))
    edge[li_y[i+1][1]].append((li_y[i+1][0]-li_y[i][0], li_y[i][1]))

import heapq
def prim_heap(edge, n):
    used = [True] * n 
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist, e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist, e)
        res += minedge[0]
    return res
print(prim_heap(edge, n))