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
input = sys.stdin.readline

class UnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x:int, y:int) -> bool:
        if self.isSame(x,y):
            
            return False
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
                
        return True
                
    
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)
    
    
def kruskal(edges: list, node_num: int) -> int:
    edges.sort(key=lambda x:x[0])
    
    uf = UnionFind(node_num)
    rem = node_num-1
    ans = 0
    
    for cost, prev, nex in edges:
        if uf.find(prev) != uf.find(nex):
            uf.unite(prev, nex)
            ans += cost
            rem -= 1
            
        if rem == 0:
            break
        
    return ans


N = int(input().rstrip())

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


edges = []
for xy in [1,2]:
    town.sort(key=lambda x: x[xy])
    
    for i in range(N-1):
        edges.append(tuple([town[i+1][xy] - town[i][xy],town[i+1][0], town[i][0]]))
        
        
ans = kruskal(edges, N)
print(ans)

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

N = int(input().rstrip())

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



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

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


par = [i for i in range(N)]
rank = [0 for i in range(N)]

def find(x:int) -> int:
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
def unite(x:int, y:int) -> bool:
    
    if find(x) == find(y):
        return False
    
    rootx = find(x)
    rooty = find(y)
    
    if rank[rootx] < rank[rooty]:
        par[rootx] = rooty
        
    else:
        par[rooty] = rootx
        if rank[rootx] == rank[rooty]:
            rank[rootx] += 1

    return True    
    
rem = N
ans = 0

for cost,nex,prev in edges:
    if find(nex) != find(prev):
        unite(nex,prev)
        ans += cost
        rem -= 1
        
    if rem == 1:
        break
    
print(ans)

Solution (Python):


















''' 二次元配列を一列ずつ
for i in ans:
	print(*i)
'''
''' heapq
queue = []
heapq.heapify(queue) 
heapq.heappush(queue,num) 
pop = heapq.heappop(queue) 
pop = heapq.heappushpop(queue,num) 

'''

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def Find(x):	
	global table

	if table[x] == x:
		return x
	else:
		table[x] = Find(table[x])	
		return table[x]

def Union(x,y):	
	x = Find(x)
	y = Find(y)

	if x == y:
		return

	if rank[x] > rank[y]:
		table[y] = x
	else:
		table[x] = y
		if rank[x] == rank[y]:
			rank[y] += 1

def Check(x,y):
	if Find(x) == Find(y):
		return True
	else:
		return False



N = int(input())



table = [i for i in range(N)]	
rank  = [1 for i in range(N)]	


q = []
heapq.heapify(q)


xys = [list(map(int,input().split()))+[i] for i in range(N)]
xys.sort()
for i in range(N-1):
	xa,ya,a = xys[i]
	xb,yb,b = xys[i+1]
	heapq.heappush(q,[xb-xa,a,b])

xys.sort(key=lambda x:x[1])
for i in range(N-1):
	xa,ya,a = xys[i]
	xb,yb,b = xys[i+1]
	heapq.heappush(q,[yb-ya,a,b])


weight = 0


while q:
	w,a,b = heapq.heappop(q)

	if not Check(a,b):
		weight += w
		Union(a,b)

print(weight)

Solution (Python):











from collections import defaultdict


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())
Vx=[]
Vy=[]
for i in range(N):
  x,y=map(int,input().split())
  Vx.append([i,x])
  Vy.append([i,y])

E=[]

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

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


for i in range(N-1):
  a,b=Vx[i]
  c,d=Vx[i+1]
  e,f=Vy[i]
  g,h=Vy[i+1]
  E.append((d-b,a,c))
  E.append((h-f,e,g))
  

E=sorted(E,key = lambda x:x[0])
UF=UnionFind(N)
ans=0
for a,b,c in E:
  if UF.find(b)!=UF.find(c):
    ans+=a
    UF.union(b,c)

print(ans)

Solution (Python):
import operator
import numpy as np
n = int(input())
xy = np.array([list(map(int, input().split())) for _ in range(n)])

sa1 = np.argsort(xy[:,0])
sa2 = np.argsort(xy[:,1])

