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 UnionFindNode:
    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1
        self.member_num_ = 1

    def is_root(self):
        return not self.parent_

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

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

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
                root.member_num_ = root.member_num_ + unite_root.member_num_
            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                unite_root.member_num_ = root.member_num_ + unite_root.member_num_

N, = map(int, input().split())
X,Y = [],[]
for i in range(1, N+1):
    x, y = map(int, input().split())
    X.append((x,i))
    Y.append((y,i))
X = sorted(X, key=lambda x:x[0])
Y = sorted(Y, key=lambda x:x[0])
G = [set() for _ in range(N+1)]
Es = set()
for i in range(N-1):
    Es.add((tuple(sorted([X[i][1], X[i+1][1]])), abs(X[i][0]-X[i+1][0])))
    Es.add((tuple(sorted([Y[i][1], Y[i+1][1]])), abs(Y[i][0]-Y[i+1][0])))
    G[X[i][1]].add(X[i+1][1])
    G[Y[i][1]].add(Y[i+1][1])
    G[X[i+1][1]].add(X[i][1])
    G[Y[i+1][1]].add(Y[i][1])
node_list = [UnionFindNode(i) for i in range(N+1)]
Es = sorted(Es, key=lambda x:x[1])

r = 0
for (x, y), c in Es:
    if node_list[x].find() == node_list[y].find():
        continue
    r += c
    node_list[x].unite(node_list[y])

print(r)

Solution (Python):
import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.readline
N = int(input())
p = [tuple(map(int, input().split())) for _ in range(N)]
e = dd(list)
p = [(i, p[i][0], p[i][1]) for i in range(N)]
p.sort(key = lambda x: x[1])
for i in range(N - 1):
  x = p[i][0]
  y = p[i + 1][0]
  e[x].append((y, abs(p[i][1] - p[i + 1][1])))
  e[y].append((x, abs(p[i][1] - p[i + 1][1])))
p.sort(key = lambda x: x[2])
for i in range(N - 1):
  x = p[i][0]
  y = p[i + 1][0]
  e[x].append((y, abs(p[i][2] - p[i + 1][2])))
  e[y].append((x, abs(p[i][2] - p[i + 1][2])))
class prim:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def MSTcost(self):
    h = []
    visited = [0] * (self.n + 1)
    ks = list(self.e.keys())
    b = pow(10, 10)
    for edge in self.e[ks[0]]:
      heapq.heappush(h, edge[1] * b + edge[0])
    res = 0
    visited[ks[0]] = 1
    while len(h):
      p = heapq.heappop(h)
      p0 = p // b
      p1 = p % b
      if visited[p1]: continue
      visited[p1] = 1
      for q in self.e[p1]:
        if visited[q[0]]:
          continue
        heapq.heappush(h, q[1] * b + q[0])
      res += p0
    return res
pri = prim(N, e)
print(pri.MSTcost())

