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):
n=int(input())
hqx=[]
hqy=[]
for i in range(n):
    x,y=map(int,input().split())
    hqx.append((x,i))
    hqy.append((y,i))
hqx.sort()
hqy.sort()
prex,prexi=hqx[0]
prey,preyi=hqy[0]
edges=[]
for i in range(1,n):
    x,xi=hqx[i]
    y,yi=hqy[i]
    edges.append((x-prex,prexi,xi))
    edges.append((y-prey,preyi,yi))
    prex,prexi=x,xi
    prey,preyi=y,yi
edges.sort()

frag=list(range(n+1))
fragnum=[0]*(n+1)

def takefrag(p):
    stock=[]
    while frag[frag[p]]!=frag[p]:
        stock.append(p)
        p=frag[p]
    p=frag[p]
    for i in stock:
        frag[i]=p
    return p

count=0
ans=0
for i in range(2*n):
    cost,a,b=edges[i]
    f1,f2 = map(takefrag,(a,b))
    if f1!=f2:
        count+=1
        f1,f2 = min(f1,f2),max(f1,f2)
        frag[f1]=f2
        ans+=cost
    if count==n-1:
        break

print(ans)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = list(range(n))
        self.size = [1]*n
        self.cost = 0
        
    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 unit(self,x,y,dist):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.size[x] < self.size[y]:
            x,y = y,x
        self.size[x] += self.size[y]
        self.par[y] = x
        self.cost += dist
        
n,*xy = map(int,open(0).read().split())
x = [(x,i) for i,x in enumerate(xy[::2])]
y = [(y,i) for i,y in enumerate(xy[1::2])]

x.sort()
y.sort()

xdist = [(x2-x1, i1, i2) for (x1,i1),(x2,i2) in zip(x,x[1:])]
ydist = [(y2-y1, i1, i2) for (y1,i1),(y2,i2) in zip(y,y[1:])]

dist_list = sorted(xdist+ydist)

uf = UnionFind(n)
for dist,i1,i2 in  dist_list:
    uf.unit(i1,i2,dist)
print(uf.cost)

Solution (Python):
import sys
import copy
import heapq
from collections import deque
import decimal


INF = sys.maxsize



def main():
    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())
    tree = UnionFind(n)

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

    edges_x.sort()
    edges_y.sort()

    edges = []
    for i in range(n - 1):
        tmp = abs(edges_x[i][0] - edges_x[i + 1][0])
        edges.append((tmp, edges_x[i][1], edges_x[i + 1][1]))
        tmp = abs(edges_y[i][0] - edges_y[i + 1][0])
        edges.append((tmp, edges_y[i][1], edges_y[i + 1][1]))

    edges.sort()

    ans = 0
    for d, s, t in edges:
        if not tree.same(s, t):
            tree.union(s, t)
            ans += d

    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
h = [list(map(int, input().split())) for _ in range(N)]

x = [(val[0],i) for i,val in enumerate(h)]
y = [(val[1],i) for i,val in enumerate(h)]

x.sort()
y.sort()
edge = []
for i in range(1,N):
    
    edge.append((x[i][0]-x[i-1][0], x[i-1][1], x[i][1]))
    edge.append((y[i][0]-y[i-1][0], y[i-1][1], y[i][1]))
edge.sort()
par = list(range(N))
rank = [0]*N

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

def unite(val1, val2):
    val1 = find(val1)
    val2 = find(val2)
    if val1==val2:
        return
    if rank[val1] < rank[val2]:
        par[val1] = val2
    else:
        par[val2] = val1
        if rank[val1] == rank[val2]:
            rank[val1] += 1
def same(val1, val2):
    return find(val1)==find(val2)

res = 0
for e in edge:
    start = e[1]
    end = e[2]
    if same(start, end):
        continue
    res += e[0]
    unite(start, end)
print(res)

Solution (Python):
import heapq
N = int(input())
X = []
Y = []
for n in range(N):
    x, y = map(int,input().split())
    X.append((x, n))
    Y.append((y, n))
X.sort()
Y.sort()
adj = [ [] for v in range(N)]
for n in range(N-1):
    cost = X[n+1][0] - X[n][0]
    adj[X[n+1][1]].append((cost, X[n][1]))
    adj[X[n][1]].append((cost, X[n+1][1]))
    cost = Y[n+1][0] - Y[n][0]
    adj[Y[n+1][1]].append((cost, Y[n][1]))
    adj[Y[n][1]].append((cost, Y[n+1][1]))