s1 = xy[sa1,0]
s2 = xy[sa2,1]
c1 = s1[1:] - s1[:-1]
c2 = s2[1:] - s2[:-1]

c = [(c, (sa1[i], sa1[i+1])) for i, c in enumerate(c1)] + [(c, (sa2[i], sa2[i+1])) for i, c in enumerate(c2)]
c = sorted(c, key=operator.itemgetter(0))

total_cost = 0
sg = {}
for cost, verts in c:
    vf1 = sg.get(verts[0])
    vf2 = sg.get(verts[1])
    if vf1 and vf2:
        if vf1 is vf2: continue
        if len(vf1) < len(vf2): vf1, vf2 = vf2, vf1
        total_cost += cost
        vf1.update(vf2)
        for v in vf2: sg[v] = vf1
    else:
        total_cost += cost
        if vf1:
            vf1.add(verts[1])
            sg[verts[1]] = vf1
        elif vf2:
            vf2.add(verts[0])
            sg[verts[0]] = vf2
        else:
            sg[verts[0]] = sg[verts[1]] = set(verts)
print(total_cost)

Solution (Python):
from operator import itemgetter
from heapq import heappush,heappop
N = int(input())
table=[]
for i in range(N):
    a,b = map(int,input().split())
    table.append([a,b,i])
A = sorted(table,key=itemgetter(0))
B = sorted(table,key=itemgetter(1))

graph=[]
for k in range(N):
    graph.append((min(abs(A[k][0]-A[k-1][0]),abs( A[k][1]-A[k-1][1])),A[k][2],A[k-1][2]))
for k in range(N):
    graph.append((min(abs(B[k][0]-B[k-1][0]),abs( B[k][1]-B[k-1][1])),B[k][2],B[k-1][2]))

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

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

kei = Unionfindtree(N)
graph.sort()
dist =0
for d,i,j in graph:
    if not kei.connect(i,j):
        kei.union(i,j)
        dist +=d
print(dist)

Solution (Python):
from operator import itemgetter
from heapq import heappush,heappop
import sys
N = int(input())
table=[]
for i in range(N):
    a,b = map(int,input().split())
    table.append([a,b,i])
A = sorted(table,key=itemgetter(0))
B = sorted(table,key=itemgetter(1))

graph=[[] for i in range(N)]
for k in range(N-1):
    graph[A[k][2]].append((abs(A[k][0]-A[k-1][0]),A[k-1][2]))
    graph[A[k][2]].append((abs(A[k][0]-A[k+1][0]),A[k+1][2]))
graph[A[N-1][2]].append((abs(A[N-1][0]-A[N-2][0]),A[N-2][2]))
for k in range(N-1):
    graph[B[k][2]].append((abs(B[k][1]-B[k-1][1]),B[k-1][2]))
    graph[B[k][2]].append((abs(B[k][1]-B[k+1][1]),B[k+1][2]))
graph[B[N-1][2]].append((abs(B[N-1][1]-B[N-2][1]),B[N-2][2]))

kei = []
visit=[False]*N
heappush(kei,[0,0])
dist = 0
point =0
while kei:
    d,i = heappop(kei)
    if point ==N:
        print(dist)
        sys.exit()
    if visit[i]==True:
        continue
    visit[i]=True
    dist += d
    point+=1
    for e,j in graph[i]:
        if not visit[j]:
            heappush(kei,[e,j])

Solution (Python):
from operator import itemgetter
from heapq import heappush,heappop
N = int(input())
table=[]
for i in range(N):
    a,b = map(int,input().split())
    table.append([a,b,i])
A = sorted(table,key=itemgetter(0))
B = sorted(table,key=itemgetter(1))

graph=[]
for k in range(N):
    graph.append((min(abs(A[k][0]-A[k-1][0]),abs( A[k][1]-A[k-1][1])),A[k][2],A[k-1][2]))
for k in range(N):
    graph.append((min(abs(B[k][0]-B[k-1][0]),abs( B[k][1]-B[k-1][1])),B[k][2],B[k-1][2]))

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

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

