Problem:
 Score : 500 points    Problem Statement There are N towns on a plane. The i -th town is located at the coordinates (x_i,y_i) . There may be more than one town at the same coordinates.  You can build a road between two towns at coordinates (a,b) and (c,d) for a cost of min(|a-c|,|b-d|) yen (the currency of Japan). It is not possible to build other types of roads.  Your objective is to build roads so that it will be possible to travel between every pair of towns by traversing roads. At least how much money is necessary to achieve this?      Constraints  2 ≤ N ≤ 10^5  0 ≤ x_i,y_i ≤ 10^9  All input values are integers.         Input Input is given from Standard Input in the following format:  N  x_1  y_1  x_2  y_2 : x_N  y_N       Output Print the minimum necessary amount of money in order to build roads so that it will be possible to travel between every pair of towns by traversing roads.        Sample Input 1 3
1 5
3 9
7 8      Sample Output 1 3  Build a road between Towns 1 and 2 , and another between Towns 2 and 3 . The total cost is 2+1=3 yen.       Sample Input 2 6
8 3
4 9
12 19
18 1
13 5
7 6      Sample Output 2 8

Solution (Python):
class UnionFind(object):
  def __init__(self,n):
    self.parent={i:i for i in range(1,n+1)}
    self.size={i:1 for i in range(1,n+1)}
  def find(self,a):
    if self.parent[a]!=a:
      self.parent[a]=self.find(self.parent[a])
    return self.parent[a]
  def unite(self,a,b):
    a=self.find(a)
    b=self.find(b)
    if a==b:return
    if self.size[a]>self.size[b]:
      self.size[a]+=self.size[b]
      self.parent[b]=a
    else:
      self.size[b]+=self.size[a]
      self.parent[a]=b
  def isunited(self,a,b):
    return self.find(a)==self.find(b)

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

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

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

o.sort(key=lambda x:x[2])

ans=0
uft=UnionFind(N)
for town1,town2,cost in o:
    if not uft.isunited(town1,town2):
        uft.unite(town1,town2)
        ans+=cost

print(ans)

Solution (Python):
from operator import itemgetter
n = int(input())
x =[]
y =[]
info = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  x.append([i,info[i][0]])
  y.append([i,info[i][1]])

x = sorted(x,key=itemgetter(1))
y = sorted(y,key=itemgetter(1))
tree = []












    
for i in range(n-1):
    tree.append([x[i][0],x[i+1][0],abs(x[i][1]-x[i+1][1])])
    tree.append([y[i][0],y[i+1][0],abs(y[i][1]-y[i+1][1])])


class UnionFind(object):

  def __init__(self, n=1):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ 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 union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x != y:
      if self.rank[x] < self.rank[y]:
        x, y = y, x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
      self.par[y] = x
  
  
  def is_same(self, x, y):
    return self.find(x) == self.find(y)

uf = UnionFind(len(tree))
tree = sorted(tree,key=itemgetter(2))
ans = 0

for i in tree:
  x,y,kyori = i
  if not uf.is_same(x,y):
    uf.union(y,x)
    ans += kyori
print(ans)

Solution (Python):
from operator import itemgetter
n = int(input())
x =[]
y =[]
info = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  x.append([i,info[i][0]])
  y.append([i,info[i][1]])

x = sorted(x,key=itemgetter(1))
y = sorted(y,key=itemgetter(1))
tree = []

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


class UnionFind(object):

  def __init__(self, n=1):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ 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 union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x != y:
      if self.rank[x] < self.rank[y]:
        x, y = y, x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
      self.par[y] = x
  
  
  def is_same(self, x, y):
    return self.find(x) == self.find(y)

uf = UnionFind(len(tree))
tree = sorted(tree,key=itemgetter(2))
ans = 0

for i in tree:
  x,y,kyori = i
  if not uf.is_same(x,y):
    uf.union(y,x)
    ans += kyori
