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
import heapq
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def solve(N: int, x: "List[int]", y: "List[int]"):
    xy = []
    edges = [] 

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

    x_xy = sorted(xy, key= lambda x:x[1])
    y_xy = sorted(xy, key= lambda x:x[2])

    append = edges.append
    for i in range(N-1):
        cur = x_xy[i]
        next = x_xy[i+1]
        append((next[1]-cur[1],next[0],cur[0]))
        cur = y_xy[i]
        next = y_xy[i+1]
        append((next[2]-cur[2],next[0],cur[0]))

    edges.sort(key= lambda x: x[0])
    uf = UnionFind(N)
    answer = 0

    for cost,node1,node2 in edges:
        if uf.same(node1,node2):
            continue

        answer += cost
        uf.union(node1,node2)
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    x = [int()] * (N)  
    y = [int()] * (N)  
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
import heapq
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def solve(N: int, x: "List[int]", y: "List[int]"):
    xy = []
    edges = [] 
    for i in range(N):
        xy.append((i,x[i],y[i]))

    x_xy = sorted(xy, key= lambda x:x[1])
    y_xy = sorted(xy, key= lambda x:x[2])
    
    for i in range(N-1):
        cur = x_xy[i]
        next = x_xy[i+1]
        edges.append((next[1]-cur[1],next[0],cur[0]))
        cur = y_xy[i]
        next = y_xy[i+1]
        edges.append((next[2]-cur[2],next[0],cur[0]))

    edges.sort(key= lambda x: x[0])
    uf = UnionFind(N)
    answer = 0
    
    for cost,node1,node2 in edges:
        if uf.same(node1,node2):
            continue

        answer += cost
        uf.union(node1,node2)
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    x = [int()] * (N)  
    y = [int()] * (N)  
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
from scipy.sparse import csr_matrix
import numpy as np

N = int(input())

XY = [[i] + [int(x) for x in input().split()] for i in range(N)]


edge = set()


for key in [itemgetter(1),itemgetter(2)]:
  XY.sort(key = key)
  
  for i in range(N-1):
    i1,x1,y1 = XY[i]
    i2,x2,y2 = XY[i+1]
    d = min(abs(x1-x2),abs(y1-y2))
    edge.add((i1,i2,d))
    

    

row,col,value = zip(*edge)


value = np.array(value,dtype=int)
graph = csr_matrix((value,(row,col)),shape=(N,N))



from scipy.sparse.csgraph import minimum_spanning_tree
tree = minimum_spanning_tree(graph, overwrite = True).astype(int)


answer = tree.sum()
print(answer)

Solution (Python):
import sys
import heapq
n = int(input())
v_ls = []
x_ls = []
y_ls = []
for j in range(n):
    x, y = [int(i) for i in sys.stdin.readline().split()]
    v_ls.append((j, x, y))

graph = {i:[] for i in range(n)}
v_ls.sort(key=lambda x:x[1])
for i, v in enumerate(v_ls[:-1]):
    _from = v
    _to = v_ls[i + 1]
    diff = _to[1] - _from[1]
    graph[_from[0]].append((_to[0], diff))
    graph[_to[0]].append((_from[0], diff))

v_ls.sort(key=lambda x:x[2])
for i, v in enumerate(v_ls[:-1]):
    _from = v
    _to = v_ls[i + 1]
    diff = _to[2] - _from[2]
    graph[_from[0]].append((_to[0], diff))
    graph[_to[0]].append((_from[0], diff))

v_ls.sort(key=lambda x:x[0])
already = set()
cur = [(0, 0)]
cost = 0
while len(cur) > 0:
    cur_cost, cur_ind = heapq.heappop(cur)
    if cur_ind in already:
        continue
    already.add(cur_ind)
    cost += cur_cost
    for _next, next_cost in graph[cur_ind]:
        if _next in already:
            continue
        heapq.heappush(cur, (next_cost, _next))
    if len(already) == n:
        break
print(cost)

Solution (Python):
from operator import itemgetter as get

class UnionFind():
	def __init__(self, n):
		self.n = n
		self.root = [-1] * (n + 1)
		self.rank = [0] * (n + 1)

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

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

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

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