visited = [0] * N
pq = []
for w, t in adj[0]:
    heapq.heappush(pq, (w, t))
visited[0] = 1

ans = 0
while(pq):
    w, t = heapq.heappop(pq)
    if visited[t]:
        continue
    visited[t] = 1
    ans += w
    for w, s in adj[t]:
        if visited[s]==0:
            heapq.heappush(pq, (w, s))
print (ans)

Solution (Python):

N = int(input())
city = []
for i in range(N):
    city_i = [i] + list(map(int,input().split()))
    city.append(city_i)


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

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




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)

par = [-1]*N

ans = 0
for e in edges:
    if same(e[1],e[2]):
        continue
    unite(e[1],e[2])
    ans += e[0]
print(ans)

Solution (Python):
N = int(input())
city = []
for i in range(N):
    city_i = [i] + list(map(int,input().split()))
    city.append(city_i)


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

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




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)

par = [-1]*N

ans = 0
for e in edges:
    if same(e[1],e[2]):
        continue
    unite(e[1],e[2])
    ans += e[0]
print(ans)

Solution (Python):
import sys
read=sys.stdin.readline
def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
        else:
            par[a]=b
            if rank[a]==rank[b]:
                rank[b]+=1
def same(a,b):
    return find(a)==find(b)
def Kruskal(Edge,E):
    cost=0
    Edge.sort(key=lambda x:x[2])
    for i in range(E):
        f,t,c=Edge[i]
        if(not same(f,t)):
            union(f,t)
            cost+=c
    return cost
    
N=int(input())
par=[];p=[];dic={};rank=[]
for i in range(N):
    par.append(i)
    rank.append(0)
    p.append(tuple(map(int,read().split())))
    dic[p[i]]=i
xp,yp=sorted(p,key=lambda x:x[0]),sorted(p,key=lambda x:x[1])
Edge=[]
for i in range(N):
    if(i>0):
        Edge.append((dic[xp[i]],dic[xp[i-1]],abs(xp[i][0]-xp[i-1][0])))
        Edge.append((dic[yp[i]],dic[yp[i-1]],abs(yp[i][1]-yp[i-1][1])))
    if(i<N-1):
        Edge.append((dic[xp[i]],dic[xp[i+1]],abs(xp[i][0]-xp[i+1][0])))
        Edge.append((dic[yp[i]],dic[yp[i+1]],abs(yp[i][1]-yp[i+1][1])))
print(Kruskal(Edge,len(Edge)))

Solution (Python):
import sys
read=sys.stdin.readline
def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
        else:
            par[a]=b
            if rank[a]==rank[b]:
                rank[b]+=1
def same(a,b):
    return find(a)==find(b)
def Kruskal(Edge,E):
    cost=0
    Edge.sort(key=lambda x:x[2])
    for i in range(E):
        f,t,c=Edge[i]
        if(not same(f,t)):
            union(f,t)
            cost+=c
    return cost

N=int(input())
par=[];p=[];dic={};rank=[]
for i in range(N):
    par.append(i)
    rank.append(0)
    p.append(tuple(map(int,read().split())))
    dic[p[i]]=i
xp=sorted(p,key=lambda x:x[0])
yp=sorted(p,key=lambda x:x[1])
Edge=[]
for i in range(N):
    if(i>0):
        Edge.append((dic[xp[i]],dic[xp[i-1]],abs(xp[i][0]-xp[i-1][0])))
    if(i<N-1):
        Edge.append((dic[xp[i]],dic[xp[i+1]],abs(xp[i][0]-xp[i+1][0])))
    if(i>0):
        Edge.append((dic[yp[i]],dic[yp[i-1]],abs(yp[i][1]-yp[i-1][1])))
    if(i<N-1):
        Edge.append((dic[yp[i]],dic[yp[i+1]],abs(yp[i][1]-yp[i+1][1])))
print(Kruskal(Edge,len(Edge)))

Solution (Python):
from collections import namedtuple


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

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

  def unite(self, a, b):
    a = self.find(a)
    b = self.find(b)  
    if self.size[a] < self.size[b]:
      a, b = b, a
    self.par[b] = a
    self.size[a] += self.size[b]

  def size_of(self, a):
    return self.size[self.find(a)]

  def find(self, a):
    if a == self.par[a]:
      return a
    self.par[a] = self.find(self.par[a])
    return self.par[a]