kei = Unionfindtree(N)
graph.sort()
dist =0
for d,i,j in graph:
    if not kei.connect(i,j):
        kei.union(i,j)
        dist +=d
print(dist)

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

def Find(x):	
	global table

	if table[x] == x:
		return x
	else:
		table[x] = Find(table[x])	
		return table[x]

def Union(x,y):	
	x = Find(x)	
	y = Find(y)
	
	if x == y:
		return
	
	if rank[x] > rank[y]:
		table[y] = x
	else:
		table[x] = y
		if rank[x] == rank[y]:
			rank[y] += 1

def Check(x,y):
	if Find(x) == Find(y):
		return True
	else:
		return False


		

N = int(input())


table = [i for i in range(N)]	
rank  = [1 for i in range(N)]	


q = []
heapq.heapify(q)


rout = []

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

rout.sort(key=lambda x:x[2])
for i in range(N-1):	
	n1,x1,y1 = rout[i]
	n2,x2,y2 = rout[i+1]
	w = y2 - y1
	heapq.heappush(q,[w,n1,n2])



rout.sort(key=lambda x:x[1])
for i in range(N-1):	
	n1,x1,y1 = rout[i]
	n2,x2,y2 = rout[i+1]
	w = x2 - x1
	heapq.heappush(q,[w,n1,n2])

	


weight = 0


while q:
	w,a,b = heapq.heappop(q)
	
	if not Check(a,b):
		weight += w
		Union(a,b)
		
print(weight)

Solution (Python):
N = int(input())
xy = [[int(_) for _ in input().split()] for i in range(N)]

xsort_n = sorted(range(N), key=lambda n:xy[n][0])
ysort_n = sorted(range(N), key=lambda n:xy[n][1])

from collections import defaultdict

neighbors = defaultdict(list)

for i in range(N - 1):
    x1 = xsort_n[i]
    x2 = xsort_n[i+1]
    xd = xy[x2][0] - xy[x1][0]
    y1 = ysort_n[i]
    y2 = ysort_n[i+1]
    yd = xy[y2][1] - xy[y1][1]
    neighbors[x1].append((x2, xd))
    neighbors[x2].append((x1, xd))
    neighbors[y1].append((y2, yd))
    neighbors[y2].append((y1, yd))

from heapq import *

isused = [0] * N

h = []

heappush(h, (0, 0))

result = 0

while h:
    d, n = heappop(h)
    if isused[n]:
        continue
    result += d
    isused[n] = 1
    for ni, nd in neighbors[n]:
        if not isused[ni]:
            heappush(h, (nd, ni))
    
print(result)

Solution (Python):
N = int(input())
xy = [[int(_) for _ in input().split()] for i in range(N)]

xsort_n = sorted(range(N), key=lambda n:xy[n][0])
ysort_n = sorted(range(N), key=lambda n:xy[n][1])

from collections import defaultdict

neighbors = defaultdict(list)

for i in range(N - 1):
    x1 = xsort_n[i]
    x2 = xsort_n[i+1]
    xd = xy[x2][0] - xy[x1][0]
    y1 = ysort_n[i]
    y2 = ysort_n[i+1]
    yd = xy[y2][1] - xy[y1][1]
    neighbors[x1].append((x2, xd))
    neighbors[x2].append((x1, xd))
    neighbors[y1].append((y2, yd))
    neighbors[y2].append((y1, yd))

from heapq import *

isused = [0] * N

h = []

heappush(h, (0, 0))

result = 0

while h:
    d, n = heappop(h)
    if isused[n]:
        continue
    result += d
    isused[n] = 1
    for ni, nd in neighbors[n]:
        if not isused[ni]:
            heappush(h, (nd, ni))
    
print(result)

Solution (Python):
N = int(input())
xy = [[int(_) for _ in input().split()] for i in range(N)]

xsort_n = sorted(range(N), key=lambda n:xy[n][0])
ysort_n = sorted(range(N), key=lambda n:xy[n][1])

from collections import defaultdict

neighbors = defaultdict(list)