print(ans)

Solution (Python):
from operator import itemgetter
n = int(input())
x =[]
y =[]
info = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  x.append([i,info[i][0]])
  y.append([i,info[i][1]])

x = sorted(x,key=itemgetter(1))
y = sorted(y,key=itemgetter(1))
tree = []












    
for i in range(n-1):
    tree.append([x[i][0],x[i+1][0],abs(x[i][1]-x[i+1][1])])
    tree.append([y[i][0],y[i+1][0],abs(y[i][1]-y[i+1][1])])


class UnionFind(object):

  def __init__(self, n=1):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ 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 union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x != y:
      if self.rank[x] < self.rank[y]:
        x, y = y, x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
      self.par[y] = x
  
  
  def is_same(self, x, y):
    return self.find(x) == self.find(y)

uf = UnionFind(len(tree))
tree = sorted(tree,key=itemgetter(2))
ans = 0

for i in tree:
  x,y,kyori = i
  if not uf.is_same(x,y):
    uf.union(y,x)
    ans += kyori
print(ans)

Solution (Python):
from operator import itemgetter
n = int(input())
x =[]
y =[]
info = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  x.append([i,info[i][0]])
  y.append([i,info[i][1]])

x = sorted(x,key=itemgetter(1))
y = sorted(y,key=itemgetter(1))
tree = []












    
for i in range(n-1):
    tree.append([x[i][0],x[i+1][0],abs(x[i][1]-x[i+1][1])])
    tree.append([y[i][0],y[i+1][0],abs(y[i][1]-y[i+1][1])])


class UnionFind(object):

  def __init__(self, n=1):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ 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 union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x != y:
      if self.rank[x] < self.rank[y]:
        x, y = y, x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
      self.par[y] = x
  
  
  def is_same(self, x, y):
    return self.find(x) == self.find(y)

uf = UnionFind(len(tree))
tree = sorted(tree,key=itemgetter(2))
ans = 0

for i in range(len(tree)):
  if not uf.is_same(tree[i][0],tree[i][1]):
    uf.union(tree[i][0],tree[i][1])
    ans +=tree[i][2]
print(ans)

Solution (Python):


from heapq import heappush, heappop, heapify
n=int(input())
G=[[]for i in range(n)]
d=[]
for i in range(n):
    a,b=map(int,input().split())
    d.append((a,b,i))
d=sorted(d,key=lambda x:x[0])
for i in range(n-1):
    G[d[i][2]].append((d[i+1][0]-d[i][0],d[i+1][2]))
    G[d[i+1][2]].append((d[i+1][0]-d[i][0],d[i][2]))
d=sorted(d,key=lambda x:x[1])
for i in range(n-1):
    G[d[i][2]].append((d[i+1][1]-d[i][1],d[i+1][2]))
    G[d[i+1][2]].append((d[i+1][1]-d[i][1],d[i][2]))
used = [0 for i in range(n)]
que = [(c, w) for c, w in G[0]]
used[0] = 1
heapify(que)

ans = 0
while que:
    cv, v = heappop(que)
    if used[v]:
        continue
    used[v] = 1
    ans += cv
    for c, w in G[v]:
        if used[w]:
            continue
        heappush(que, (c, w))
print(ans)

Solution (Python):
n=int(input())
points=[[i]+list(map(int,input().split())) for i in range(n)]
 
edges=[]
points.sort(key=lambda x: x[1])
for i in range(n-1):
    n1,x1,y1=points[i]
    n2,x2,y2=points[i+1]
    edges.append([n1,n2,x2-x1])
points.sort(key=lambda y: y[2])
for i in range(n-1):
    n1,x1,y1=points[i]
    n2,x2,y2=points[i+1]
    edges.append([n1,n2,y2-y1])

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 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)
edges.sort(key=lambda c: c[2], reverse=True)
ans=0
i=0


