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):
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())
    
import heapq    
    
n = int(input())
a = []
b = []
for i in range(n):
    x,y= map(int, input().split())
    a.append((x,y,i))
    b.append((y,x,i))
a.sort()
b.sort()
edgea = []
edgeb = []
for i in range(n-1):
    edgea.append((a[i+1][0]-a[i][0],a[i][2],a[i+1][2]))
    edgeb.append((b[i+1][0]-b[i][0],b[i][2],b[i+1][2]))
edge = edgea+edgeb
heapq.heapify(edge)

uf = UnionFind(n)
ans = 0
while len(edge):
    x,y,z = heapq.heappop(edge)
    if not uf.same(y,z):
        ans += x
        uf.union(y,z)
print(ans)

Solution (Python):
class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    def find(self, x):
        stack = []
        parent = self.parent
        while parent[x] != x:
            stack.append(x)
            x = parent[x]
        for y in stack:
            parent[y] = x
        return x

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        
        if self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        elif self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif xr != yr:
            self.parent[yr] = xr
            self.rank[xr] += 1

from itertools import chain

N = int(input())
points = tuple(tuple(map(int,input().split())) for _ in range(N))
ds = DisjointSet(N)

x_i = sorted((x,i) for i,(x,y) in enumerate(points))
y_i = sorted((y,i) for i,(x,y) in enumerate(points))

xr = [x_i[0]]
yr = [y_i[0]]

for (x0,i0),(x1,i1) in zip(x_i,x_i[1:]):
    if x0 == x1:
        ds.union(i0,i1)
    else:
        xr.append((x1,i1))

for (y0,i0),(y1,i1) in zip(y_i,y_i[1:]):
    if y0 == y1:
        ds.union(i0,i1)
    else:
        yr.append((y1,i1))

deltas = sorted(
        chain(
            ((x1-x0,i0,i1) for (x0,i0), (x1,i1) in zip(xr,xr[1:])),
            ((y1-y0,i0,i1) for (y0,i0), (y1,i1) in zip(yr,yr[1:])),
        )
    )


def it():
    for d,i0,i1 in deltas:
        i0,i1 = ds.find(i0), ds.find(i1)
        if i0 != i1:
            ds.union(i0,i1)
            yield d
print(sum(it()))

Solution (Python):
class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    def find(self, x):
        stack = []
        parent = self.parent
        while parent[x] != x:
            stack.append(x)
            x = parent[x]
        for y in stack:
            parent[y] = x
        return x

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        
        if self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        elif self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif xr != yr:
            self.parent[yr] = xr
            self.rank[xr] += 1

from itertools import chain

N = int(input())
points = tuple(tuple(map(int,input().split())) for _ in range(N))
ds = DisjointSet(N)

x_i = sorted((x,i) for i,(x,y) in enumerate(points))
y_i = sorted((y,i) for i,(x,y) in enumerate(points))

xr = [x_i[0]]
yr = [y_i[0]]

for (x0,i0),(x1,i1) in zip(x_i,x_i[1:]):
    if x0 == x1:
        ds.union(i0,i1)
    else:
        xr.append((x1,i1))

for (y0,i0),(y1,i1) in zip(y_i,y_i[1:]):
    if y0 == y1:
        ds.union(i0,i1)
    else:
        yr.append((y1,i1))

deltas = sorted(
        chain(
            ((x1-x0,i0,i1) for (x0,i0), (x1,i1) in zip(xr,xr[1:])),
            ((y1-y0,i0,i1) for (y0,i0), (y1,i1) in zip(yr,yr[1:])),
        )
    )


def it():
    for d,i0,i1 in deltas:
        i0,i1 = ds.find(i0), ds.find(i1)
        if i0 != i1:
            ds.union(i0,i1)
            yield d
print(sum(it()))