def main():
	n, *L = map(int, open(0).read().split())
	x_order = sorted([(x, y, i) for i, (x, y) in enumerate(zip(*[iter(L)] * 2))])
	con = []
	for p1, p2 in zip(x_order, x_order[1:]):
		con.append((p1[2], p2[2], min(abs(p1[0] - p2[0]), abs(p1[1] - p2[1]))))
	y_order = sorted(x_order, key=get(1))
	for p1, p2 in zip(y_order, y_order[1:]):
		con.append((p1[2], p2[2], min(abs(p1[0] - p2[0]), abs(p1[1] - p2[1]))))
	uf = UnionFind(n)
	ans = 0
	for i, j, c in sorted(con, key=get(2)):
		if uf.isSame(i, j):
			continue
		ans += c
		uf.unite(i, j)
	print(ans)


if __name__ == "__main__":
	main()

Solution (Python):
import heapq as hq

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

cx = sorted(c, key=lambda x: x[1])
cy = sorted(c, key=lambda x: x[2])

edge = [set() for i in range(N)] 

for i in range(1, N):
  edge[cx[i-1][0]].add((cx[i][1]-cx[i-1][1], cx[i][0]))
  edge[cx[i][0]].add((cx[i][1]-cx[i-1][1], cx[i-1][0]))

  edge[cy[i-1][0]].add((cy[i][2]-cy[i-1][2], cy[i][0]))
  edge[cy[i][0]].add((cy[i][2]-cy[i-1][2], cy[i-1][0]))
  
for i in range(N-1):
  edge[cx[i][0]].add((cx[i+1][1]-cx[i][1], cx[i+1][0]))
  edge[cx[i+1][0]].add((cx[i+1][1]-cx[i][1], cx[i][0]))

  edge[cy[i][0]].add((cy[i+1][2]-cy[i][2], cy[i+1][0]))
  edge[cy[i+1][0]].add((cy[i+1][2]-cy[i][2], cy[i][0]))
  

q = [(0, 0)]
used = [False] * N
un = 0
r = 0

while q and un < N:
  w, prev = hq.heappop(q)

  if used[prev]: continue
  
  used[prev] = True
  un += 1
  r += w
  
  for w, to in edge[prev]:
    if not used[to]:
      hq.heappush(q, (w, to))
print(r)

Solution (Python):
import heapq as hq

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

cx = sorted(c, key=lambda x: x[1])
cy = sorted(c, key=lambda x: x[2])

edge = [set() for i in range(N)] 

for i in range(1, N):
  edge[cx[i-1][0]].add((cx[i][1]-cx[i-1][1], cx[i][0]))
  edge[cx[i][0]].add((cx[i][1]-cx[i-1][1], cx[i-1][0]))

  edge[cy[i-1][0]].add((cy[i][2]-cy[i-1][2], cy[i][0]))
  edge[cy[i][0]].add((cy[i][2]-cy[i-1][2], cy[i-1][0]))
  
for i in range(N-1):
  edge[cx[i][0]].add((cx[i+1][1]-cx[i][1], cx[i+1][0]))
  edge[cx[i+1][0]].add((cx[i+1][1]-cx[i][1], cx[i][0]))

  edge[cy[i][0]].add((cy[i+1][2]-cy[i][2], cy[i+1][0]))
  edge[cy[i+1][0]].add((cy[i+1][2]-cy[i][2], cy[i][0]))
  

q = [(0, 0)]
used = [False] * N
un = 0
r = 0

while q and un < N:
  w, prev = hq.heappop(q)

  if used[prev]: continue
  
  used[prev] = True
  un += 1
  r += w
  
  for w, to in edge[prev]:
    if not used[to]:
      hq.heappush(q, (w, to))
print(r)

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

cities = [tuple(map(int, input().split())) for _ in range(N)]

