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
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    def __init__(self, size):
        """
        size:頂点の数
        parent[x]->parent of x
        rank[x] -> height of tree of x
        """
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]

    def find(self, x):
        """
        xのrootを返す
        """
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        """
        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):
        """
        xとyが同じグループならTrue
        """
        return self.find(x) == self.find(y)

    def component(self):
        """
        各連結成分のrootの集合を返す
        len()をとれば連結成分の数が求められる
        return-> set()
        """
        comp = set()
        for i in self.parent:
            p = self.find(i)
            comp.add(p)
        return comp

    def componentNum(self):
        """
        連結成分の数を返す
        """
        return len(self.component())

    def __str__(self):
        """
        for debug
        クラスのlistの情報を出力
        """
        ret = "parents\n"
        ret += " ".join(map(str, self.parent))
        ret += '\n'
        ret += " ".join(map(str, self.rank))
        return ret


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

X = sorted(X, key=lambda x: x[1])
Y = sorted(Y, key=lambda x: x[1])

for p1, p2 in zip(X, X[1:]):
    i1, x1 = p1
    i2, x2 = p2
    cand.append([i1, i2, x2-x1])

for p1, p2 in zip(Y, Y[1:]):
    i1, y1 = p1
    i2, y2 = p2
    cand.append([i1, i2, y2-y1])

Un = UnionFind(N)
ans = 0

cand = sorted(cand, key=lambda x: x[2])
for s, g, w in cand:
    if Un.same(s, g):
        continue
    else:
        Un.union(s, g)
        ans += w
print(ans)

Solution (Python):
def main():
    n = int(input())
    city = []
    for i in range(n):
        x,y = map(int, input().split())
        city.append((x,y,i))
    edges = []
    
    city.sort()
    for i in range(n-1):
        dist = city[i+1][0] - city[i][0]
        edges.append((dist, city[i][2], city[i+1][2]))
    
    city.sort(key=lambda x:x[1])
    for i in range(n-1):
        dist = city[i+1][1] - city[i][1]
        edges.append((dist, city[i][2], city[i+1][2]))

    edges.sort()
    ans = 0

    uf = [-1]*n
    def root(x):
        if uf[x] < 0:
            return x
        uf[x] = root(uf[x])
        return uf[x]
    def unite(x,y):
        rx, ry = root(x), root(y)
        if rx == ry:
            return False
        if rx > ry:
            rx,ry = ry,rx
        uf[rx] += uf[ry]
        uf[ry] = rx
        return True

    for dist, from_, to in edges:
        if unite(from_, to):
            ans += dist
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
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


n = int(input())


edge = [[] for i in range(n)]
p=[]
edge=[[] for i in range(n)]
for i in range(n):
    p.append(tuple(map(int,input().split()))+tuple([i]))
x_sorted=sorted(p,key=lambda x:x[0])
y_sorted=sorted(p,key=lambda x:x[1])
for i in range(n-1):
    edge[x_sorted[i][2]].append((x_sorted[i+1][0]-x_sorted[i][0],x_sorted[i+1][2]))
    edge[x_sorted[i+1][2]].append((x_sorted[i+1][0]-x_sorted[i][0],x_sorted[i][2]))
    edge[y_sorted[i][2]].append((y_sorted[i+1][1]-y_sorted[i][1],y_sorted[i+1][2]))
    edge[y_sorted[i+1][2]].append((y_sorted[i+1][1]-y_sorted[i][1],y_sorted[i][2]))

print(prim_heap())

Solution (Python):
from heapq import heappush,heappop
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()
inf=float("inf")
G=[[]*N for i in range(N)]
for i in range(N-1):
  G[X[i][1]].append((X[i+1][0]-X[i][0],X[i+1][1]))
  G[X[i+1][1]].append((X[i+1][0]-X[i][0],X[i][1]))
  G[Y[i][1]].append((Y[i+1][0]-Y[i][0],Y[i+1][1]))
  G[Y[i+1][1]].append((Y[i+1][0]-Y[i][0],Y[i][1]))
  
Q=[(0,0)]
ans=0
visited=[False]*N
while Q:
  c,n=heappop(Q)
  if visited[n]:
    continue
  visited[n]=True
  ans+=c
  for c2,n2 in G[n]:
    if visited[n2]:
      continue
    else:
      heappush(Q,(c2,n2))

print(ans)

Solution (Python):

import heapq
n=int(input())
p=[]
d=[[] for i in range(n)]
for i in range(n):
    p.append(tuple(map(int,input().split()))+tuple([i]))
x_sorted=sorted(p,key=lambda x:x[0])
y_sorted=sorted(p,key=lambda x:x[1])
for i in range(n-1):
    d[x_sorted[i][2]].append((x_sorted[i+1][0]-x_sorted[i][0],x_sorted[i+1][2]))
    d[x_sorted[i+1][2]].append((x_sorted[i+1][0]-x_sorted[i][0],x_sorted[i][2]))
    d[y_sorted[i][2]].append((y_sorted[i+1][1]-y_sorted[i][1],y_sorted[i+1][2]))
    d[y_sorted[i+1][2]].append((y_sorted[i+1][1]-y_sorted[i][1],y_sorted[i][2]))
h=[]
for q in d[0]:
    heapq.heappush(h,q)
used=[False for i in range(n)]
used[0]=True
cost=0
while len(h):
    q=heapq.heappop(h)
    if used[q[1]]:
        continue
    used[q[1]]=True
    cost+=q[0]
    for r in d[q[1]]:
        heapq.heappush(h,r)
print(cost)

Solution (Python):
def inpl(): return [int(i) for i in input().split()]
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
            if self.par[rx] > self.par[ry]:
                self.par[rx] = ry
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
        return

N = int(input())
V = [0 for _ in range(N)]
Edge = []
for i in range(N):
    x, y = inpl()
    V[i] = (x, y, i)
V = sorted(V, key = lambda x: x[0])
for i in range(N-1):
    Edge.append((V[i+1][0]-V[i][0],V[i+1][2],V[i][2]))
V = sorted(V, key = lambda x: x[1])
for i in range(N-1):
    Edge.append((V[i+1][1]-V[i][1],V[i+1][2],V[i][2]))

Edge = sorted(Edge, key = lambda x: -x[0])
U = UnionFind(N)
ctr = 0
ans = 0
while ctr != N-1:
    c,i,j = Edge.pop()
    if U.find(i) != U.find(j):
        U.union(i,j)
        ans += c
        ctr += 1
print(ans)

Solution (Python):

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

ax.sort()
ay.sort()

edge = []
for i in range(n-1):
    v = ax[i][1]
    u = ax[i+1][1]
    c = abs(ax[i][0]-ax[i+1][0])
    edge.append((c,v,u))

    v = ay[i][1]
    u = ay[i+1][1]
    c = abs(ay[i][0]-ay[i+1][0])
    edge.append((c,v,u))

edge.sort()



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

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

t = UnionFind(n)
res = 0
for e in edge:
    cost = e[0]
    v = e[1]
    u = e[2]

    if not t.same(v,u):
        
        t.unite(v,u)
        res += cost

print(res)

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

n = int(input())
x_loc, y_loc = [], []
for i in range(n):
    x, y = map(int, input().split())
    x_loc.append((x, i))
    y_loc.append((y, i))
x_loc.sort()
y_loc.sort()
links = [set() for _ in range(n)]
for (x1, i1), (x2, i2) in zip(x_loc, x_loc[1:]):
    dist = x2 - x1
    links[i1].add((dist, i2))
    links[i2].add((dist, i1))
for (y1, i1), (y2, i2) in zip(y_loc, y_loc[1:]):
    dist = y2 - y1
    links[i1].add((dist, i2))
    links[i2].add((dist, i1))


visited = {0}
queue = list(links[0])
heapify(queue)
total = 0
while True:
    cost, i = heappop(queue)
    if i in visited:
        continue
    visited.add(i)
    total += cost
    if len(visited) == n:
        break
    for cost2, j in links[i]:
        if j in visited:
            continue
        heappush(queue, (cost2, j))
print(total)

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1 << 30)

class union_find:
  def __init__(self, n): self.par = [-1] * n; self.rank = [0] * n
  def __repr__(self): return "union_find({0})".format([self.root(i) for i in range(n)])
  def unite(self, x, y):
    x = self.root(x); y = self.root(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
  def root(self, x):
    if self.par[x] == -1: return x
    else: self.par[x] = self.root(self.par[x]); return self.par[x]
  def same(self, x, y): return self.root(x) == self.root(y)

N = read()
ps = []
for i in range(N):
  x, y = reads()
  ps.append((i, x, y))

edges = []

for q in range(1, 3):
  ps.sort(key=lambda p: p[q])
  for i in range(N-1):
    edges.append((ps[i+1][q] - ps[i][q], ps[i][0], ps[i+1][0]))

edges.sort()

uf = union_find(N)
ans = 0
for c, i, j in edges:
  if not uf.same(i, j):
    ans += c
    uf.unite(i, j)
print(ans)

Solution (Python):
import heapq
import sys
sys.setrecursionlimit(10 ** 7)

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]
		self.count = 0






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

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1

			self.count += 1
			return True
		return False

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

vx = sorted(x, key=lambda x: x[1])
vy = sorted(y, key=lambda x: x[1])

edges = []
uf = UnionFind(n)

for i in range(n - 1):
	if vx[i][1] == vx[i + 1][1]:
		uf.union(vx[i][0], vx[i + 1][0])
	else:
		heapq.heappush(edges, (vx[i + 1][1] - vx[i][1], vx[i][0], vx[i + 1][0]))

	if vy[i][1] == vy[i + 1][1]:
		uf.union(vy[i][0], vy[i + 1][0])
	else:
		heapq.heappush(edges, (vy[i + 1][1] - vy[i][1], vy[i][0], vy[i + 1][0]))





ans = 0

while edges != []:
	e = heapq.heappop(edges)
	if uf.union(e[1], e[2]):
		ans += e[0]
	if uf.count == n - 1:
		break

print(ans)

Solution (Python):
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
a = sorted(a)
gra = []
for i in range(n):
  a[i].append(i)
for i in range(n-1):
  gra.append([a[i][2],a[i+1][2],a[i+1][0]-a[i][0]])
a = sorted(a,key= lambda x:x[1])
for i in range(n-1):
  gra.append([a[i][2],a[i+1][2],a[i+1][1]-a[i][1]])
union = [0] *  n
uc = 0
ans = 0
gra = sorted(gra, key = lambda x: x[2])
class UnionFind():
    
    
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]

    
    def find(self,x):
        while self.table[x] >= 0:
            
            x = self.table[x]
        return x

    
    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                
                
                self.table[s1] += -1
                self.table[s2] = s1
        return
uni = UnionFind(n)
for i in range(len(gra)):
  hen = gra[i]
  if (uni.find(hen[0]) != uni.find(hen[1])):
    ans += hen[2]
    uni.union(hen[0],hen[1])
    uc += 1
  if uc == n-1:
    break
print(ans)

Solution (Python):

import sys

def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


class UnionFind:
    def __init__(self, N):
        
        self.N = N
        self.parent = list(range(N))  

    def root(self, x):
        
        path_to_root = []
        while self.parent[x] != x:
            path_to_root.append(x)
            x = self.parent[x]
        for node in path_to_root:
            self.parent[node] = x  
        return x

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

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

    def __str__(self):
        
        groups = {}  
        for x in range(self.N):
            root = self.root(x)
            if root in groups.keys():
                groups[root].append(x)
            else:
                groups[root] = [x]
        result = ""
        for root in groups.keys():
            result += str(groups[root]) + "\n"
        return result


def kruskal(num_vertices, edges):
    
    """Kruscal法: 最小全域木を求める
    edgesについて破壊的なことに注意
    """
    total_weight = 0
    edges.sort(key=lambda e: e[2])
    u = UnionFind(num_vertices)
    for e in edges:
        x = e[0]
        y = e[1]
        weight = e[2]
        if u.same(x, y):
            continue
        u.unite(x, y)
        total_weight += weight
    return total_weight


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

edges = []
sorted_x = sorted(l, key=lambda c: c[1])
sorted_y = sorted(l, key=lambda c: c[2])

for e in range(N-1):
    i0, x0, y0 = sorted_x[e]
    i1, x1, y1 = sorted_x[e+1]
    edges.append((i0, i1, x1-x0))

    i0, x0, y0 = sorted_y[e]
    i1, x1, y1 = sorted_y[e+1]
    edges.append((i0, i1, y1-y0))

print(kruskal(N, edges))

Solution (Python):
import numpy as np

def ii():
    return int(input())


def lii():
    return list(map(int, input().split(' ')))


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


def next_pair(lst):
    n = len(lst)
    for i in range(n-1):
        yield lst[i], lst[i+1]


class UnionFind(object):

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

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

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

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

        self.par[x] = y


class UnionFindRank(UnionFind):

    def __init__(self, n):
        UnionFind.__init__(self, n)

        self.rank = [0 for _ in range(n)]

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

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.rank[x] += 1
        else:
            self.par[y] = x
            self.rank[y] += 1


class UnionFindRankCount(UnionFind):

    def __init__(self, n):
        UnionFind.__init__(self, n)

        self.rank = [0 for _ in range(n)]
        self.count = [1 for _ in range(n)]

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

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.count[y] += self.count[x]
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def kruskal(n, edges):
    """
    :param n: int node数
    :param edges: list(tuple(int)) edge
        ex.) edges = [(0, 1, 10), (1, 0, 50), (2, 0, 30)]  (from, to, weight)
    :return: 最小全域木に含まれるエッジ（edgesの部分集合）
    """
    edges = sorted(edges, key=lambda x: x[2])
    u = UnionFindRankCount(n)

    k = []
    cnt = 0
    for e in edges:
        i, j, w = e
        if not u.same(i, j):
            u.union(i, j)
            k.append(e)
            cnt += 1

        if cnt == n-1: break

    return k



def main():
    N = ii()
    coord = []
    for n in range(N):
        x, y = lii()
        coord.append((x, y, n))

    c_sortx = sorted(coord, key=lambda x: x[0])
    c_sorty = sorted(coord, key=lambda x: x[1])

    edges = []
    for p1, p2 in next_pair(c_sortx):
        w = min(abs(p1[0] - p2[0]), abs(p1[1] - p2[1]))
        edges.append([p1[2], p2[2], w])

    for p1, p2 in next_pair(c_sorty):
        w = min(abs(p1[0] - p2[0]), abs(p1[1] - p2[1]))
        edges.append([p1[2], p2[2], w])

    min_tree = kruskal(N, edges)
    return sum(map(lambda x: x[2], min_tree))


if __name__ == '__main__':
    print(main())

Solution (Python):
from collections import defaultdict

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

N = int(input())
xd = defaultdict(lambda: [])
yd = defaultdict(lambda: [])
for i in range(N):
    x,y = map(int,input().split())
    xd[x].append(i)
    yd[y].append(i)

uf = UnionFind(N)
es = []
pre_x = pre_i = None
for x,idxs in sorted(xd.items()):
    if len(idxs) >= 2:
        for i1,i2 in zip(idxs,idxs[1:]):
            if uf.is_same(i1,i2): continue
            uf.unite(i1,i2)
    if pre_x is not None:
        dx = x - pre_x
        es.append((dx,pre_i,idxs[0]))
    pre_x = x
    pre_i = idxs[0]
pre_y = pre_i = None
for y,idxs in sorted(yd.items()):
    if len(idxs) >= 2:
        for i1,i2 in zip(idxs,idxs[1:]):
            if uf.is_same(i1,i2): continue
            uf.unite(i1,i2)
    if pre_y is not None:
        dy = y - pre_y
        es.append((dy,pre_i,idxs[0]))
    pre_y = y
    pre_i = idxs[0]

if uf.count == N-1:
    print(0)
    exit()
ans = 0
for cost,a,b in sorted(es):
    if uf.is_same(a,b): continue
    uf.unite(a,b)
    ans += cost
    if uf.count == N-1:
        break
print(ans)

Solution (Python):

from heapq import heappop, heappush
def inpl(): return map(int, input().split())
N = int(input())

X = []
Y = []

for i in range(N):
    x, y = inpl()
    X.append((i, x))
    Y.append((i, y))

X = sorted(X, key=lambda x: x[1])
Y = sorted(Y, key=lambda y: y[1])

G = [[] for _ in range(N)]
for i in range(N-1):
    Xa, Xb = X[i], X[i+1]
    Ya, Yb = Y[i], Y[i+1]
    G[Xa[0]].append([Xb[0], Xb[1]-Xa[1]])
    G[Xb[0]].append([Xa[0], Xb[1]-Xa[1]])
    
    G[Ya[0]].append([Yb[0], Yb[1]-Ya[1]])
    G[Yb[0]].append([Ya[0], Yb[1]-Ya[1]])

visited = [False]*N
Q = [(0, 0)]
ans = 0

while Q:
    c, n = heappop(Q)
    if visited[n]:
        continue
    visited[n] = True
    ans += c
    
    for m, d in G[n]:
        if visited[m]:
            continue
        else:
            heappush(Q, (d, m))

print(ans)

Solution (Python):
class UnionFind(object):
  def __init__(self,n):
    self.table=[-1]*n
 
  def find(self,x):
    parent=self.table[x]
    if parent<0:
      return x
    else:
      root=self.find(parent)
      self.table[x]=root
      return root
 
  def union(self,a,b):
    root1=self.find(a)
    root2=self.find(b)
    if root1 != root2:
      if self.table[root1] != self.table[root2]:
        if self.table[root1] < self.table[root2]:
          self.table[root2]=root1
        else:
          self.table[root1]=root2
      else:
        self.table[root1]+=(-1)
        self.table[root2]=root1

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

x=sorted(x,key=lambda x:x[1])
y=sorted(y,key=lambda y:y[1])

for i in range(N-1):
  a,b=x[i]
  c,d=y[i]
  e,f=x[i+1]
  g,h=y[i+1]
  M.append((f-b,a,e))
  M.append((h-d,c,g))
  
uf=UnionFind(N)
ans=0

for v,s,t in sorted(M,key=lambda x:x[0]):
  if uf.find(s)!=uf.find(t):
    uf.union(s,t)
    ans+=v

print(ans)

Solution (Python):
n = int(input())
xs = []
ys = []

for i in range(n):
    x, y = map(int, input().split())
    xs.append((x, i))
    ys.append((y, i))


xs.sort()
ys.sort()

es = []

for i in range(n-1):
    es.append((xs[i+1][0] - xs[i][0], xs[i][1], xs[i+1][1]))
    es.append((ys[i+1][0] - ys[i][0], ys[i][1], ys[i+1][1]))

es.sort()

class UF:
    def __init__(self):
        self.p = {}
    def find(self, x):
        if x not in self.p:
            self.p[x] = x
        if x == self.p[x]:
            return x
        self.p[x] = self.find(self.p[x])
        return self.p[x]
    def merge(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.p[x] = y


uf = UF()
ans = 0
try:
    for d, i0, i1 in es:
        c0 = uf.find(i0)
        c1 = uf.find(i1)
        if c0 == c1:
            continue
        ans += d
        uf.merge(i0, i1)
    print(ans)
except:
    print(0)

Solution (Python):




N = int(input())

Xs = []
Ys = []

V = [] 

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

Xs.sort()
Ys.sort()


Xedges = []
Yedges = []
for i in range(N-1):
    Xedges.append((Xs[i+1][0]-Xs[i][0],Xs[i][1],Xs[i+1][1]))
    Yedges.append((Ys[i+1][0]-Ys[i][0],Ys[i][1],Ys[i+1][1]))
Xedges.extend(Yedges)
Xedges.sort()





class UnionFind:
    def __init__(self, size):
        
        
        self.table = [-1 for _ in range(size)]

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

    
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    
    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

uf = UnionFind(N)



i = 0
while len(V) != N-1:
    v, x1, x2 = Xedges[i]
    if uf.find(x1) != uf.find(x2):
        uf.union(x1, x2)
        V.append(v)
        
    i += 1

print(sum(V))

Solution (Python):

def inpl(): return tuple(map(int, input().split()))

n = int(input())
X = []
Y = []
for i in range(n):
    x, y = inpl()
    X.append((x, i))
    Y.append((y, i))

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

G = [[] for _ in range(n)]
edges = []
for i in range(n-1):
    edges.append((X[i][1], X[i+1][1], abs(X[i][0] - X[i+1][0])))
    edges.append((Y[i][1], Y[i+1][1], abs(Y[i][0] - Y[i+1][0])))

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

tree = [[-1, 1] for _ in range(n)]

def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0])    
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: 
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px

res = 0

for s, t, w in edges:
    if find(s) != find(t):
        unite(s, t)
        res += w
print(res)

Solution (Python):
class UnionFind(object):

    def __init__(self, n):
        self.n = n
        self.par = list(range(n))
        self.rank = [1] * n

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

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

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


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 = sorted(X)
Y = sorted(Y)
graph = []
for i in range(N - 1):
    graph.append((X[i + 1][0] - X[i][0], X[i][1], X[i + 1][1]))
    graph.append((Y[i + 1][0] - Y[i][0], Y[i][1], Y[i + 1][1]))

graph.sort()
uf = UnionFind(N)

total_cost = 0
for cost, a, b in graph:
    if not uf.is_same(a, b):
        uf.unite(a, b)
        total_cost += cost

print(total_cost)

Solution (Python):
N = int(input())


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 = self.find(x)
    yr = 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


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

def convert_to_dists(L):
  it = iter(L)
  it2 = iter(L)
  next(it2)

  D = []

  for a,b in zip(it, it2):
    ax, ai = a
    bx, bi = b
    d = abs(ax-bx)
    D.append((d,ai,bi))
  return D

dX = convert_to_dists(X)
dY = convert_to_dists(Y)

D = dX+dY
D.sort()

cost = 0
S = DisjointSet(N)
edge_count = 1

for d,i,j in D:
  if S.find(i) != S.find(j):
    S.union(i,j)
    cost += d
    edge_count += 1
    if edge_count >= N:
      break

print(cost)

Solution (Python):
class Edge:
    def __init__(self, u, v, cost):
        self.u = u
        self.v = v
        self.cost = cost
        


class Coordinate:
    def __init__(self, x, y, n):
        self.x = x
        self.y = y
        self.n = n

    def __repr__(self):
        return repr((self.x, self.y))



def init(_n):
    for i in range(0, _n):
        par[i] = i
        rank[i] = 0



def find(_x):
    if par[_x] == _x:
        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

    if rank[_x] < rank[_y]:
        par[_x] = _y
    else:
        par[_y] = _x
        if rank[_x] == rank[_y]:
            rank[_x] += 1



def same(_x, _y):
    return find(_x) == find(_y)


def comp(edge1, edge2):
    return edge1.cost < edge2.cost


def kruskal():
    sorted_edges = sorted(Edges, key=lambda edges: edges.cost)
    init(V)
    res = 0
    
    

    for i in range(0, E):
        tmp_edge = sorted_edges[i]
        if not same(tmp_edge.u, tmp_edge.v):
            unite(tmp_edge.u, tmp_edge.v)
            
            res += tmp_edge.cost

    return res


if __name__ == '__main__':
    N = int(input())
    x = []
    y = []
    Coordinates = []
    for i in range(0, N):
        tmp_x, tmp_y = list(map(int, input().split()))
        
        
        Coordinates.append(Coordinate(tmp_x, tmp_y, i))

    sorted_by_x = sorted(Coordinates, key=lambda coordinate: coordinate.x)
    sorted_by_y = sorted(Coordinates, key=lambda coordinate: coordinate.y)

    Edges = []
    for i in range(0, N - 1):
        cost_x = min(abs(sorted_by_x[i].x - sorted_by_x[i + 1].x), abs(sorted_by_x[i].y - sorted_by_x[i + 1].y))
        Edges.append(Edge(sorted_by_x[i].n, sorted_by_x[i + 1].n, cost_x))
        
        cost_y = min(abs(sorted_by_y[i].x - sorted_by_y[i + 1].x), abs(sorted_by_y[i].y - sorted_by_y[i + 1].y))
        Edges.append(Edge(sorted_by_y[i].n, sorted_by_y[i + 1].n, cost_y))
        

    par = [0 for i in range(N)]
    rank = [0 for i in range(N)]
    V = N
    E = 2 * (N - 1)

    print(kruskal())