Solution (Python):
import sys
read = sys.stdin.read
from operator import itemgetter
from copy import deepcopy
from collections import deque
def main():
    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 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)
    def size(x):
        return -par[find(x)]
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]
    def roots():
        return [i for i, x in enumerate(par) if x < 0]

    
    n = int(input())
    m = map(int, read().split())
    
    mm = zip(m, m)
    cnt = 0
    nodes = []
    nodes_a = nodes.append
    for a, b in mm:
        
        nodes_a((a, b, cnt))
        cnt += 1
    nodes.sort(key=itemgetter(0))
    nodes_y = deepcopy(nodes)
    nodes_y.sort(key=itemgetter(1))
    
    edges = []
    for i1 in range(n - 1):
        
        edges.append((nodes[i1+1][0] - nodes[i1][0], nodes[i1][2], nodes[i1+1][2]))
        edges.append((nodes_y[i1+1][1] - nodes_y[i1][1], nodes_y[i1][2], nodes_y[i1+1][2]))
    
    edges.sort(key=itemgetter(0))
    
    par = [-1] * n  
    edges = deque(edges)  
    r = 0  
    while edges:
        e = edges.popleft()
        if not same(e[1], e[2]):
            r += e[0]
            unite(e[1], e[2])
    print(r)

if __name__ == '__main__':
    main()

Solution (Python):


import sys
input = sys.stdin.readline

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 False

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

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



N = int(input())


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

datax = sorted(data, key=lambda x:x[1])
datay = sorted(data, key=lambda x:x[2])

cost = []
for i in range(N-1):
    p, q = datax[i:i+2]
    pi, px, py = p
    qi, qx, qy = q
    cost.append((pi, qi, min(abs(px-qx), abs(py-qy))))
    cost.append((qi, pi, min(abs(px-qx), abs(py-qy))))
    p, q = datay[i:i+2]
    pi, px, py = p
    qi, qx, qy = q
    cost.append((pi, qi, min(abs(px-qx), abs(py-qy))))
    cost.append((qi, pi, min(abs(px-qx), abs(py-qy))))

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

tree = UnionFind(N)
res = 0
for p, q, dist in cost:
    
    
    if tree.union(p, q):
        res += dist                                                 

print(res)

Solution (Python):
class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        
        if self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        elif self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif xr != yr:
            self.parent[yr] = xr
            self.rank[xr] += 1

from itertools import chain

N = int(input())
points = tuple(tuple(map(int,input().split())) for _ in range(N))
ds = DisjointSet(N)

x_i = sorted((x,i) for i,(x,y) in enumerate(points))
y_i = sorted((y,i) for i,(x,y) in enumerate(points))

xr = [x_i[0]]
yr = [y_i[0]]

for (x0,i0),(x1,i1) in zip(x_i,x_i[1:]):
    if x0 == x1:
        ds.union(i0,i1)
    else:
        xr.append((x1,i1))

for (y0,i0),(y1,i1) in zip(y_i,y_i[1:]):
    if y0 == y1:
        ds.union(i0,i1)
    else:
        yr.append((y1,i1))

deltas = sorted(
        chain(
            ((x1-x0,i0,i1) for (x0,i0), (x1,i1) in zip(xr,xr[1:])),
            ((y1-y0,i0,i1) for (y0,i0), (y1,i1) in zip(yr,yr[1:])),
        )
    )


def it():
    for d,i0,i1 in deltas:
        if ds.find(i0) != ds.find(i1):
            ds.union(i0,i1)
            yield d