Solution (Python):
import heapq
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(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
            self.rank[x] += (self.rank[x] == self.rank[y])

def kruskal(n, edge):
    ans = 0
    uf = UnionFind(n)
    while True:
        d, v, u = heapq.heappop(edge)
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            n -= 1
            ans += d
        if n < 2: return ans
    return ans

n = int(input())
x, y = [None]*n, [None]*n

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

x.sort(key=lambda x:x[0])
y.sort(key=lambda y:y[0])

edge = []
for i in range(n-1):
    heapq.heappush(edge, (x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    heapq.heappush(edge, (y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))

del x, y
print(kruskal(n, edge))

Solution (Python):
N=int(input())
import sys
input=sys.stdin.readline
X=[(-10**10,0)]
Y=[(-10**10,0)]

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



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

C=[1 for i in range(N+2)]
C[0]=0
C[-1]=0
C[1]=0
import heapq
ans=0
Q=L[1]
heapq.heapify(Q)
for i in range(10**6):
    
    
    if len(Q)==0:
        break
    q=heapq.heappop(Q)
    if C[q[1]]==0:
        continue
    else:
        C[q[1]]=0
        ans+=q[0]
        for j in range(4):
            if C[L[q[1]][j][1]]==1:
                heapq.heappush(Q,L[q[1]][j])
print(ans)

Solution (Python):
N=int(input())
city=[0]*N
for i in range(N):
    x,y=map(int,input().split())
    city[i]=(i,x,y)
city.sort(key=lambda x:x[1])
data=[(city[i][0],city[i+1][0],city[i+1][1]-city[i][1]) for i in range(N-1)]
city.sort(key=lambda x:x[2])
data+=[(city[i][0],city[i+1][0],city[i+1][2]-city[i][2]) for i in range(N-1)]
data.sort(key=lambda x:x[2])
f = list(range(N))
costs = [1] * N
def find(x):
    if f[x] != x:
        f[x] = find(f[x])
    return f[x]
res = 0
for i, j, k in data:
    fi, fj = find(i), find(j)
    if fi == fj:
        continue
    else:
        if costs[fi] <= costs[fj]:
            f[fi] = fj
            costs[fj] += costs[fi]
            res += k
        else:
            f[fj] = fi
            costs[fi] += costs[fj]
            res += k
print(res)

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

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

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

def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    X = []
    Y = []
    for i in range(1,N+1):
        x,y = map(int,input().split())
        X.append([x,i])
        Y.append([y,i])
    
    X = sorted(X,key=lambda a:a[0])
    Y = sorted(Y,key=lambda a:a[0])
    DX = []
    DY = []
    for i in range(N-1):
        x1,i1 = X[i]
        x2,i2 = X[i+1]
        DX.append([abs(x1-x2),i1,i2])
        y1,i1 = Y[i]
        y2,i2 = Y[i+1]
        DY.append([abs(y1-y2),i1,i2])
    
    DX = sorted(DX,key=lambda a:a[0])
    DY = sorted(DY,key=lambda a:a[0])
    
    
        
    ans = 0
    A = UnionFind(N)
    i,j = 0,0
    c = 0
    while c < N-1:
        if i<=N-2 and j<=N-2:
            if DX[i][0] < DY[j][0]:
                cost,m1,m2 = DX[i]
                if not A.same_check(m1,m2):
                    
                    A.union(m1,m2)
                    c += 1
                    ans += cost
                i += 1
            else:
                cost,m1,m2 = DY[j]
                if not A.same_check(m1,m2):
                    
                    A.union(m1,m2)
                    c += 1
                    ans += cost
                j += 1
        elif i==N-1:
            cost,m1,m2 = DY[j]
            if not A.same_check(m1,m2):
                
                A.union(m1,m2)
                c += 1
                ans += cost
            j += 1
        else:
            cost,m1,m2 = DX[i]
            if not A.same_check(m1,m2):
                
                A.union(m1,m2)
                c += 1
                ans += cost
            i += 1
    print(ans)
        
    
    
main()

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

def same_tree(node_a, node_b):
    if node_a.root() == node_b.root():
        return True

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        node = self
        while not node.is_root:
            node = node.parent
        return node

def main():
    N = int(input())
    
    nodes = [Node() for i in range(N)]

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

    
    edges = []
    for i in range(1, N):
        edges.append((xs[i][0] - xs[i-1][0], xs[i-1][1], xs[i][1]))
        edges.append((ys[i][0] - ys[i-1][0], ys[i-1][1], ys[i][1]))
    edges = sorted(edges)

    
    ans = 0
    for (cost, a, b) in edges:
        if not same_tree(nodes[a], nodes[b]):
            unite(nodes[a], nodes[b])
            ans += cost
    print(ans)

if __name__ == "__main__":
    main()

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

def same_tree(node_a, node_b):
    if node_a.root() == node_b.root():
        return True

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        node = self
        while not node.is_root:
            node = node.parent
        return node

def main():
    N = int(input())
    
    nodes = [Node() for i in range(N)]

    
    xy = []
    for i in range(N):
        x, y = map(int, input().split())
        xy.append((i, x, y))
    
    
    edges = []
    xy = sorted(xy, key=lambda x: x[1])
    
    for i in range(1, N):
        edges.append((xy[i][1] - xy[i-1][1], xy[i-1][0], xy[i][0]))
    xy = sorted(xy, key=lambda x: x[2])
    
    for i in range(1, N):
        edges.append((xy[i][2] - xy[i-1][2], xy[i-1][0], xy[i][0]))
    
    ans = 0
    edges = sorted(edges)
    
    for (cost, a, b) in edges:
        if not same_tree(nodes[a], nodes[b]):
            unite(nodes[a], nodes[b])
            ans += cost
    print(ans)




if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    class UnionFind(object):
        """
        query: O(Ack^-1(n,n)) (amortize)
        """
        def __init__(self,n):
            """
            param n: number of nodes
            """
            self.__par=list(range(n))
            self.__rank=[0]*n
            self.__size=[1]*n

        def __root(self,k):
            if self.__par[k]==k: return k
            else:
                self.__par[k]=self.__root(self.__par[k])
                return self.__par[k]

        def is_same(self,i,j):
            return self.__root(i)==self.__root(j)

        def unite(self,i,j):
            i=self.__root(i)
            j=self.__root(j)
            if i==j: return
            if self.__rank[i]>self.__rank[j]:
                self.__par[j]=i
            else:
                self.__par[i]=j
                if self.__rank[i]==self.__rank[j]: self.__rank[j]+=1

    
    from operator import itemgetter
    n=int(input())
    P=[0]*n
    edges=[0]*(2*n-2)
    for i in range(n):
        x,y=map(int,input().split())
        P[i]=(x,y,i)
    
    P.sort(key=itemgetter(0))
    for k in range(n-1):
        x0,y0,i=P[k]
        x1,y1,j=P[k+1]
        edges[k]=(i,j,min(abs(x0-x1),abs(y0-y1)))
    
    P.sort(key=itemgetter(1))
    for k in range(n-1):
        x0,y0,i=P[k]
        x1,y1,j=P[k+1]
        edges[k+n-1]=(i,j,min(abs(x0-x1),abs(y0-y1)))
    
    edges.sort(key=itemgetter(2))
    
    tree=UnionFind(n)
    ans=0
    for i,j,cost in edges:
        if tree.is_same(i,j): continue
        tree.unite(i,j)
        ans+=cost
    print(ans)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7

def resolve():
    class UnionFind(object):
        """
        query: O(Ack^-1(n,n)) (amortize)
        """
        def __init__(self,n):
            """
            param n: number of nodes
            """
            self.__par=list(range(n))
            self.__rank=[0]*n
            self.__size=[1]*n

        def __root(self,k):
            if self.__par[k]==k: return k
            else:
                self.__par[k]=self.__root(self.__par[k])
                return self.__par[k]

        def is_same(self,i,j):
            return self.__root(i)==self.__root(j)

        def unite(self,i,j):
            i=self.__root(i)
            j=self.__root(j)
            if i==j: return
            if self.__rank[i]>self.__rank[j]:
                self.__par[j]=i
            else:
                self.__par[i]=j
                if self.__rank[i]==self.__rank[j]: self.__rank[j]+=1

    
    
    from operator import itemgetter
    n=int(input())
    P=[0]*n
    edges=[0]*(2*n-2)
    for i in range(n):
        x,y=map(int,input().split())
        P[i]=(x,y,i)
    
    P.sort(key=itemgetter(0))
    for k in range(n-1):
        x0,y0,i=P[k]
        x1,y1,j=P[k+1]
        edges[k]=(i,j,min(abs(x0-x1),abs(y0-y1)))
    
    P.sort(key=itemgetter(1))
    for k in range(n-1):
        x0,y0,i=P[k]
        x1,y1,j=P[k+1]
        edges[k+n-1]=(i,j,min(abs(x0-x1),abs(y0-y1)))
    
    edges.sort(key=itemgetter(2))
    
    tree=UnionFind(n)
    ans=0
    for i,j,cost in edges:
        if tree.is_same(i,j): continue
        tree.unite(i,j)
        ans+=cost
    print(ans)

resolve()

Solution (Python):

class uf_tree():

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

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

    def unite(self,x,y):
        if self.root(x) == self.root(y):
            return
        else:
            rootx = self.root(x)
            rooty = self.root(y)
            if self.rank[rootx] < self.rank[rooty]:
                self.par[rootx] = rooty
            else:
                self.par[rooty] = rootx
                if self.rank[rootx] == self.rank[rooty]:
                    self.rank[rootx] += 1
    def root(self,i):
        if self.par[i] == i:
            return i
        else:
            self.par[i] = self.root(self.par[i])
            return self.par[i]

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

def kruscal(n,edge_arr):
    edge_arr.sort(key=lambda x:x[2])
    ans = []
    tree = uf_tree(n)
    for e in edge_arr:
        s = e[0]-1
        g = e[1]-1
        if tree.same(s,g):
            continue
        else:
            ans.append(e)
            tree.unite(s,g)
    return ans

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

p.sort(key = lambda x:x[0])
for i in range(n-1):
    cost = min(abs(p[i+1][0]-p[i][0]),abs(p[i+1][1]-p[i][1]))
    edge.append([p[i][2],p[i+1][2],cost])

p.sort(key = lambda x:x[1])
for i in range(n-1):
    cost = min(abs(p[i+1][0]-p[i][0]),abs(p[i+1][1]-p[i][1]))
    edge.append([p[i][2],p[i+1][2],cost])

ans = kruscal(n,edge)
tot = 0
for e in ans:
    tot += e[2]
print(tot)

Solution (Python):

import heapq

def prime_method():
    not_went = [True] * n  
    edges = []
    start = graph[0]
    for e in start:
        heapq.heappush(edges,e)
    not_went[0] = False
    cost = 0
    while len(edges) != 0:
        minedge = heapq.heappop(edges)
        if not not_went[minedge[1]]:
            continue
        v = minedge[1]
        gv = graph[v]
        not_went[v] = False
        for temp in gv:
            if not_went[temp[1]]:  
                heapq.heappush(edges, temp)
        cost += minedge[0]
    return cost
    


n = int(input())
graph = [[] for i in  range(n)]
cities = []
for i in range(n):
    cities.append(tuple(map(int,input().split()))+tuple([i]))


citiesX=sorted(cities,key=lambda x:x[0])
citiesY=sorted(cities,key=lambda x:x[1])

for i in range(n-1):
    graph[citiesX[i][2]].append(((citiesX[i+1][0] - citiesX[i][0]),citiesX[i+1][2]))
    graph[citiesX[i+1][2]].append(((citiesX[i+1][0] - citiesX[i][0]),citiesX[i][2]))
    graph[citiesY[i][2]].append(((citiesY[i+1][1] - citiesY[i][1]),citiesY[i+1][2]))
    graph[citiesY[i+1][2]].append(((citiesY[i+1][1] - citiesY[i][1]),citiesY[i][2]))
print(prime_method())

Solution (Python):
from heapq import *

def prim(V, E):
    '''
    Input:
        V = list(range(N))
        E = {i: defaultdict(int) for i in range(N)}
    Output:
        the edges of the minimum weight tree and its weight
    '''
    N = len(V)
    weight = 0; edges = [];
    used = [False]*N; used[0] = True; n_used = 1;
    heap = [(c, 0, v) for v, c in E[0].items()]; heapify(heap)
    while heap and n_used < N:
        c, u, v = heappop(heap)
        if used[v]: continue
        used[v] = True; n_used += 1; edges.append((u, v))
        weight += c
        for w, d in E[v].items():
            if not used[w]: heappush(heap, (d, v, w))
    return edges, weight

N = int(input())
cities = [(a, b, i) for i, (a, b) in enumerate([tuple(map(int, input().split())) for _ in range(N)])]
sorted_x, sorted_y = sorted(cities, key=lambda x:x[0]), sorted(cities, key=lambda x:x[1])
E = {i: {} for i in range(N)}
for i in range(N-1):
    (a1, _, u), (a2, _, v) = sorted_x[i], sorted_x[i+1]
    E[u][v] = min(a2 - a1, E[u][v]) if E[u].get(v) is not None else a2 - a1
    E[v][u] = E[u][v]
    (_, b1, u), (_, b2, v) = sorted_y[i], sorted_y[i+1]
    E[u][v] = min(b2 - b1, E[u][v]) if E[u].get(v) is not None else b2 - b1
    E[v][u] = E[u][v]
V = list(range(N))
_, ans = prim(V, E)
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 for _ in range(size)]


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


    def unite(self, x, y):
        x = self.find(x)
        y = 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)
def compute_mst_kruskal(N, edges):
    edges = sorted(edges, key = lambda x:x[2])
    UF = UnionFind(N)
    cost = 0
    for edge in edges:
        x, y, w = edge
        if not UF.same(x, y):
            UF.unite(x, y)
            cost+=w
    return cost
N = int(input())
ixy = []
for i in range(N):
    x, y = map(int, input().split())
    ixy.append((i, x, y))
xy_x = sorted(ixy, key = lambda x:x[1])
xy_y = sorted(ixy, key = lambda x:x[2])
edges = []
for i in range(N-1):
    i1, x1, y1 = xy_x[i]
    i2, x2, y2 = xy_x[i+1]
    edges.append([i1, i2, x2-x1])
    i1, x1, y1 = xy_y[i]
    i2, x2, y2 = xy_y[i+1]
    edges.append([i1, i2, y2-y1])
ans = compute_mst_kruskal(N, edges)
print(ans)

Solution (Python):
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]


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


    def unite(self, x, y):
        x = self.find(x)
        y = 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)