Edge = namedtuple('Edge', 'w s t')
X = namedtuple('X', 'x i')
Y = namedtuple('Y', 'y i')

N = int(input())

edges = []
xg = []
yg = []

for i in range(N):
  x, y = map(int, input().split())
  xg.append(X(x, i))
  yg.append(Y(y, i))

xg.sort()
yg.sort()

for i in range(N - 1):
  x1, a = xg[i]
  x2, b = xg[i + 1]
  edges.append(Edge(abs(x1 - x2), a, b))

for i in range(N - 1):
  y1, a = yg[i]
  y2, b = yg[i + 1]
  edges.append(Edge(abs(y1 - y2), a, b))

edges.sort()

u = UnionFind(N)
cost = 0

for w, s, t in edges:
  if u.is_same(s, t):
    continue
  u.unite(s, t)
  cost += w

print(cost)

Solution (Python):
import sys


class UnionFind:
    def __init__(self, n):
        
        self.n = n
        
        self._root_table = list(range(n))
        
        self._size_table = [1] * n

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

    def size(self, x):
        return self._size_table[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._root_table) if x == i]

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


input = sys.stdin.readline


def main():
    N = int(input())
    cities, xs, ys = [], [], []
    for i in range(N):
        x, y = map(int, input().split())
        cities.append((x, y))
        xs.append((x, i))
        ys.append((y, i))
    xs.sort()
    ys.sort()
    xd, yd = [], []
    for i in range(1, N):
        x1, c1 = xs[i - 1]
        x2, c2 = xs[i]
        if x2 - x1 <= abs(cities[c1][1] - cities[c2][1]):
            xd.append((x2 - x1, c1, c2))
        y1, c1 = ys[i - 1]
        y2, c2 = ys[i]
        if y2 - y1 < abs(cities[c1][0] - cities[c2][0]):
            xd.append((y2 - y1, c1, c2))
    xd.sort()

    uf = UnionFind(N)
    cost = 0
    merged_cnt = 0
    for d1, c1, c2 in xd:
        if not uf.same(c1, c2):
            uf.union(c1, c2)
            cost += d1
            merged_cnt += 1
            if merged_cnt == N - 1:
                break
    print(cost)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


class UnionFind:
    def __init__(self, n):
        
        self.n = n
        
        self._root_table = list(range(n))
        
        self._size_table = [1] * n

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

    def size(self, x):
        return self._size_table[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._root_table) if x == i]

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


input = sys.stdin.readline


def main():
    N = int(input())
    cities, xs, ys = [], [], []
    for i in range(N):
        x, y = map(int, input().split())
        cities.append((x, y))
        xs.append((x, i))
        ys.append((y, i))
    xs.sort()
    ys.sort()
    xd, yd = [], []
    for i in range(1, N):
        x1, c1 = xs[i - 1]
        x2, c2 = xs[i]
        if x2 - x1 <= abs(cities[c1][1] - cities[c2][1]):
            xd.append((x2 - x1, c1, c2))
        y1, c1 = ys[i - 1]
        y2, c2 = ys[i]
        if y2 - y1 < abs(cities[c1][0] - cities[c2][0]):
            xd.append((y2 - y1, c1, c2))
    xd.sort()

    uf = UnionFind(N)
    cost = 0
    merged_cnt = 0
    for d1, c1, c2 in xd:
        if not uf.same(c1, c2):
            uf.union(c1, c2)
            cost += d1
            merged_cnt += 1
            if merged_cnt == N - 1:
                break
    print(cost)


if __name__ == "__main__":
    main()

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)

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()
Distance = []
for i in range(N-1):
    Distance.append((X[i+1][0] - X[i][0], X[i][1], X[i+1][1]))
    Distance.append((Y[i+1][0] - Y[i][0], Y[i][1], Y[i+1][1]))