print(sum(it()))

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.size = [1] * (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 same_check(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]:
            if self.same_check(x, y) != True:
                self.size[y] += self.size[x]
                self.size[x] = 0
            self.par[x] = y
        else:
            if self.same_check(x, y) != True:
                self.size[x] += self.size[y]
                self.size[y] = 0
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N = int(input())
UF = UnionFind(N)
X = []
Y = []
Branch = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((x, i))
    Y.append((y, i))
X.sort()
Y.sort()
for X1, X2 in zip(X, X[1:]):
    Branch.append((X2[0] - X1[0], X1[1], X2[1]))
for Y1, Y2 in zip(Y, Y[1:]):
    Branch.append((Y2[0] - Y1[0], Y1[1], Y2[1]))
Branch.sort()


par = [-1] * N
ans = 0
for c, a, b in Branch:
    if N <= 1:
        break
    if not UF.same_check(a, b):
        UF.union(a, b)
        ans += c
        N -= 1

print(ans)

Solution (Python):
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
x,y=zip(*xy)
x=list(zip(range(n),x))
y=list(zip(range(n),y))
x.sort(key=lambda a:a[1])
y.sort(key=lambda a:a[1])
d=[]
for i in range(n-1):
  d.append([x[i+1][1]-x[i][1],x[i+1][0],x[i][0]])
  d.append([y[i+1][1]-y[i][1],y[i+1][0],y[i][0]])
d.sort(key=lambda a:a[0],reverse=True)

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

ans=0
uf=UnionFind(n)
while d:
  dist,i,j=d.pop()
  if uf.same(i,j):
    continue
  uf.union(i,j)
  ans+=dist
print(ans)

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

n = int(input()) 
ixy = [[i] + [int(x) for x in input().split()] for i in range(n)]

edge = set()

for key in [itemgetter(1),itemgetter(2)]:
    ixy.sort(key = key)
    for i in range(n-1):
        i1, i2 = ixy[i][0], ixy[i+1][0]
        x1, x2 = ixy[i][1], ixy[i+1][1]
        y1, y2 = ixy[i][2], ixy[i+1][2]
        d = min(abs(x2-x1), abs(y2-y1))
        edge.add((i1,i2,d))
    
row,col,value = zip(*edge)
csr_ = csr_matrix((value, (row,col)), shape=(n, n))
mst = minimum_spanning_tree(csr_, overwrite=True).astype(int)
print(mst.sum())

Solution (Python):
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
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
n=int(input())
points=[list(map(int,input().split()))+[i] for i in range(n)]
points.sort(key = lambda x:x[1])
edge=[]
for i in range(n-1):
    edge.append((points[i][2],points[i+1][2],points[i+1][1]-points[i][1]))
points.sort()
for i in range(n-1):
    edge.append((points[i][2],points[i+1][2],points[i+1][0]-points[i][0]))
class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for i in range(N)]
    
    def merge(self, a, b):
        if self.issame(a,b):
            return
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
        self.size[pb] += self.size[pa]
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r
    
    def issame(self, x, y):
        return self.root(x) == self.root(y)
    
    def getsize(self, x):
        return self.size[self.root(x)]
edge.sort(key=lambda x:x[2])
uf=UnionFind(n)
ans=0
for ed in edge:
    if uf.issame(ed[0],ed[1]):continue
    ans+=ed[2]
    uf.merge(ed[0],ed[1])
print(ans)

Solution (Python):
from heapq import heappop, heappush, heapify

class Graph():  
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.edge = edge
        self.indexed = indexed
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.graph[e[1] - indexed].append((e[0] - indexed, e[2]))

    def prim(self):
        used = [False for _ in range(self.n)]
        used[0] = True
        heap = [(cost, adj) for adj, cost in self.graph[0]]
        heapify(heap)
        res = 0
        while heap:
            cost, node = heappop(heap)
            if used[node]:
                continue
            used[node] = True
            res += cost
            for adj, adjcost in self.graph[node]:
                if used[adj]:
                    continue
                heappush(heap, (adjcost, adj))
        return res

import sys
input = sys.stdin.readline

N = int(input())
T = []

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

sort_by_x = sorted(T, key=lambda x: x[0])
sort_by_y = sorted(T, key=lambda x: x[1])

E = []

for i in range(N - 1):
    x1, y1, id1 = sort_by_x[i]
    x2, y2 ,id2 = sort_by_x[i + 1]
    E.append((id1, id2, min(abs(x1 - x2), abs(y1 - y2))))
    x1, y1, id1 = sort_by_y[i]
    x2, y2 ,id2 = sort_by_y[i + 1]
    E.append((id1, id2, min(abs(x1 - x2), abs(y1 - y2))))

g = Graph(N, E, 0)

print(g.prim())

Solution (Python):
class Graph():  
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.edge = edge
        self.indexed = indexed
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.graph[e[1] - indexed].append((e[0] - indexed, e[2]))

    def kruskal(self):  
        
        sortedge = sorted(self.edge, key=lambda x: x[2])
        
        uf = UnionFind(self.n)
        res = 0
        restored = []
        for e in sortedge:
            if uf.find(e[0] - self.indexed) != uf.find(e[1] - self.indexed):
                res += e[2]
                
                uf.unite(e[0] - self.indexed, e[1] - self.indexed)
        return res

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

    def find(self, x):
        root = x
        while self.parents[root] != root:
            root = self.parents[root]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root

    def unite(self, x, y):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot: return
        xrank = self.rank[xroot]
        yrank = self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
            self.size[yroot] += self.size[xroot]
        elif xrank == yrank:
            self.parents[yroot] = xroot
            self.rank[yroot] += 1
            self.size[xroot] += self.size[yroot]
        else:
            self.parents[yroot] = xroot
            self.size[xroot] += self.size[yroot]