def compute_mst_kruskal(N, edges):
    edges = sorted(edges, key = lambda x:x[2])
    UF = UnionFind(N)
    cost = 0
    for edge in edges:
        x, y, w = edge
        if not UF.same(x, y):
            UF.unite(x, y)
            cost+=w
    return cost
N = int(input())
ixy = []
for i in range(N):
    x, y = map(int, input().split())
    ixy.append((i, x, y))
xy_x = sorted(ixy, key = lambda x:x[1])
xy_y = sorted(ixy, key = lambda x:x[2])
edges = []
for i in range(N-1):
    i1, x1, y1 = xy_x[i]
    i2, x2, y2 = xy_x[i+1]
    edges.append((i1, i2, x2-x1))
    i1, x1, y1 = xy_y[i]
    i2, x2, y2 = xy_y[i+1]
    edges.append((i1, i2, y2-y1))
ans = compute_mst_kruskal(N, edges)
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 for _ in range(size)]


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


    def unite(self, x, y):
        x = self.find(x)
        y = 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)
def compute_mst_kruskal(N, edges):
    edges = sorted(edges, key = lambda x:x[2])
    UF = UnionFind(N)
    cost = 0
    for edge in edges:
        x, y, w = edge
        if not UF.same(x, y):
            UF.unite(x, y)
            cost+=w
    return cost