"""
AtCoder Beginner Contest 065 D
あるノードについてx座標の差とや座標の差それぞれの絶対値の小さいほうがコストになる
最小全域木を作ることでコストを最小にする
なので、
・x座標が小さい順で並べ替えたノードリスト
・ｙ座標が小さい順で並べ替えたノードリスト
を作って、それらのノード間に辺が張られているとする。
これで最小全域木ができるまでクラスカル法とかで頑張る
"""
xs = []
ys = []
for i,(x,y) in enumerate(cities):
    xs.append((x, i))
    ys.append((y, i))

xs.sort()
ys.sort()

es = []
for (xa, a), (xb,b) in zip(xs, xs[1:]):
    es.append((abs(xa-xb), a, b))

for (ya, a), (yb, b) in zip(ys, ys[1:]):
    es.append((abs(ya-yb), a, b))

es.sort()

uf = UnionFind(N)

totalcost = 0
"""
esは辺のコストが小さい順で並んでいるので、コストが小さい順に繋がれる
また、esは2N個なので、十分間に合う
"""
for c, a, b in es:
    if uf.is_same(a,b):
        continue
    uf.unite(a,b)
    totalcost += c

print(totalcost)

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

l=[]
for i in range(n):
    a,b=map(int,input().split())
    l.append([a,b,i])
l=sorted(l,key=lambda x: -x[0])
for i in range(n-1):
    x=l[i][2]
    y=l[i+1][2]
    z=l[i][0]-l[i+1][0]
    edge[x].append([z,y])
    edge[y].append([z,x])
l=sorted(l,key=lambda x: -x[1])
for i in range(n-1):
    x=l[i][2]
    y=l[i+1][2]
    z=l[i][1]-l[i+1][1]
    edge[x].append([z,y])
    edge[y].append([z,x])
print(prim_heap())

Solution (Python):


def solve() -> None:
    from collections import namedtuple
    from heapq import heappush, heappop
    from operator import attrgetter
    pt = namedtuple('pt', 'x y idx')

    n = int(input())
    cities = []
    for idx in range(n):
        x, y = map(int, input().split())
        cities.append(pt(x=x, y=y, idx=idx))

    g = tuple(set() for _ in range(n))

    xs = sorted(cities, key=attrgetter('x'))
    for a, b in zip(xs, xs[1:]):
        g[a.idx].add((b.x - a.x, b.idx))
        g[b.idx].add((b.x - a.x, a.idx))

    ys = sorted(cities, key=attrgetter('y'))
    for a, b in zip(ys, ys[1:]):
        g[a.idx].add((b.y - a.y, b.idx))
        g[b.idx].add((b.y - a.y, a.idx))

    ret = 0
    h = [(0, 0)]
    used = [False] * n
    count = 0

    while True:
        c, v = heappop(h)
        if used[v]:
            continue
        used[v] = True
        count += 1
        ret += c
        if count == n:
            break
        for c_, u in g[v]:
            if used[u]:
                continue
            heappush(h, (c_, u))

    return ret


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

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
pointx=[]
pointy=[]
for i in range(n):
    x,y=map(int,input().split())
    pointx.append((x,i))
    pointy.append((y,i))
pointx.sort()
pointy.sort()
G=[[] for i in range(n)]
for i in range(n-1):
    dx=abs(pointx[i+1][0]-pointx[i][0])
    G[pointx[i][1]].append((dx,pointx[i+1][1]))
    G[pointx[i+1][1]].append((dx,pointx[i][1]))
    dy=abs(pointy[i+1][0]-pointy[i][0])
    G[pointy[i][1]].append((dy,pointy[i+1][1]))
    G[pointy[i+1][1]].append((dy,pointy[i][1]))
import heapq
q=[]
check=[False]*n
check[0]=True
for i in G[0]:
    heapq.heappush(q,i)
ans=0
while len(q)>0:
    now=heapq.heappop(q)
    if not check[now[1]]:
        ans+=now[0]
        check[now[1]]=True
        for i in G[now[1]]:
            heapq.heappush(q,i)
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = list(range(n))
        self.ranks = [0 for _ in range(n)]
 
    def get_root(self, x):
        if self.parents[x] == x:
            return x
        self.parents[x] = self.get_root(self.parents[x])
        return self.parents[x]
 
    def merge(self, x, y):
        x = self.get_root(x)
        y = self.get_root(y)
        if x != y:
            if self.ranks[x] < self.ranks[y]:
                self.parents[x] = y
            else:
                self.parents[y] = x
                if self.ranks[x] == self.ranks[y]:
                    self.ranks[x] += 1
 