for i in range(N - 1):
    x1 = xsort_n[i]
    x2 = xsort_n[i+1]
    y1 = ysort_n[i]
    y2 = ysort_n[i+1]
    neighbors[x1].append(x2)
    neighbors[x2].append(x1)
    neighbors[y1].append(y2)
    neighbors[y2].append(y1)

from heapq import *

isused = [0] * N

h = []

heappush(h, (0, 0))

result = 0

while h:
    d, n = heappop(h)
    if isused[n]:
        continue
    result += d
    isused[n] = 1
    for i in neighbors[n]:
        if not isused[i]:
            d1 = min(abs(xy[n][0] - xy[i][0]), abs(xy[n][1] - xy[i][1]))
            heappush(h, (d1, i))
    
print(result)

Solution (Python):
import sys
sys.setrecursionlimit(500000)

N = int(input())
T = [[i] + list(map(int, input().split())) for i in range(N)]
E = [[] for i in range(N)]
E = []
T.sort(key=lambda x: x[1])
for i in range(N-1):
    s, l = T[i:i+2]
    E.append([s[0], l[0], l[1]-s[1]])
T.sort(key=lambda x: x[2])
for i in range(N-1):
    s, l = T[i:i+2]
    E.append([s[0], l[0], l[2]-s[2]])
E.sort(key=lambda x: x[2])

Par = list(range(N))
def root(x):
    if Par[x] == x:
        return x
    else:
        Par[x] = root(Par[x])
        return Par[x]

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

def unite(x, y):
    x = root(x)
    y = root(y)
    if x != y:
        Par[x] = y

ans = 0
for e in E:
    if not same(e[0], e[1]):
        ans += e[2]
        unite(e[0], e[1])

print(ans)

Solution (Python):
n = int(input())
par,rank = [i for i in range(n+1)],[0 for i in range(n+1)]
def root(x):
	if par[x]!=x: par[x] = root(par[x])
	return par[x]
def unite(x,y):
	x2,y2 = root(x),root(y)
	if x2!=y2:
		if rank[x2]<rank[y2]: par[x2] = y2
		else: par[y2] = x2
		if rank[x2]==rank[y2]: rank[x2]+=1
def same(x,y):
	return root(x)==root(y)
a,b = [],[]
for i in range(n):
	x,y = (int(_) for _ in input().split())
	a.append([x,i])
	b.append([y,i])
a,b,h,ans = sorted(a),sorted(b),[],0
from heapq import heappush,heappop
for i in range(n-1):
	heappush(h,(a[i+1][0]-a[i][0],a[i+1][1],a[i][1]))
	heappush(h,(b[i+1][0]-b[i][0],b[i+1][1],b[i][1]))
while h:
	i,j,k = heappop(h)
	if root(j)!=root(k):
		unite(j,k)
		ans += i
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(100000)
n = int(input())
x = []
y = []
for i in range(n):
    s = list(map(int, input().split()))
    x.append([s[0], i])
    y.append([s[1], i])

x.sort()
y.sort()

xdiff = []
ydiff = []
for i in range(1, n):
    xdiff.append([x[i][0] - x[i - 1][0], x[i - 1][1], x[i][1]])
    ydiff.append([y[i][0] - y[i - 1][0], y[i - 1][1], y[i][1]])

xdiff.sort()
ydiff.sort()

parent = [-1] * n

def getParent(index):
    if parent[index] == -1:
        return index
    else:
        parent[index] = getParent(parent[index])
        return parent[index]

count = 0
ans = 0
xIndex = 0
yIndex = 0
while count != n - 1:
    if xIndex != n - 1:
        xTemp = xdiff[xIndex]
    if yIndex != n - 1:
        yTemp = ydiff[yIndex]

    if yIndex == n - 1 or (xIndex != n - 1 and xTemp[0] < yTemp[0]):
        xIndex += 1
        temp = xTemp
    else:
        yIndex += 1
        temp = yTemp

    parent1 = getParent(temp[1])
    parent2 = getParent(temp[2])
    if parent1 == parent2:
        continue
    else:
        count += 1
        ans += temp[0]
        parent[parent1] = parent2

print(ans)