import sys
input = sys.stdin.readline

N = int(input())
T = []

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

sort_by_x = sorted(T, key=lambda x: x[0])
sort_by_y = sorted(T, key=lambda x: x[1])

E = []

for i in range(N - 1):
    x1, y1, id1 = sort_by_x[i]
    x2, y2 ,id2 = sort_by_x[i + 1]
    E.append((id1, id2, min(abs(x1 - x2), abs(y1 - y2))))
    x1, y1, id1 = sort_by_y[i]
    x2, y2 ,id2 = sort_by_y[i + 1]
    E.append((id1, id2, min(abs(x1 - x2), abs(y1 - y2))))

g = Graph(N, E)

print(g.kruskal())

Solution (Python):
class Graph():  
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.edge = edge
        self.indexed = indexed
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.graph[e[1] - indexed].append((e[0] - indexed, e[2]))

    def kruskal(self):  
        edgemap = {self.edge[i]: i for i in range(len(self.edge))}
        sortedge = sorted(self.edge, key=lambda x: x[2])
        
        uf = UnionFind(self.n)
        res = 0
        restored = []
        for e in sortedge:
            if uf.find(e[0] - self.indexed) != uf.find(e[1] - self.indexed):
                res += e[2]
                restored.append(edgemap[e])
                uf.unite(e[0] - self.indexed, e[1] - self.indexed)
        return res, restored

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

    def find(self, x):
        root = x
        while self.parents[root] != root:
            root = self.parents[root]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root

    def unite(self, x, y):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot: return
        xrank = self.rank[xroot]
        yrank = self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
            self.size[yroot] += self.size[xroot]
        elif xrank == yrank:
            self.parents[yroot] = xroot
            self.rank[yroot] += 1
            self.size[xroot] += self.size[yroot]
        else:
            self.parents[yroot] = xroot
            self.size[xroot] += self.size[yroot]

import sys
input = sys.stdin.readline

N = int(input())
T = []

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

sort_by_x = sorted(T, key=lambda x: x[0])
sort_by_y = sorted(T, key=lambda x: x[1])

E = []

for i in range(N - 1):
    x1, y1, id1 = sort_by_x[i]
    x2, y2 ,id2 = sort_by_x[i + 1]
    E.append((id1, id2, min(abs(x1 - x2), abs(y1 - y2))))
    x1, y1, id1 = sort_by_y[i]
    x2, y2 ,id2 = sort_by_y[i + 1]
    E.append((id1, id2, min(abs(x1 - x2), abs(y1 - y2))))

g = Graph(N, E)

print(g.kruskal()[0])

Solution (Python):
import sys
import collections
sys.setrecursionlimit(10 ** 8)

def input(): return sys.stdin.readline().strip()
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

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

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

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

def main():
    N = Z()
    Cs = [ZZ()+[i] for i in range(N)]
    X = sorted(Cs)
    Y = sorted(Cs, key=lambda x:x[1])
    es = []
    for i in range(N-1):
        c = X[i+1][0] - X[i][0]
        u, v = X[i][2], X[i+1][2]
        es.append([c, u, v])
    for i in range(N-1):
        c = Y[i+1][1] - Y[i][1]
        u, v = Y[i][2], Y[i+1][2]
        es.append([c, u, v])
    es.sort()
    uf = UnionFind(N)
    output = 0
    for i in range(len(es)):
        c, u, v = es[i]
        if not uf.same(u, v):
            uf.unite(u, v)
            output += c
    print(output)

    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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 main():
    N, *XY = map(int, read().split())
    X = list(zip(XY[::2], range(N)))
    Y = list(zip(XY[1::2], range(N)))

    X.sort()
    Y.sort()

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

    edge.sort()

    uf = UnionFind(N)
    ans = 0
    for d, s, t in edge:
        if not uf.same(s, t):
            uf.union(s, t)
            ans += d

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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 main():
    N, *XY = map(int, read().split())
    X = list(zip(XY[::2], range(N)))
    Y = list(zip(XY[1::2], range(N)))

    X.sort()
    Y.sort()

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

    edge.sort()

    uf = UnionFind(N)
    ans = 0
    for d, s, t in edge:
        if not uf.same(s, t):
            uf.union(s, t)
            ans += d

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
l=sorted([list(map(int,input().split()))+[i] for i in range(n)])
xs=[(x,i)for x,y,i in l]
ys=sorted([(x,i)for y,x,i in l])
edges={}
for i in range(1,n):
    a,s=xs[i-1];d,f=xs[i]
    if (s,f)in edges:
        edges[(s,f)]=min(edges[(s,f)],abs(a-d))
    else:edges[(s,f)]=abs(a-d)
    a,s=ys[i-1];d,f=ys[i]
    if (s,f)in edges:
        edges[(s,f)]=min(edges[(s,f)],abs(a-d))
    else:edges[(s,f)]=abs(a-d)