def kruskal(n_nodes, edges):
    edges.sort(key=itemgetter(2))
    res = []
    uf = UnionFind(n_nodes)
    for e in edges:
        if uf.get_root(e[0]) != uf.get_root(e[1]):
            res.append(e)
            uf.merge(e[0], e[1])
    return res

N = INT()
xy = [LIST() for _ in range(N)]
ixy = list(enumerate(xy))
ixy.sort(key=lambda x:x[1][0])

edges = []

for (i, (x, y)), (j, (x1, y1)) in zip(ixy, ixy[1:]):
	edges.append((i, j, min(abs(x-x1), abs(y-y1))))

ixy.sort(key=lambda x:x[1][1])
for (i, (x, y)), (j, (x1, y1)) in zip(ixy, ixy[1:]):
	edges.append((i, j, min(abs(x-x1), abs(y-y1))))

tree = kruskal(N, edges)
print(sum(x[2] for x in tree))

Solution (Python):
n = int(input())
L = []
ans = 0
for i in range(n):
    a,b = map(int,input().split())
    L.append([a,b,i])
P = []
L.sort()
for i in range(n-1):
    dist = min(abs(L[i][0]-L[i+1][0]),abs(L[i][1]-L[i+1][1]))
    P.append([dist,L[i][2],L[i+1][2]])
L = sorted(L, key = lambda x:x[1])
for i in range(n-1):
    dist = min(abs(L[i][0]-L[i+1][0]),abs(L[i][1]-L[i+1][1]))
    P.append([dist,L[i][2],L[i+1][2]])
P.sort()
par = [i for i in range(n)]
rank = [0]*n
def find(x,par):
    if x == par[x]:
        return par[x]
    else:
        return find(par[x],par)
def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    if x != y:
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
for i in range(len(P)):
    if find(P[i][1],par) != find(P[i][2],par):
        ans += P[i][0]
        unite(P[i][1],P[i][2],par,rank)
print(ans)

Solution (Python):

import sys
from operator import itemgetter
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def dist(x1, y1, x2, y2):
    return min(abs(x1-x2), abs(y1-y2))


n = int(input())
Aedges = []
Aedges2 = []
for i in range(n):
    x, y = map(int, input().split())
    Aedges.append((x, y, i))
    Aedges2.append((x, y, i))
Aedges.sort()
Aedges2.sort(key=itemgetter(1))



edges = []

for i in range(1, n):
    edges.append((Aedges[i][0]-Aedges[i-1][0], Aedges[i][2], Aedges[i-1][2]))
for i in range(1, n):
    edges.append((Aedges2[i][1]-Aedges2[i-1][1],
                  Aedges2[i][2], Aedges2[i-1][2]))

edges.sort()


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

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

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if(x == y):
            return
        self.tree[x] = y


def kruskal(n, edges):  
    U = UnionFind(n)
    res = 0
    for e in edges:
        w, s, t = e
        if not U.same(s, t):
            res += w
            U.unite(s, t)
    return res


print(kruskal(n, edges))