Solution (Python):
from operator import itemgetter
from heapq import heappush,heappop
N = int(input())
table=[]
for i in range(N):
    a,b = map(int,input().split())
    table.append([a,b,i])
A = sorted(table,key=itemgetter(0))
B = sorted(table,key=itemgetter(1))

graph=[]
for k in range(N):
    graph.append([min(abs(A[k][0]-A[k-1][0]),abs( A[k][1]-A[k-1][1])),A[k][2],A[k-1][2]])
for k in range(N):
    graph.append([min(abs(B[k][0]-B[k-1][0]),abs( B[k][1]-B[k-1][1])),B[k][2],B[k-1][2]])

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

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

kei = Unionfindtree(N)
graph.sort()
dist =0
for d,i,j in graph:
    if not kei.connect(i,j):
        kei.union(i,j)
        dist +=d
print(dist)

Solution (Python):
import sys
import collections
import itertools

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        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 are_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def grouper(self):
        import itertools
        import operator
        par = operator.itemgetter(1)
        for _, group in itertools.groupby(
                sorted(enumerate(self.par), key=par), par):
            yield [i for i, par in group]

def sliding_window(n, seq):
    import collections
    import itertools
    return zip(*(collections.deque(itertools.islice(it, i), 0) or it
               for i, it in enumerate(itertools.tee(seq, n))))

Edge = collections.namedtuple('Edge', ['s', 't', 'cost'])

N = int(sys.stdin.readline())
xys = [[i] + list(map(int, line.split())) for i, line in enumerate(sys.stdin)]
edges = []
for (i1, x1, _), (i2, x2, _) in sliding_window(2, sorted(xys, key=lambda t: t[1])):
    edges.append(Edge(i1, i2, abs(x1 - x2)))
for (i1, _, y1), (i2, _, y2) in sliding_window(2, sorted(xys, key=lambda t: t[2])):
    edges.append(Edge(i1, i2, abs(y1 - y2)))
edges = sorted(edges, key=lambda e: e.cost)
uf = UnionFind(N)
min_cost = 0
for edge in edges:
    if not uf.are_same(edge.s, edge.t):
        uf.union(edge.s, edge.t)
        min_cost += edge.cost
print(min_cost)

Solution (Python):
n = int(input())
z = []
for i in range(n):
    X, Y = map(int, input().split())
    z.append([X, Y, i])

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

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

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


parent = [i for i in range(n)]
rank = [0 for i in range(n)]

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

def judge(a, b):
    a_parent = find(a)
    b_parent = find(b)
    if a_parent == b_parent:
        return True
    else:
        return False

def merge(a, b):
    a_parent = find(a)
    b_parent = find(b)
    if a_parent == b_parent:
        return
    else:
        if rank[a_parent] > rank[b_parent]:
            parent[b_parent] = a_parent
        elif rank[a_parent] < rank[b_parent]:
            parent[a_parent] = b_parent
        else:
            parent[a_parent] = b_parent
            rank[b_parent] += 1


from collections import deque
q = deque(new_list)

cost = 0
while len(q)>0:
    c = q.popleft()
    if not judge(c[1], c[2]):
        merge(c[1], c[2])
        cost += c[0]

print(cost)

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

X = sorted([(i, xy[0]) for i, xy in enumerate(p)], key=lambda x: x[1])
Y = sorted([(i, xy[1]) for i, xy in enumerate(p)], key=lambda x: x[1])
dX = sorted([[X[i][0], X[i+1][0], X[i+1][1]-X[i][1]] for i in range(n-1)], key=lambda x: x[2])
dY = sorted([[Y[i][0], Y[i+1][0], Y[i+1][1]-Y[i][1]] for i in range(n-1)], key=lambda x: x[2])

def root(x):
    if parent[x] == x:
        return x
    else:
        return root(parent[x])

def connected(x, y):
    return root(x) == root(y)

parent = [i for i in range(n+1)]
depth = [1 for i in range(n+1)]