while i!=n-1:
    x,y,cost=edges.pop()
    if not uf.same_check(x,y):
        ans+=cost
        uf.union(x,y)
        i+=1
print(ans)

Solution (Python):
n = int(input())
xys = [list(map(int, input().split())) + [i] for i in range(n)]
edges = []
xys.sort()
for i in range(n - 1):
    x1, y1, index1 = xys[i]
    x2, y2, index2 = xys[i + 1]
    edges.append((x2 - x1, index1, index2))

xys.sort(key=lambda x:x[1])
for i in range(n - 1):
    x1, y1, index1 = xys[i]
    x2, y2, index2 = xys[i + 1]
    edges.append((y2 - y1, index1, index2))

parent = [i for i in range(n)]
def find(x):
    if x == parent[x]:return x
    parent[x] = find(parent[x])
    return parent[x]

edges.sort()
ans = 0
for cost, index1, index2 in edges:
    p1, p2 = find(index1), find(index2)
    if p1 != p2:
        parent[p1] = p2
        ans += cost
print(ans)

Solution (Python):
from operator import itemgetter
import heapq
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(key=itemgetter(0))
Y.sort(key=itemgetter(0))

import sys
sys.setrecursionlimit(10**6)


class UnionFind(object):

    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
        else:
            return False
u = UnionFind(N)
q = []
for i in range(N-1):
    q.append((X[i+1][0]-X[i][0], X[i+1][1], X[i][1]))
    q.append((Y[i+1][0]-Y[i][0], Y[i+1][1], Y[i][1]))
q.sort(key=itemgetter(0))
ans = 0
for elem in q:
    cost, a, b = elem
    if u.union(a, b):
        ans += cost
print(ans)