N = int(input())
ixy = []
for i in range(N):
    x, y = map(int, input().split())
    ixy.append((i, x, y))
xy_x = sorted(ixy, key = lambda x:x[1])
xy_y = sorted(ixy, key = lambda x:x[2])
edges = []
for i in range(N-1):
    i1, x1, y1 = xy_x[i]
    i2, x2, y2 = xy_x[i+1]
    edges.append((i1, i2, x2-x1))
    i1, x1, y1 = xy_y[i]
    i2, x2, y2 = xy_y[i+1]
    edges.append((i1, i2, y2-y1))
ans = compute_mst_kruskal(N, edges)
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 for _ in range(size)]


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


    def unite(self, x, y):
        x = self.find(x)
        y = 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)
def compute_mst_kruskal(N, edges):
    edges = sorted(edges, key = lambda x:x[2])
    UF = UnionFind(N)
    cost = 0
    for edge in edges:
        x, y, w = edge
        if not UF.same(x, y):
            UF.unite(x, y)
            cost+=w
    return cost
N = int(input())
ixy = []
for i in range(N):
    x, y = map(int, input().split())
    ixy.append((i, x, y))
xy_x = sorted(ixy, key = lambda x:x[1])
xy_y = sorted(ixy, key = lambda x:x[2])
edges = []
for i in range(N-1):
    i1, x1, y1 = xy_x[i]
    i2, x2, y2 = xy_x[i+1]
    edges.append((i1, i2, x2-x1))
    i1, x1, y1 = xy_y[i]
    i2, x2, y2 = xy_y[i+1]
    edges.append((i1, i2, y2-y1))