ans = 0
i, j = 0, 0
while i < n-1 and j < n-1:
    if dX[i][2] < dY[j][2]:
        a, b, d = dX[i]
        i += 1
    else:
        a, b, d = dY[j]
        j += 1
    ra, rb = map(root, [a,b])
    if ra != rb:
        if depth[ra] < depth[rb]:
            a, b = b, a
            ra, rb = rb, ra
        parent[rb] = ra
        depth[ra] = max(depth[ra], depth[rb]+1)
        ans += d
print(ans)

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

X = sorted([[i, xy[0]] for i, xy in P], key=lambda x: x[1])
Y = sorted([[i, xy[1]] for i, xy in P], key=lambda y: y[1])

Xe = [[X[i][0], X[i+1][0], abs(X[i][1]-X[i+1][1])] for i in range(N-1)]
Ye = [[Y[i][0], Y[i+1][0], abs(Y[i][1]-Y[i+1][1])] for i in range(N-1)]
E = sorted(Xe + Ye, key=lambda e: e[2])


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

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

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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


uf = UnionFind(N)
edge_cnt = 0
MST_cost = 0
i = 0

while edge_cnt < N-1:
    a, b, cost = E[i]
    if not uf.same_check(a, b):
        MST_cost += cost
        uf.union(a, b)
        edge_cnt += 1
    i += 1

print(MST_cost)

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

X = sorted([[i, xy[0]] for i, xy in P], key=lambda x: x[1])
Y = sorted([[i, xy[1]] for i, xy in P], key=lambda y: y[1])

Xe = [[X[i][0], X[i+1][0], abs(X[i][1]-X[i+1][1])] for i in range(N-1)]
Ye = [[Y[i][0], Y[i+1][0], abs(Y[i][1]-Y[i+1][1])] for i in range(N-1)]
E = sorted(Xe + Ye, key=lambda e: e[2])


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

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

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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


uf = UnionFind(N)
edge_cnt = 0
MST_cost = 0
i = 0

while edge_cnt < N-1:
    a, b, cost = E[i]
    if not uf.same_check(a, b):
        MST_cost += cost
        uf.union(a, b)
        edge_cnt += 1
    i += 1

print(MST_cost)

Solution (Python):
def d_Built(N, P):
    xs = []
    ys = []
    E = []  
    for i, (x, y) in enumerate(P):
        xs.append((x, i))
        ys.append((y, i))
    xs.sort()
    ys.sort()

    
    x_edge = []
    y_edge = []
    for i in range(N - 1):
        
        x_edge.append((xs[i][1], xs[i + 1][1], xs[i + 1][0] - xs[i][0]))
        y_edge.append((ys[i][1], ys[i + 1][1], ys[i + 1][0] - ys[i][0]))
    x_edge.extend(y_edge)  
    x_edge.sort(key=lambda x: x[2])  

    class UnionFind:
        def __init__(self, N):
            self.p = list(range(N))  
            self.rank = [0] * N  
            self.size = [1] * N  

        def find(self, x):
            
            if self.p[x] != x:
                
                self.p[x] = self.find(self.p[x])  
            return self.p[x]

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

        def union(self, x, y):
            
            u = self.find(x)
            v = self.find(y)
            if u == v:
                
                return
            if self.rank[u] < self.rank[v]:
                self.p[u] = v  
                self.size[v] += self.size[u]  
                self.size[u] = 0  
            else:
                
                self.p[v] = u
                self.size[u] += self.size[v]
                self.size[v] = 0
                if self.rank[u] == self.rank[v]:
                    
                    self.rank[u] += 1

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

        def show(self):
            return self.p

    uf = UnionFind(N)
    
    i = 0
    while len(E) != N - 1:
        x1, x2, cost = x_edge[i]
        if uf.find(x1) != uf.find(x2):
            
            uf.union(x1, x2)
            E.append(cost)
        i += 1
    return sum(E)
  
N = int(input())
P = [[int(i) for i in input().split()] for j in range(N)]
print(d_Built(N, P))

Solution (Python):
from heapq import heappop, heappush
N = int(input())
x, y = [0] * N, [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())

inds = range(N)
d = [[] for i in range(N)]
xxy = sorted(zip(x, y, inds))
for i in range(N-1):
    cur = xxy[i][2]
    nex = xxy[i+1][2]
    d[cur].append(((xxy[i+1][0] - xxy[i][0]), nex))
    d[nex].append(((xxy[i+1][0] - xxy[i][0]), cur))