Distance.sort()
UFT = UnionFind(N)
ans = 0
for i in range(2*(N-1)):
    d, p, q = Distance[i]
    if not UFT.same(p, q):
        UFT.union(p, q)
        ans += d
    if UFT.size(0) == N:
        break
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline


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

    
    def root(self, x):
        visited_nodes = []
        while True:
            p = self.parent[x]
            if p == x:
                
                for node in visited_nodes:
                    self.parent[node] = x
                return x
            else:
                visited_nodes.append(x)
                x = p

    
    def unite(self, x, y):
        if not self.root(x) == self.root(y):
            if self.rank[x] > self.rank[y]:
                self.parent[self.root(y)] = self.root(x)
            else:
                self.parent[self.root(x)] = self.root(y)
                if self.rank[x] == self.rank[y]:
                    self.rank[self.root(y)] += 1

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

    
    def printDebugInfo(self):
        print([self.root(i) for i in range(self.N)])






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

omega = []
for i in range(N-1):
    omega.append((X[i+1][0] - X[i][0], X[i][1], X[i+1][1], 0))
    omega.append((Y[i+1][0] - Y[i][0], Y[i][1], Y[i+1][1], 1))
omega.sort()
tree = UnionFind(N)
weight = 0
counter = N
i = 0
while True:
    
    minimum_edge = omega[i]
    a = minimum_edge[1]
    b = minimum_edge[2]
    kind = minimum_edge[3]
    cost = minimum_edge[0]
    if counter == 1:
        break
    i += 1
    if tree.ifSame(a, b):
        continue
    else:
        tree.unite(a, b)
        weight += cost
        counter -= 1
print(weight)

Solution (Python):
def main():  
  import sys
  input = sys.stdin.readline
  import heapq
  def prim_heap():
      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

  from collections import deque
  n = int(input())
  st = deque([])

  edge = deque([[] for i in range(n)])
  for i in range(n):
      x,y = map(int,input().split())
      st_append = st.append
      st_append((i,x,y))

  from operator import itemgetter
  bb = tuple(sorted(st,key=itemgetter(1)))
  chk = tuple(sorted(st,key=itemgetter(2)))
  

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

  for i in range(n-1):
    a = chk[i][0]
    b = chk[i+1][0]
    c = chk[i+1][2]-chk[i][2]
    edge[a].append((c,b))
    edge[b].append((c,a))

  edge = tuple(edge)
  print(prim_heap())
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
import heapq
def prim_heap():
    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

from collections import deque
n = int(input())
st = deque([])

edge = deque([[] for i in range(n)])
for i in range(n):
    x,y = map(int,input().split())
    st_append = st.append
    st_append((i,x,y))
    
from operator import itemgetter
bb = tuple(sorted(st,key=itemgetter(1)))
chk = tuple(sorted(st,key=itemgetter(2)))


for i in range(n-1):
  x = bb[i][0]
  y = bb[i+1][0]
  z = bb[i+1][1]-bb[i][1]
  edge[x].append((z,y))
  edge[y].append((z,x))
  
for i in range(n-1):
  a = chk[i][0]
  b = chk[i+1][0]
  c = chk[i+1][2]-chk[i][2]
  edge[a].append((c,b))
  edge[b].append((c,a))
  
edge = tuple(edge)
print(prim_heap())

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]




class UnionFind:
    def __init__(self, n):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.find(self.d[x])
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True
    
    def same(self, x, y):
        if self.find(x)==self.find(y):
            return True
        return False
    
    def size(self, x):
        return (-1) * self.d[self.find(x)]

N = ii()

l_x = []
l_y = []
for i in range(N):
    x, y = mi()
    l_x.append([i, x])
    l_y.append([i, y])
l_x.sort(key=lambda x:x[1])
l_y.sort(key=lambda x:x[1])

path = []
for i in range(N-1):
    path.append([l_x[i][0], l_x[i+1][0], l_x[i+1][1]-l_x[i][1]])
    path.append([l_y[i][0], l_y[i+1][0], l_y[i+1][1]-l_y[i][1]])
path.sort(key=lambda x:x[2])

T = UnionFind(N)
cnt = 0
for i in range(2*N-2):
    s, t, d = path[i][0], path[i][1], path[i][2]
    if not T.same(s, t):
        T.unite(s, t)
        cnt += d

print(cnt)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]




class UnionFind:
    def __init__(self, n):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.find(self.d[x])
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True
    
    def same(self, x, y):
        if self.find(x)==self.find(y):
            return True
        return False
    
    def size(self, x):
        return (-1) * self.d[self.find(x)]

N = ii()