Solution (Python):
from operator import itemgetter
import heapq
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(key=itemgetter(0))
Y.sort(key=itemgetter(0))
G = [[] for _ 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 = []
heapq.heapify(q)
for elem in G[0]:
    heapq.heappush(q, elem)
used = [False] * N
used[0] = True
ans = 0
while q:
    res = heapq.heappop(q)
    cost, nq = res
    if not used[nq]:
        used[nq] = True
        ans += cost
        for elem in G[nq]:
            heapq.heappush(q, elem)
print(ans)

Solution (Python):
from operator import itemgetter
import heapq
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(key=itemgetter(0))
Y.sort(key=itemgetter(0))
G = [[] for _ 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 = []
heapq.heapify(q)
for elem in G[0]:
    heapq.heappush(q, elem)
used = [False] * N
used[0] = True
ans = 0
while q:
    res = heapq.heappop(q)
    cost, nq = res
    if not used[nq]:
        used[nq] = True
        ans += cost
        for elem in G[nq]:
            heapq.heappush(q, elem)
print(ans)

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

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

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

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

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


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

x_order = sorted(ixy, key=lambda x: x[1])
y_order = sorted(ixy, key=lambda x: x[2])

edge = []

for i in range(1, N):
    pre_i1, pre_x1, pre_y1 = x_order[i - 1]
    i1, x1, y1 = x_order[i]
    edge.append((x1 - pre_x1, pre_i1, i1))
    pre_i2, pre_x2, pre_y2 = y_order[i - 1]
    i2, x2, y2 = y_order[i]
    edge.append((y2 - pre_y2, pre_i2, i2))

edge = sorted(edge, key=lambda x: x[0])
union_find = UnionFind(N)
ans = 0
for e in edge:
    cost, pre_i, i = e
    if union_find.check_same(pre_i, i):
        continue
    else:
        union_find.union(pre_i, i)
        ans += cost
print(ans)

Solution (Python):
import itertools

def find(table, x):
    stack = [x]
    while table[stack[-1]] != stack[-1]:
        stack.append(table[stack[-1]])
    
    for i in stack:
        table[i] = stack[-1]
    return table[x]


def union(table, x1, x2):
    p1 = find(table, x1)
    p2 = find(table, x2)
    table[p2] = p1

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

edges = []
cities = list(range(n))
for j in (0, 1):
    cities.sort(key=lambda city: points[city][j])
    for i in range(n - 1):
        city1, city2 = cities[i], cities[i + 1]
        (x1, y1), (x2, y2) = points[city1], points[city2]
        cost = min(abs(x1 - x2), abs(y1 - y2))
        edges.append((cost, city1, city2))
edges.sort() 

table = list(range(n))
answer = 0
for cost, city1, city2 in edges:
    parent1, parent2 = find(table, city1), find(table, city2)
    if parent1 != parent2:
        answer += cost
        union(table, city1, city2)

print(answer)

Solution (Python):


"""
・最小全域木、Union-Find
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from operator import itemgetter


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 same(self, x, y):
        return self.find(x) == self.find(y)

N = int(input())
X = [[0] * 2 for i in range(N)]
Y = [[0] * 2 for i in range(N)]
for i in range(N):
    x, y = map(int, input().split())
    X[i][0] = x
    X[i][1] = i
    Y[i][0] = y
    Y[i][1] = i

X.sort(key=itemgetter(0))
Y.sort(key=itemgetter(0))

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

edges.sort(key=itemgetter(2))

uf = UnionFind(N)
ans = 0
grp = N

for x, y, w in edges:
    if not uf.same(x, y):
        uf.union(x, y)
        ans += w
        grp -= 1
    
    if grp == 1:
        break
print(ans)

Solution (Python):


"""
・最小全域木、Union-Find
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from operator import itemgetter


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 same(self, x, y):
        return self.find(x) == self.find(y)

N = int(input())
X = [[0] * 2 for i in range(N)]
Y = [[0] * 2 for i in range(N)]
for i in range(N):
    x, y = map(int, input().split())
    X[i][0] = x
    X[i][1] = i
    Y[i][0] = y
    Y[i][1] = i

X.sort()
Y.sort()

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

edges.sort(key=itemgetter(2))

uf = UnionFind(N)
ans = 0
grp = N

for x, y, w in edges:
    if not uf.same(x, y):
        uf.union(x, y)
        ans += w
        grp -= 1
    
    if grp == 1:
        break
print(ans)

Solution (Python):


import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from operator import itemgetter


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 same(self, x, y):
        return self.find(x) == self.find(y)

N = int(input())
X = [[0] * 2 for i in range(N)]
Y = [[0] * 2 for i in range(N)]
for i in range(N):
    x, y = map(int, input().split())
    X[i][0] = x
    X[i][1] = i
    Y[i][0] = y
    Y[i][1] = i

X.sort()
Y.sort()

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

edges.sort(key=itemgetter(2))

uf = UnionFind(N)
ans = 0

for x, y, w in edges:
    if not uf.same(x, y):
        uf.union(x, y)
        ans += w
print(ans)

Solution (Python):


import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from operator import itemgetter


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 same(self, x, y):
        return self.find(x) == self.find(y)

N = int(input())
X = [[0] * 2 for i in range(N)]
Y = [[0] * 2 for i in range(N)]
for i in range(N):
    x, y = map(int, input().split())
    X[i][0] = x
    X[i][1] = i
    Y[i][0] = y
    Y[i][1] = i

X.sort()
Y.sort()

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

edges.sort(key=itemgetter(2))

uf = UnionFind(N)
ans = 0

for x, y, w in edges:
    if not uf.same(x, y):
        uf.union(x, y)
        ans += w
print(ans)

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

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


adj = [[] for i in range(N)]
for xy in [1, 2]:
    towns.sort(key=lambda t: t[xy])
    for i in range(N - 1):
        t1 = towns[i][0]
        t2 = towns[i + 1][0]
        cost = min(abs(towns[i + 1][1] - towns[i][1]), abs(towns[i + 1][2] - towns[i][2]))
        adj[t1].append((t2, cost))
        adj[t2].append((t1, cost))


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

done = set()
ans = 0
while pq:
    cost, v_now = heapq.heappop(pq)

    if v_now in done:
        continue

    ans += cost
    done.add(v_now)

    if len(done) == N:
        break

    for v, c in adj[v_now]:
        if v not in done:
            heapq.heappush(pq, (c, v))

print(ans)

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


Edges = []
Points.sort(key=lambda p: p[1])
for i in range(N - 1):
    n1, x1, y1 = Points[i]
    n2, x2, y2 = Points[i + 1]
    Edges.append([n1, n2, x2 - x1])

Points.sort(key=lambda p: p[2])
for i in range(N - 1):
    n1, x1, y1 = Points[i]
    n2, x2, y2 = Points[i + 1]
    Edges.append([n1, n2, y2 - y1])


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)
Edges.sort(key=lambda e: e[2], reverse=True)
MST_cost = 0
i = 0



while i != N - 1:
    x, y, cost = Edges.pop()
    
    if not uf.same_check(x, y):
        MST_cost += cost
        uf.union(x, y)
        i += 1

print(MST_cost)

Solution (Python):
import numpy as np

N = int(input())
T = [[int(_) for _ in input().split()] for i in range(N)]


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 x != 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 same_check(self, x, y):
        return self.find(x) == self.find(y)


E = []
indices_x = np.argsort([x for x, y in T])
indices_y = np.argsort([y for x, y in T])

for i in range(N - 1):
    a, _ = T[indices_x[i]]
    c, _ = T[indices_x[i + 1]]
    E.append((indices_x[i], indices_x[i + 1], abs(a - c)))

    _, b = T[indices_y[i]]
    _, d = T[indices_y[i + 1]]
    E.append((indices_y[i], indices_y[i + 1], abs(b - d)))

uf = UnionFind(N)
ans = 0
for i, j, cost in sorted(E, key=lambda x: x[2]):
    if uf.same_check(i, j):
        continue

    uf.union(i, j)
    ans += cost

print(ans)

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

class UnionFind:
    def __init__(self, n: int) -> None:
        
        self.nodes = [-1]*n
 
    def find_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find_root(self.nodes[x])
            return self.nodes[x]
 
    def unite(self, x: int, y: int) -> None:
        x, y = self.find_root(x), self.find_root(y)
        
        if (x != y):
            if (x < y):
                self.nodes[y] += self.nodes[x]
                self.nodes[x] = y
            else:
                self.nodes[x] += self.nodes[y]
                self.nodes[y] = x
        
    def is_same(self, x: int, y: int) -> bool:
        return self.find_root(x) == self.find_root(y)

from operator import itemgetter

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


G_sorted_by_x = sorted(G, key=itemgetter(1))
G_sorted_by_y = sorted(G, key=itemgetter(2))
R = []
for i in range(N-1):
    i0, x0, _ = G_sorted_by_x[i]
    i1, x1, _ = G_sorted_by_x[i+1]
    R.append((x1-x0, i0, i1))
    i0, _, y0 = G_sorted_by_y[i]
    i1, _, y1 = G_sorted_by_y[i+1]
    R.append((y1-y0, i0, i1))

R_sorted_by_cost = sorted(R, key=itemgetter(0))



uf = UnionFind(N)
total_cost = 0
for cost, i, j in R_sorted_by_cost:
    if (not uf.is_same(i, j)):
        uf.unite(i, j)
        total_cost += cost
    
print(total_cost)

Solution (Python):
from collections import defaultdict 
  

class Graph: 
  
    def __init__(self,vertices): 
        self.V= vertices 
        self.graph = [] 
                                
          
   
    
    def addEdge(self,u,v,w): 
        self.graph.append([u,v,w]) 
  
    
    
    def find(self, parent, i): 
        if parent[i] == i: 
            return i 
        return self.find(parent, parent[i]) 
  
    
    
    def union(self, parent, rank, x, y): 
        xroot = self.find(parent, x) 
        yroot = self.find(parent, y) 
  
        
        
        if rank[xroot] < rank[yroot]: 
            parent[xroot] = yroot 
        elif rank[xroot] > rank[yroot]: 
            parent[yroot] = xroot 
  
        
        
        else : 
            parent[yroot] = xroot 
            rank[xroot] += 1
  
    
        
    def KruskalMST(self): 
  
        result =[] 
  
        i = 0 
        e = 0 
  
            
                
                
                
        self.graph =  sorted(self.graph,key=lambda item: item[2]) 
  
        parent = [] ; rank = [] 
  
        
        for node in range(self.V): 
            parent.append(node) 
            rank.append(0) 
      
        
        while e < self.V -1 : 
  
            
                    
            u,v,w =  self.graph[i] 
            i = i + 1
            x = self.find(parent, u) 
            y = self.find(parent ,v) 
  
            
                        
                        
            if x != y: 
                e = e + 1     
                result.append([u,v,w]) 
                self.union(parent, rank, x, y)             
            
  
        
        ans = 0
        for u,v,weight  in result:
        	ans += weight
        print ans

n = input()
arr = []
for i in range(n):
	x,y = map(int,raw_input().split())
	arr.append((x,y,i))
arr1 = sorted(arr)

g = Graph(n)
for i in range(n-1):
	g.addEdge(arr1[i][2],arr1[i+1][2],arr1[i+1][0]-arr1[i][0])
arr2 = sorted(arr,key = lambda x : x[1])
for i in range(n-1):
	g.addEdge(arr2[i][2],arr2[i+1][2],arr2[i+1][1]-arr2[i][1])
g.KruskalMST()

Solution (Python):


import heapq
V=int(input())
vlist=[]
eque=[]
for i in range(V):
    x,y=map(int,input().split())
    vlist.append([i,x,y])

vlist.sort(key=lambda x:x[1])
for i in range(V-1):
    heapq.heappush(eque,[vlist[i+1][1]-vlist[i][1],vlist[i][0],vlist[i+1][0]])

vlist.sort(key=lambda x:x[2])
for i in range(V-1):
    heapq.heappush(eque,[vlist[i+1][2]-vlist[i][2],vlist[i][0],vlist[i+1][0]])



par=[]
rank=[]
def init(a): 
    for i in range(a):
        par.append(i)
        rank.append(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 rank[x]==rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1
    return
def same(x,y): 
    return find(x)==find(y)

init(V) 

res=0 
while len(eque)!=0:
    te=heapq.heappop(eque)
    cost,u,v=te[0],te[1],te[2]
    if same(u,v): 
        continue
    res+=cost
    unite(u,v) 

print(res)

Solution (Python):
N = int(input())
Cx = [[0, 0] for i in range(N)]
Cy = [[0, 0] for i in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  Cx[i] = [x, i]
  Cy[i] = [y, i]
Cx.sort()
Cy.sort()
Qx = sorted([[Cx[i + 1][0] - Cx[i][0], Cx[i][1], Cx[i + 1][1]] for i in range(N - 1)])
Qy = sorted([[Cy[i + 1][0] - Cy[i][0], Cy[i][1], Cy[i + 1][1]] for i in range(N - 1)])
R = [i for i in range(N)]
def root(n):
  if R[n] == n:
    return n
  else:
    R[n] = root(R[n])
    return R[n]
cnt = 0
cost = 0
x = 0
y = 0
while cnt < N - 1:
  if Qx[x][0] <= Qy[y][0]:
    q = Qx[x]
    x += 1
  else:
    q = Qy[y]
    y += 1
  r1 = root(q[1])
  r2 = root(q[2])
  if r1 != r2:
    R[r2] = q[1]
    cost += q[0]
    cnt += 1
print(cost)