ans = compute_mst_kruskal(N, edges)
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
N=int(input())
P=[tuple(map(int,input().split())) for i in range(N)]
X=[(i,P[i][0]) for i in range(N)]
Y=[(i,P[i][1]) for i in range(N)]
X.sort(key=lambda x:x[1])
Y.sort(key=lambda x:x[1])
Z=[(X[i][0],X[i+1][0],X[i+1][1]-X[i][1]) for i in range(N-1)]+[(Y[i][0],Y[i+1][0],Y[i+1][1]-Y[i][1]) for i in range(N-1)]
Z.sort(key=lambda x:x[2])
root=[-1]*N
def search(i):
    global root
    if root[i]>=0:
        root[i]=search(root[i])
        return root[i]
    return i
ans=0
for i,j,k in Z:
    ri=search(i)
    rj=search(j)
    if ri==rj:
        continue
    elif root[ri]<=root[rj]:
        root[ri]+=root[rj]
        root[rj]=ri
        ans+=k
    else:
        root[rj]+=root[ri]
        root[ri]=rj
        ans+=k
print(ans)

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

Solution (Python):
class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[i for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)

N=int(input())
edge=[]
points=[]
for i in range(N):
    x,y=map(int,input().split())
    points.append((i,x,y))
points.sort(key=lambda x:x[1])
for i in range(N-1):
    i1,x1,y1=points[i]
    i2,x2,y2=points[i+1]
    wt=min(abs(x1-x2),abs(y1-y2))
    edge.append((wt,i1,i2))