l_x = []
l_y = []
for i in range(N):
    x, y = mi()
    l_x.append([i, x])
    l_y.append([i, y])
l_x.sort(key=lambda x:x[1])
l_y.sort(key=lambda x:x[1])

path = []
for i in range(N-1):
    path.append([l_x[i][0], l_x[i+1][0], l_x[i+1][1]-l_x[i][1]])
    path.append([l_y[i][0], l_y[i+1][0], l_y[i+1][1]-l_y[i][1]])
path.sort(key=lambda x:x[2])

T = UnionFind(N)
cnt = 0
for i in range(2*N-2):
    s, t, d = path[i][0], path[i][1], path[i][2]
    if not T.same(s, t):
        T.unite(s, t)
        cnt += d

print(cnt)

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

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


def main():
    N = int(input())
    X = []
    Y = []
    for i, _ in enumerate(range(N)):
        x, y = map(int, input().split())
        X.append((x, i))
        Y.append((y, i))
    X.sort()
    Y.sort()
    hq = []
    for i in range(N-1):
        x1, x1_ind = X[i]
        x2, x2_ind = X[i+1]
        y1, y1_ind = Y[i]
        y2, y2_ind = Y[i+1]
        heappush(hq, (x2-x1, x1_ind, x2_ind))
        heappush(hq, (y2-y1, y1_ind, y2_ind))
    ans = 0
    union_find = UnionFind(N)
    while hq:
        w, s, t = heappop(hq)
        if not union_find.is_same(s, t):
            union_find.union(s, t)
            ans += w

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from heapq import heappop, heappush
def prim(G):
    used = [False] * len(G) 
    hq = [(0, 0)]
    res = 0
    while hq:
        w, v = heappop(hq)
        if used[v]:
            continue
        used[v] = True
        res += w
        for cv, cw in G[v]:
            if used[cv]:
                continue
            heappush(hq, (cw, cv))
    return res

def main():
    N = int(input())
    X = []
    Y = []
    for i, _ in enumerate(range(N)):
        x, y = map(int, input().split())
        X.append((x, i))
        Y.append((y, i))
    X.sort()
    Y.sort()
    graph = [[] for _ in range(N)]
    prev_x, prev_x_ind = X[0]
    prev_y, prev_y_ind = Y[0]
    for i in range(1, N):
        x, x_ind = X[i]
        y, y_ind = Y[i]
        graph[prev_x_ind].append((x_ind, x - prev_x))
        graph[x_ind].append((prev_x_ind, x - prev_x))
        graph[prev_y_ind].append((y_ind, y - prev_y))
        graph[y_ind].append((prev_y_ind, y - prev_y))
        prev_x, prev_x_ind = x, x_ind
        prev_y, prev_y_ind = y, y_ind
    print(prim(graph))

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

class Kruskal_UnionFind():
    
    def __init__(self, N):
        self.edges = []
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

    def add(self, u, v, d):
        """
        u = from, v = to, d = cost
        """
        self.edges.append([u, v, d])

    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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        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 size(self, x):
        x = self.find(x)
        return self.counter[x]

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

    def Kruskal(self):
        """
        return: 最小全域木のコストの和
        """
        edges = sorted(self.edges, key=lambda x: x[2])  
        res = 0
        for e in edges:
            if not self.same(e[0], e[1]):
                self.unite(e[0], e[1])
                res += e[2]
        return res

n = int(input())
xy = mylistinput(n)

G = Kruskal_UnionFind(n)

xy0 = []
for i in range(n):
    x = xy[i][0]
    y = xy[i][1]
    xy0.append([i,x,y])

xy1 = mysort(xy0,1)
for i in range(n-1):
    No1 = xy1[i][0]
    a = xy1[i][1]
    b = xy1[i][2]
    No2 = xy1[i+1][0]
    c = xy1[i+1][1]
    d = xy1[i+1][2]
    cost = min(abs(c-a),abs(d-b))
    G.add(No1,No2,cost)

xy2 = mysort(xy0,2)
for i in range(n-1):
    No1 = xy2[i][0]
    a = xy2[i][1]
    b = xy2[i][2]
    No2 = xy2[i+1][0]
    c = xy2[i+1][1]
    d = xy2[i+1][2]
    cost = min(abs(c-a),abs(d-b))
    G.add(No1,No2,cost)

ans = G.Kruskal()
print(ans)