Solution (Python):
def main():
    import heapq
    from sys import stdin
    input=stdin.readline
    class unionfind():
        
        def __init__(self,size):
            self.size=size
            self.tree=[[i,1] for i in range(self.size)]
        
        
        def root(self,index):
            if self.tree[index][0]==index:
                return index
            else:
                self.tree[index][0]=self.root(self.tree[index][0])
                return self.tree[index][0]
    
        
        def unite(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1!=r2:
                d1,d2=self.tree[r1][1],self.tree[r2][1]
                if d1<=d2:
                    self.tree[r1][0]=r2
                    self.tree[r2][1]=max(d1+1,d2)
                else:
                    self.tree[r2][0]=r1
                    self.tree[r1][1]=max(d2+1,d1)
    
        
        def same(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            return r1==r2
    
    n=int(input())
    xy=[list(map(int,input().split())) for _ in [0]*n]
    xyz=[xy[i]+[i] for i in range(n)]
    x_sort=sorted(xyz,key=lambda x:x[0])
    y_sort=sorted(xyz,key=lambda x:x[1])
    g=[]
    heapq.heapify(g)
    for i in range(n-1):
        heapq.heappush(g,[abs(x_sort[i+1][0]-x_sort[i][0]),x_sort[i][2],x_sort[i+1][2]])
    for i in range(n-1):
        heapq.heappush(g,[abs(y_sort[i+1][1]-y_sort[i][1]),y_sort[i][2],y_sort[i+1][2]])
    u=unionfind(n)
    cnt=0
    while g:
        d,i,j=heapq.heappop(g)
        if u.same(i,j)==False:
            cnt+=d
            u.unite(i,j)
    print(cnt)
main()

Solution (Python):
def main():
    import heapq
    def root(index):
        if tree[index][0]==index:
            return index
        else:
            tree[index][0]=root(tree[index][0])
            return tree[index][0]

    def unite(index1,index2):
        r1=root(index1)
        r2=root(index2)
        if r1!=r2:
            d1,d2=tree[r1][1],tree[r2][1]
            if d1<=d2:
                tree[r1][0]=r2
                tree[r2][1]=max(d1+1,d2)
            else:
                tree[r2][0]=r1
                tree[r1][1]=max(d2+1,d1)

    def same(index1,index2):
        return root(index1)==root(index2)
    
    n=int(input())
    xy=[list(map(int,input().split())) for _ in [0]*n]
    xyz=[xy[i]+[i] for i in range(n)]
    x_sort=sorted(xyz,key=lambda x:x[0])
    y_sort=sorted(xyz,key=lambda x:x[1])
    
    tree=[[i,1] for i in range(n)]
    g=[]
    heapq.heapify(g)
    for i in range(n-1):
        heapq.heappush(g,[abs(x_sort[i+1][0]-x_sort[i][0]),x_sort[i][2],x_sort[i+1][2]])
    for i in range(n-1):
        heapq.heappush(g,[abs(y_sort[i+1][1]-y_sort[i][1]),y_sort[i][2],y_sort[i+1][2]])

    cnt=0
    while g:
        d,i,j=heapq.heappop(g)
        if same(i,j)==False:
            cnt+=d
            unite(i,j)
    print(cnt)
main()

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

class UnionFind(object):
    def __init__(self,n):
        self.__par=list(range(n))
        self.__rank=[0]*n
        self.__size=[1]*n

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

    def unite(self,i,j):
        i=self.root(i); j=self.root(j)
        par=self.__par; rank=self.__rank; size=self.__size
        if(i==j): return False
        if(rank[i]>rank[j]):
            par[j]=i
            size[i]+=size[j]
        else:
            par[i]=j
            size[j]+=size[i]
            if(rank[i]==rank[j]): rank[j]+=1
        return True

    def size(self,k):
        return self.__size[self.root(k)]

def resolve():
    n=int(input())
    XYI=[0]*n
    for i in range(n):
        x,y=map(int,input().split())
        XYI[i]=(x,y,i)

    
    E=[]
    XYI.sort()
    for i in range(n-1):
        x0,y0,u=XYI[i]
        x1,y1,v=XYI[i+1]
        E.append((u,v,x1-x0))
    XYI.sort(lambda x:x[1])
    for i in range(n-1):
        x0,y0,u=XYI[i]
        x1,y1,v=XYI[i+1]
        E.append((u,v,y1-y0))

    
    E.sort(lambda x:x[2])
    uf=UnionFind(n)
    ans=0
    for u,v,w in E:
        if(uf.unite(u,v)):
            ans+=w
    print(ans)
resolve()

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy


from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])

def graphm():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(m):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((w,b))
        g[b].append((w,a))
    return n,m,g