edges=sorted(edges.items(),key=lambda x:x[1])
class UnionFind:
    
    
    __slots__ = ["_size", "_first_idx", "_parents"]
    def __init__(self, size: int, first_index: int = 0) -> None:
        self._size = size
        self._first_idx = first_index
        self._parents = [-1] * (size + first_index)
    def find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]
    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)
    def unite(self, x: int, y: int) -> bool:
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x
        return True
    def size(self, x: int) -> int:
        return -self._parents[self.find(x)]
    def group_count(self) ->int:
        return sum(1 for i in  self._parents if i<0)-self._first_idx
    def connected(self) ->bool:
        return self._parents[self.find(self._first_idx)]==-self._size
uf=UnionFind(n)
ans=edges[0][1]
uf.unite(*edges[0][0])
for f,c in edges:
    if uf.same(*f):continue
    uf.unite(*f)
    ans+=c
print(ans)

Solution (Python):
import heapq


class UnionFind:
    from collections import deque

    def __init__(self, v):
        self.v = v
        self._tree = list(range(v + 1))

    def _root(self, a):
        queue = self.deque()
        while self._tree[a] != a:
            queue.append(a)
            a = self._tree[a]
        while queue:
            index = queue.popleft()
            self._tree[index] = a
        return a

    def union(self, a, b):
        root_a = self._root(a)
        root_b = self._root(b)
        self._tree[root_b] = root_a

    def find(self, a, b):
        return self._root(a) == self._root(b)


N = int(input())
V = []
for i in range(N):
    s, t = map(int, input().split(' '))
    V.append((i, s, t))

E = []
vx = sorted(V, key=lambda v: v[1])
for v1, v2 in zip(vx, vx[1:]):
    i, x1, y1 = v1
    j, x2, y2 = v2
    heapq.heappush(E, (abs(x1 - x2), i, j))

vy = sorted(V, key=lambda v: v[2])
for v1, v2 in zip(vy, vy[1:]):
    i, x1, y1 = v1
    j, x2, y2 = v2
    heapq.heappush(E, (abs(y1 - y2), i, j))

uf = UnionFind(N)
cost = 0
while E:
    c, i, j = heapq.heappop(E)
    if not uf.find(i, j):
        uf.union(i, j)
        cost += c

print(cost)

Solution (Python):
class UnionFind:
    def __init__(self,n):
        self.v=[-1]*n
    
    def find(self,x):
        if self.v[x]<0:
            return x
        else:
            self.v[x]=self.find(self.v[x])
            return self.v[x]
    
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)

        if x==y:
            return False
        else:
            if self.v[x]>self.v[y]:
                x,y=y,x
            self.v[x]+=self.v[y]
            self.v[y]=x
            return True
    
    def same(self,x,y):
        return self.find(x)==self.find(y)
    
    def size(self,x):
        return -self.v[self.find(x)]

import sys

N=int(sys.stdin.readline())
ps=[]
xs=set()
ys=set()
for i in range(N):
    x,y=map(int,input().split())
    ps.append((x,y))
    xs.add(x)
    ys.add(y)

xs=tuple(sorted(xs))
ys=tuple(sorted(ys))

dx={e:i for i,e in enumerate(xs)}
dy={e:i for i,e in enumerate(ys)}
uf=(UnionFind(N*2))
for x,y in ps:
    uf.unite(dx[x],dy[y]+N)

def make_edges(xs,start):
    xes=[]
    for i, (x0,x1) in enumerate(zip(xs,xs[1:]),start=start):
        xes.append((abs(x1-x0), i, i+1))
    return xes

xes=make_edges(xs,start=0)
yes=make_edges(ys,start=N)

ret=0
for cost,a,b in sorted(xes+yes,key=lambda x:x[0]):
    if uf.same(a,b):
        continue
    uf.unite(a,b)
    ret+=cost
print(ret)