yxy = sorted(zip(y, x, inds))
for i in range(N-1):
    cur = yxy[i][2]
    nex = yxy[i+1][2]
    d[cur].append(((yxy[i+1][0] - yxy[i][0]), nex))
    d[nex].append(((yxy[i+1][0] - yxy[i][0]), cur))

ans = 0
used = [False] * N
used[0] = True
q = []
for i in d[0]:
    heappush(q, i)
while len(q) > 0:
    v, x = heappop(q)
    if used[x]:
        continue
    used[x] = True
    ans += v
    for y in d[x]:
        if not used[y[1]]:
            heappush(q, y)

print(ans)

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

N = int(input())
ixy=[]
for i in range(N):
  x, y = map(int,input().split())
  ixy+=[[i,x,y]]
costs = []

ixy.sort(key=lambda x:x[1])
for j in range(N-1):
  costs += [(ixy[j][0], ixy[j+1][0], ixy[j+1][1]-ixy[j][1])]
  costs += [(ixy[j+1][0], ixy[j][0], ixy[j+1][1]-ixy[j][1])]
ixy.sort(key=lambda y:y[2])
for j in range(N-1):
  costs += [(ixy[j][0], ixy[j+1][0], ixy[j+1][2]-ixy[j][2])]
  costs += [(ixy[j+1][0], ixy[j][0], ixy[j+1][2]-ixy[j][2])]

costs.sort(key=lambda cost:cost[2])
ans = 0
roots = UnionFind(N)
for cost in costs:
  u, v, c = cost
  if roots.find(u)!=roots.find(v):
    roots.union(u, v)
    ans += c
    
print(ans)

Solution (Python):
N = int(input())
ixy=[]
for i in range(N):
  x, y = map(int,input().split())
  ixy+=[[i,x,y]]
costs = [[] for i in range(N)]

ixy.sort(key=lambda x:x[1])
for j in range(N-1):
  costs[ixy[j][0]] += [(ixy[j+1][0],abs(ixy[j][1]-ixy[j+1][1]))]
  costs[ixy[j+1][0]] += [(ixy[j][0],abs(ixy[j][1]-ixy[j+1][1]))]
ixy.sort(key=lambda y:y[2])
for j in range(N-1):
  costs[ixy[j][0]] += [(ixy[j+1][0],abs(ixy[j][2]-ixy[j+1][2]))]
  costs[ixy[j+1][0]] += [(ixy[j][0],abs(ixy[j][2]-ixy[j+1][2]))]

import heapq
pq = []
heapq.heappush(pq, (0,0))

visited = [0]*N
ans = 0
while pq:
  cost, v = heapq.heappop(pq)

  if visited[v]: continue
  
  ans += cost
  visited[v]=1
  
  for u,c in costs[v]:
    if not visited[u]:
      heapq.heappush(pq, (c,u))

print(ans)

Solution (Python):

import heapq
import sys
sys.setrecursionlimit(10**6)
N = input()
a = []
for i in range(N):
	x,y=map(int,raw_input().split())
	a.append((i,x,y))


a1=sorted(a, key=lambda x: x[1])
a2=sorted(a, key=lambda x: x[2])




par=[ i for i in range(N) ]

def root(x):
	if par[x]==x:
		return x
	else:
		r=root(par[x])
		
		par[x]=r
		return r

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


def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y:
		return
	else:
		par[x]=y


b=[]
for i in range(N-1):
	
	heapq.heappush( b, ( abs(a1[i+1][1]-a1[i][1]),a1[i][0],a1[i+1][0],  ))

for i in range(N-1):
	
	heapq.heappush( b, ( abs(a2[i+1][2]-a2[i][2]),a2[i][0],a2[i+1][0],  ))





ans=0
cnt=0
for i in range(len(b)):
	if cnt==N-1:
		break
	val=heapq.heappop(b)
	
	if not same(val[1],val[2]):
		unite(val[1],val[2])
		ans+=val[0]
		cnt+=1

print ans