def prim(n,g):
    edgelist = []
    used = [False for _ in range(n)]
    for edge in g[0]:
        heappush( edgelist, edge)
    used[0] = True
    res = 0 

    while len(edgelist)>0:
        minedge = heappop(edgelist)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = True
        for edge in g[v]:
            if not used[edge[1]]:
                heappush( edgelist, edge)
        res += minedge[0]
    return res

def main():
    n=inp()
    xy=[]
    for index in range(n):
        x,y = inpm()
        xy.append((x,y,index))
        
    g=[[] for _ in range(n)]
    xy.sort()
    for i in range(n-1):
        j = i+1
        w = min(abs(xy[i][0]-xy[j][0]),abs(xy[i][1]-xy[j][1]))
        a = xy[i][2]
        b = xy[j][2]
        g[a].append((w,b))
        g[b].append((w,a))
    xy.sort(key=lambda y:y[1])
    for i in range(n-1):
        j = i+1
        w = min(abs(xy[i][0]-xy[j][0]),abs(xy[i][1]-xy[j][1]))
        a = xy[i][2]
        b = xy[j][2]
        g[a].append((w,b))
        g[b].append((w,a))
    print( prim(n,g) )

if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy


from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])

def graphm():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(m):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((w,b))
        g[b].append((w,a))
    return n,m,g

def prim(n,g):
    edgelist = []
    used = [False for _ in range(n)]
    for edge in g[0]:
        heappush( edgelist, edge)
    used[0] = True
    res = 0 

    while len(edgelist)>0:
        minedge = heappop(edgelist)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = True
        for edge in g[v]:
            if not used[edge[1]]:
                heappush( edgelist, edge)
        res += minedge[0]
    return res

def main():
    n=inp()
    xy=[]
    for index in range(n):
        x,y = inpm()
        xy.append((x,y,index))
        
    g=[[] for _ in range(n)]
    xy.sort()
    for i in range(n-1):
        j = i+1
        w = min(abs(xy[i][0]-xy[j][0]),abs(xy[i][1]-xy[j][1]))
        a = xy[i][2]
        b = xy[j][2]
        g[a].append((w,b))
        g[b].append((w,a))
    xy.sort(key=lambda y:y[1])
    for i in range(n-1):
        j = i+1
        w = min(abs(xy[i][0]-xy[j][0]),abs(xy[i][1]-xy[j][1]))
        a = xy[i][2]
        b = xy[j][2]
        g[a].append((w,b))
        g[b].append((w,a))
    print( prim(n,g) )

if __name__ == "__main__":
    main()

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):
from operator import itemgetter
import heapq
 
N = int(input())
pos = [[int(p) for p in input().split()] for _ in range(N)]
 
pos.sort()
for i in range(N):
    pos[i].append(i)
    
Y = sorted(pos, key=itemgetter(1))
Y_idx = [0]*N
for i in range(N):
    Y_idx[Y[i][2]] = i
    
ans = 0
used = [0]*N
used[0] = 1
h = []
c = 1
idx = Y_idx[0]
heapq.heappush(h, (pos[c][0]-pos[c-1][0], 1))
if idx > 0:
    heapq.heappush(h, (Y[idx][1]-Y[idx-1][1], Y[idx-1][2]))
if idx < N-1:
    heapq.heappush(h, (Y[idx+1][1]-Y[idx][1], Y[idx+1][2]))
    
cnt = 0
while cnt < N-1:
    t = heapq.heappop(h)
    if used[t[1]] == 1:
        continue
    c = t[1]
    used[c] = 1
    cnt += 1
    ans += t[0]
    if c > 0 and used[c-1] == 0:
        heapq.heappush(h, (pos[c][0]-pos[c-1][0], c-1))
    if c < N-1 and used[c+1] == 0:
        heapq.heappush(h, (pos[c+1][0]-pos[c][0], c+1))
    idx = Y_idx[c]
    if idx > 0 and used[Y[idx-1][2]] == 0:
        heapq.heappush(h, (Y[idx][1]-Y[idx-1][1], Y[idx-1][2]))
    if idx < N-1 and used[Y[idx+1][2]] == 0:
        heapq.heappush(h, (Y[idx+1][1]-Y[idx][1], Y[idx+1][2]))
            
print(ans)