points.sort(key=lambda x:x[2])
for i in range(N-1):
    i1,x1,y1=points[i]
    i2,x2,y2=points[i+1]
    wt=min(abs(x1-x2),abs(y1-y2))
    edge.append((wt,i1,i2))
edge.sort()
G=UnionFind(N)
ans=0
for e in edge:
    w,i,j=e
    if not(G.same(i,j)):
        G.unite(i,j)
        ans+=w
print(ans)

Solution (Python):
from heapq import heappush, heappop



N = int(input())
x, y = (
    zip(*(map(int, input().split()) for _ in range(N))) if N else
    ((), ())
)



ts = list(zip(range(1, N + 1), x, y))
ts_x = sorted(ts, key=lambda t: t[1])
ts_y = sorted(ts, key=lambda t: t[2])
G = [{} for _ in range(N + 1)]
for ((i, a, b), (j, c, d)) in zip(ts_x[1:], ts_x):
    G[i][j] = min(abs(c - a), abs(d - b))
    G[j][i] = G[i][j]
for ((i, a, b), (j, c, d)) in zip(ts_y[1:], ts_y):
    G[i][j] = min(abs(c - a), abs(d - b))
    G[j][i] = G[i][j]


def prim(G):
    used = [False for _ in range(len(G))]
    res = 0
    q = []
    used[1] = True
    for j, w in G[1].items():
        heappush(q, (w, j))
    while q:
        w, j = heappop(q)
        if not used[j]:
            used[j] = True
            res += w
            for j2, w2 in G[j].items():
                heappush(q, (w2, j2))
    return res


ans = prim(G)

print(ans)