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

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

v = []

xy.sort(key=lambda x: x[1])
pi, px, py = xy[0]
for i in range(1, N) :
    ci, cx, cy = xy[i]
    v.append((min(cx-px, abs(cy-py)), pi, ci))
    pi, px, py = ci, cx, cy
    
xy.sort(key=lambda x: x[2])
pi, px, py = xy[0]
for i in range(1, N) :
    ci, cx, cy = xy[i]
    v.append((min(cy-py, abs(cx-px)), pi, ci))
    pi, px, py = ci, cx, cy

class UnionFind() :
    def __init__(self, N) :
        self.par = [-1] * N
        
    def root(self, x) :
        while self.par[x] >= 0:
            x = self.par[x]
        return x

    def unite(self, x,y) :
        rx = self.root(x)
        ry = self.root(y)

        if rx != ry :
            if self.par[rx] > self.par[ry] :
                self.par[rx] = ry
            else :
                if self.par[rx] == self.par[ry] :
                    self.par[rx] -= 1
                self.par[ry] = rx
    
    def same(self, x, y) :
        return self.root(x) == self.root(y)

uf = UnionFind(N)
counter = 0
s = 0

v.sort()
for v_ in v :
    c, a, b = v_
    if not uf.same(a, b) :
        uf.unite(a, b)
        counter += 1
        s += c
        if counter == N - 1 :
            break
            
print(s)

Solution (Python):
from scipy.sparse import*;N=int(input());Z=[[i]+list(map(int,input().split()))for i in range(N)]
def X(k):Z.sort(key=lambda a:a[k]);return{(min(abs(b-e),abs(c-f)),a,d)for(a,b,c),(d,e,f)in zip(Z,Z[1:])}
d,*x=zip(*X(1)|X(2));print(int(csgraph.minimum_spanning_tree(csr_matrix((d,x),(N,N))).sum()))

Solution (Python):
from scipy.sparse import*;N=int(input());Z=[[i]+list(map(int,input().split()))for i in range(N)];P=set()
for j in[1,2]:
 Z.sort(key=lambda a:a[j])
 for i in range(1,N):a,b,c=Z[i-1];d,e,f=Z[i];P.add((min(abs(e-b),abs(f-c)),a,d))
d,i,j=zip(*P);print(int(csgraph.minimum_spanning_tree(csr_matrix((d,(i,j)),(N,N))).sum()))

Solution (Python):
from scipy.sparse import*;N=int(input());Z=[[i]+list(map(int,input().split()))for i in range(N)];P=set()
for j in[1,2]:
 Z.sort(key=lambda a:a[j])
 for i in range(1,N):
  a,b,c=Z[i-1]
  d,e,f=Z[i]
  P.add((min(abs(e-b),abs(f-c)),a,d))
d,i,j=zip(*P);print(int(csgraph.minimum_spanning_tree(csr_matrix((d,(i,j)),(N,N))).sum()))

Solution (Python):
from scipy.sparse import*;N=int(input());Z=[[i]+list(map(int,input().split()))for i in range(N)];P=set()
for j in[1,2]:Z.sort(key=lambda a:a[j]);P|={(min(abs(Z[i][1]-Z[i-1][1]),abs(Z[i][2]-Z[i-1][2])),Z[i-1][0],Z[i][0])for i in range(1,N)}
d,i,j=zip(*P);print(int(csgraph.minimum_spanning_tree(csr_matrix((d,(i,j)),(N,N))).sum()))

Solution (Python):
from scipy.sparse import *;N=int(input());Z=[[i]+list(map(int,input().split())) for i in range(N)];P=set()
for j in [1,2]:Z.sort(key=lambda a:a[j]);P|={(min(abs(Z[i][1]-Z[i-1][1]),abs(Z[i][2]-Z[i-1][2])),Z[i-1][0],Z[i][0]) for i in range(1,N)}
d,i,j=zip(*P);print(int(csgraph.minimum_spanning_tree(csr_matrix((d,(i,j)),(N,N))).sum()))

Solution (Python):
from scipy.sparse import *;N=int(input());Z=[[i]+list(map(int,input().split())) for i in range(N)];P=set()
for j in [1,2]:
 Z.sort(key=lambda a:a[j])
 for i in range(1,N):
  a,b,c=Z[i-1]
  d,e,f=Z[i]
  P.add((min(abs(e-b),abs(f-c)),a,d))
d,i,j=zip(*P);print(int(csgraph.minimum_spanning_tree(csr_matrix((d,(i,j)),(N,N))).sum()))

Solution (Python):
from scipy.sparse import *
N=int(input())
Z=[[i]+list(map(int,input().split())) for i in range(N)]
P=set()
for j in [1,2]:
 Z.sort(key=lambda a:a[j])
 for i in range(1,N):
  a,b,c=Z[i-1]
  d,e,f=Z[i]
  P.add((min(abs(e-b),abs(f-c)),a,d))
d,i,j=zip(*P)
print(int(csgraph.minimum_spanning_tree(csr_matrix((d,(i,j)),(N,N))).sum()))

Solution (Python):
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import coo_matrix

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

P = set()
for j in [1, 2]:
  iXY.sort(key=lambda a: a[j])
  for i in range(1, N):
    i0, x0, y0 =  iXY[i - 1]
    i1, x1, y1 =  iXY[i]
    P.add((min(abs(x1 - x0), abs(y1 - y0)), i0, i1))

d, i, j = zip(*P)
G = coo_matrix((d, (i, j)), shape=(N, N))
mst = minimum_spanning_tree(G)
print(int(mst.sum()))

Solution (Python):
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix

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

P = set()
for j in [1, 2]:
  iXY.sort(key=lambda a: a[j])
  for i in range(1, N):
    i0, x0, y0 =  iXY[i - 1]
    i1, x1, y1 =  iXY[i]
    P.add((min(abs(x1 - x0), abs(y1 - y0)), i0, i1))

d, i, j = zip(*P)
G = csr_matrix((d, (i, j)), shape=(N, N))
mst = minimum_spanning_tree(G)
print(int(mst.sum()))

Solution (Python):
from collections import defaultdict
from heapq import heappush, heappop

N = int(input())
Vx = [None] * N
Vy = [None] * N
for i in range(N):
    x, y = map(int, input().split())
    Vx[i] = (i, x)
    Vy[i] = (i, y)
Vx.sort(key=lambda v: v[1])
Vy.sort(key=lambda v: v[1])
E = defaultdict(list)
for j in range(N-1):
    E[Vx[j][0]].append((Vx[j+1][1] - Vx[j][1], Vx[j+1][0]))
    E[Vx[j+1][0]].append((Vx[j+1][1] - Vx[j][1], Vx[j][0]))
    E[Vy[j][0]].append((Vy[j + 1][1] - Vy[j][1], Vy[j + 1][0]))
    E[Vy[j+1][0]].append((Vy[j + 1][1] - Vy[j][1], Vy[j][0]))
used = [False] * N


ans = 0
q = []
heappush(q, (0, 0))
while q:
    dist, now = heappop(q)
    if used[now]:
        continue
    used[now] = True
    ans += dist
    for w, nxt in E[now]:
        if not used[nxt]:
            heappush(q, (w, nxt))
print(ans)

Solution (Python):
import heapq

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

G = [set() for _ in range(N)]
for k in [1, 2]:
  iXY.sort(key=lambda a: a[k])
  for i in range(1, N):
    i0 = iXY[i - 1][0]
    i1 = iXY[i][0]
    G[i0].add((i1))
    G[i1].add((i0))

Q = [(0, 0)]
B = set()
a = 0
iXY.sort()

while True:
  d, v = heapq.heappop(Q)
  while v in B:
     d, v = heapq.heappop(Q)
  a += d
  B.add(v)
  if len(B) == N:
    break
  for i in G[v]:
    if i not in B:
      heapq.heappush(Q, (min(abs(iXY[v][1] - iXY[i][1]), abs(iXY[v][2] - iXY[i][2])), i))
print(a)

Solution (Python):
import heapq

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

iXY.sort(key=lambda a: a[1])
for i in range(1, N):
  i0, x0, y0 = iXY[i - 1]
  i1, x1, y1 = iXY[i]
  G[i0].add((i1))
  G[i1].add((i0))

iXY.sort(key=lambda a: a[2])
for i in range(1, N):
  i0, x0, y0 = iXY[i - 1]
  i1, x1, y1 = iXY[i]
  G[i0].add((i1))
  G[i1].add((i0))

Q = [(0, 0)]
B = set()
a = 0
iXY.sort()

while True:
  d, v = heapq.heappop(Q)
  while v in B:
     d, v = heapq.heappop(Q)
  a += d
  B.add(v)
  if len(B) == N:
    break
  for i in G[v]:
    if i not in B:
      heapq.heappush(Q, (min(abs(iXY[v][1] - iXY[i][1]), abs(iXY[v][2] - iXY[i][2])), i))
print(a)

Solution (Python):

import sys
import heapq
INF = float("inf")


class Graph(object):

    def __init__(self, N):
        self.N = N
        self.E = []

    def add_edge(self, edge):
        """
        args:
          edge : (from_, to_, weight)
        """
        s, t, w = edge
        if s > t:
            s, t = t, s
        self.E.append([s, t, w])


class UnionFind(object):
    """UnionFind木
    """

    def __init__(self, N):
        self.tree = list(range(N))

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

    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:
            self.tree[x] = y


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

    XYN = sorted(zip(x, y, range(N)))
    YXN = sorted(zip(y, x, range(N)))
    edges = []
    for i in range(N-1):
        (x1, y1, n1), (x2, y2, n2) = XYN[i:i+2]
        heapq.heappush(edges, [min(abs(x1-x2), abs(y1-y2)), n1, n2])
        (y1, x1, n1), (y2, x2, n2) = YXN[i:i+2]
        heapq.heappush(edges, [min(abs(x1-x2), abs(y1-y2)), n1, n2])
    tot, counter = 0, 0
    group = UnionFind(N)
    while len(edges) > 0 and counter <= N:
        w, f, t = heapq.heappop(edges)
        if not group.same(f, t):
            tot += w
            counter += 1
            group.unite(f, t)

    print(tot)
    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):

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

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

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

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

Krus = Kruskal_UnionFind(N)

xy.sort(key=lambda x: x[0])
x_cost = [[xy[i-1][2], xy[i][2], abs(xy[i-1][0] - xy[i][0])] for i in range(1, N)]
xy.sort(key=lambda x: x[1])
y_cost = [[xy[i-1][2], xy[i][2], abs(xy[i-1][1] - xy[i][1])] for i in range(1, N)]

for i in range(N-1):
    a, b, w = x_cost[i]
    Krus.add(a, b, w)
    a, b, w = y_cost[i]
    Krus.add(a, b, w)

ans = Krus.Kruskal()

print(ans)

Solution (Python):
import heapq

N = int(input())
cities = [0 for _ in range(N)]

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

edges = [[] for _ in range(N)]

cities.sort(key=lambda A : A[1])
for i in range(N - 1):
    a, xFrom, yFrom = cities[i]
    b, xTo, yTo = cities[i + 1]
    cost = min(abs(xFrom - xTo), abs(yFrom - yTo))

    edges[a].append((cost, b))
    edges[b].append((cost, a))

cities.sort(key=lambda A : A[2])
for i in range(N - 1):
    a, xFrom, yFrom = cities[i]
    b, xTo, yTo = cities[i + 1]
    cost = min(abs(xFrom - xTo), abs(yFrom - yTo))

    edges[a].append((cost, b))
    edges[b].append((cost, a))

vertex = set([0])
newEdge = []
que = []

for cost, to in edges[0]:
    heapq.heappush(que, (cost, to))

ans = 0
while len(vertex) < N:
    cost, now = heapq.heappop(que)
    if now in vertex:
        continue
    ans += cost
    vertex.add(now)
    for c, to in edges[now]:
        if not to in vertex:
            heapq.heappush(que, (c, to))

print(ans)

Solution (Python):
from collections import defaultdict
from heapq import heappush, heappop

N = int(input())
xy = [[int(i) for i in input().split()] for j 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])
neighbours = 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]
    neighbours[x1].append((x2, xd))
    neighbours[x2].append((x1, xd))
    neighbours[y1].append((y2, yd))
    neighbours[y2].append((y1, yd))

is_used = [0] * N
h = []
heappush(h, (0, 0))
result = 0

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

print(result)

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heapify
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n = int(sys.stdin.readline())
par = [i for i in range(n)]
rank = [0]*n
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def union(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

x,y = [],[]
for i in range(n):
    a,b = map(int,sys.stdin.readline().split())
    x.append((a,i))
    y.append((b,i))
x.sort()
y.sort()
h = []
heapify(h)
for i in range(n-1):
    x1, j1 = x[i]
    x2, j2 = x[i+1]
    y1, k1 = y[i]
    y2, k2 = y[i+1]
    heappush(h,(x2-x1, j1, j2))
    heappush(h,(y2-y1, k1, k2))
ans = 0
x = 0
while h:
    w,s,t = heappop(h)
    if find(s) != find(t):
        x += 1
        union(s,t)
        ans += w
    if x == n-1:
        break
print(ans)

Solution (Python):
class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * N 
    
    

    
    def root(self, A):
        if self.parent[A-1] < 0: 
            return A
        self.parent[A-1] = self.root(self.parent[A-1]) 
        return self.parent[A-1] 

    
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    
    def connect(self, A, B):
        A = self.root(A) 
        B = self.root(B) 
        if A == B: 
            return False
        
        
        if self.size(A) < self.size(B): 
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] 
        self.parent[B-1] = A 
        return True
    
    def same(self, A, B):
        if self.root(A) == self.root(B):
            return True
        else:
            return False

N = int(input())

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

edge = []
e_append = edge.append
lst.sort(key = lambda x: x[0])
for i in range(1, N):
    e_append([lst[i-1][2], lst[i][2], min(abs(lst[i-1][0]-lst[i][0]), abs(lst[i-1][1]-lst[i][1]))])

lst.sort(key = lambda x: x[1])
for i in range(1, N):
    e_append([lst[i-1][2], lst[i][2], min(abs(lst[i-1][0]-lst[i][0]), abs(lst[i-1][1]-lst[i][1]))])

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

uni = UnionFind(N)
ans = 0
for i in edge:
    if not uni.same(i[0], i[1]): 
        uni.connect(i[0], i[1])
        ans += i[2]
print (ans)

Solution (Python):
class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * N 
    
    

    
    def root(self, A):
        if self.parent[A-1] < 0: 
            return A
        self.parent[A-1] = self.root(self.parent[A-1]) 
        return self.parent[A-1] 

    
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    
    def connect(self, A, B):
        A = self.root(A) 
        B = self.root(B) 
        if A == B: 
            return False
        
        
        if self.size(A) < self.size(B): 
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] 
        self.parent[B-1] = A 
        return True
    
    def same(self, A, B):
        if self.root(A) == self.root(B):
            return True
        else:
            return False

N = int(input())

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

edge = []
e_append = edge.append
lst.sort(key = lambda x: x[0])
for i in range(1, N):
    e_append([lst[i-1][2], lst[i][2], min(abs(lst[i-1][0]-lst[i][0]), abs(lst[i-1][1]-lst[i][1]))])

lst.sort(key = lambda x: x[1])
for i in range(1, N):
    e_append([lst[i-1][2], lst[i][2], min(abs(lst[i-1][0]-lst[i][0]), abs(lst[i-1][1]-lst[i][1]))])

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

uni = UnionFind(N)
ans = 0
for i in edge:
    if not uni.same(i[0], i[1]): 
        uni.connect(i[0], i[1])
        ans += i[2]
print (ans)

Solution (Python):
class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * N 
    
    

    
    def root(self, A):
        if self.parent[A-1] < 0: 
            return A
        self.parent[A-1] = self.root(self.parent[A-1]) 
        return self.parent[A-1] 

    
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    
    def connect(self, A, B):
        A = self.root(A) 
        B = self.root(B) 
        if A == B: 
            return False
        
        
        if self.size(A) < self.size(B): 
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] 
        self.parent[B-1] = A 
        return True
    
    def same(self, A, B):
        if self.root(A) == self.root(B):
            return True
        else:
            return False

N = int(input())

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

edge = []
e_append = edge.append
lst.sort(key = lambda x: x[0])
for i in range(1, N):
    e_append([lst[i-1][2], lst[i][2], min(abs(lst[i-1][0]-lst[i][0]), abs(lst[i-1][1]-lst[i][1]))])

lst.sort(key = lambda x: x[1])
for i in range(1, N):
    e_append([lst[i-1][2], lst[i][2], min(abs(lst[i-1][0]-lst[i][0]), abs(lst[i-1][1]-lst[i][1]))])

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

uni = UnionFind(N)
ans = 0
for i in edge:
    if not uni.same(i[0], i[1]): 
        uni.connect(i[0], i[1])
        ans += i[2]
print (ans)

Solution (Python):
class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * N 
    
    

    
    def root(self, A):
        if self.parent[A-1] < 0: 
            return A
        self.parent[A-1] = self.root(self.parent[A-1]) 
        return self.parent[A-1] 

    
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    
    def connect(self, A, B):
        A = self.root(A) 
        B = self.root(B) 
        if A == B: 
            return False
        
        
        if self.size(A) < self.size(B): 
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] 
        self.parent[B-1] = A 
        return True
    
    def same(self, A, B):
        if self.root(A) == self.root(B):
            return True
        else:
            return False

N = int(input())

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

edge = []
lst.sort(key = lambda x: x[0])
for i in range(1, N):
    edge.append([lst[i-1][2], lst[i][2], min(abs(lst[i-1][0]-lst[i][0]), abs(lst[i-1][1]-lst[i][1]))])

lst.sort(key = lambda x: x[1])
for i in range(1, N):
    edge.append([lst[i-1][2], lst[i][2], min(abs(lst[i-1][0]-lst[i][0]), abs(lst[i-1][1]-lst[i][1]))])

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

uni = UnionFind(N)
ans = 0
for i in edge:
    if not uni.same(i[0], i[1]): 
        uni.connect(i[0], i[1])
        ans += i[2]
print (ans)

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
INF=10**10
d=[INF]*n
ans=0
d[0]=0
heapq.heappush(q,(0,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]]:
            if i[0]<d[i[1]]:
                d[i[1]]=i[0]
                heapq.heappush(q,i)
print(ans)

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

xs = []
ys = []

for i, (x,y) in enumerate(towns):
    xs.append((x, i))
    ys.append((y, i))

xs.sort()
ys.sort()

es = []
for (x1, i1), (x2, i2) in zip(xs, xs[1:]):
    es.append((x2-x1, i1, i2)) 

for (y1, i1), (y2, i2) in zip(ys, ys[1:]):
    es.append((y2-y1, i1, i2)) 
es.sort()

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


ans = 0
uf = UnionFind(N)
for d,a,b in es:
    
    if uf.is_same(a,b):
        continue
    uf.unite(a,b) 
    ans += d
print(ans)

Solution (Python):

import sys
import math
from collections import defaultdict


sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))



class UF(object):
  def __init__(self, n=1):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ in range(n)]
    self.size = [1 for _ in range(n)]

  def find(self, x):
    """
    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 と 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
      self.size[x] += self.size[y]

  def is_same(self, x, y):
    """
    x と y が同じグループか否か
    """
    return self.find(x) == self.find(y)

  def get_size(self, x):
    """
    x が属するグループの要素数
    """
    x = self.find(x)
    return self.size[x]

N = I()
x = []
y = []

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

xsort = sorted(x,lambda a:a[0])
ysort = sorted(y,lambda a:a[0])

graph = []
for i in range(N-1):
  graph.append([min(abs(xsort[i][0]-xsort[i+1][0]),abs(y[xsort[i][1]][0]-y[xsort[i+1][1]][0])), \
                xsort[i][1],xsort[i+1][1]])
  graph.append([min(abs(ysort[i][0]-ysort[i+1][0]),abs(x[ysort[i][1]][0]-x[ysort[i+1][1]][0])), \
                ysort[i][1],ysort[i+1][1]])

ans = 0
uf = UF(N)
graph.sort()
for w in graph:
  if not uf.is_same(w[1],w[2]):
    uf.union(w[1],w[2])
    ans += w[0]

print(ans)

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


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

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

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

    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

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


def main():
    N = int(input())
    x_list = []
    y_list = []
    x_app = x_list.append
    y_app = y_list.append
    for i in range(N):
        x, y = map(int, input().split())
        x_app([x, i])
        y_app([y, i])

    x_list.sort()
    y_list.sort()
    adj = []
    adj_app = adj.append
    for i in range(N-1):
        adj_app([x_list[i + 1][0] - x_list[i][0], x_list[i + 1][1], x_list[i][1]])
        adj_app([y_list[i + 1][0] - y_list[i][0], y_list[i + 1][1], y_list[i][1]])

    adj.sort(key=lambda x: x[0])
    uf = UnionFind(N)
    ans = 0
    for edge in adj:
        if not uf.isSameGroup(edge[1], edge[2]):
            ans += edge[0]
            uf.unite(edge[1], edge[2])
    print(ans)


if __name__ == '__main__':
    main()

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


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

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if (x == y):
            return False
        if (self.size(x) < self.size(y)):
            self.parent[y] += self.parent[x]
            self.parent[x] = y
        else:
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        return True

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


def main():
    N = int(input())
    x_list = []
    y_list = []
    x_app = x_list.append
    y_app = y_list.append
    for i in range(N):
        x, y = (int(x) for x in input().split())
        x_app([x, i])
        y_app([y, i])

    x_list.sort()
    y_list.sort()
    adj = []
    adj_app = adj.append
    for i in range(N-1):
        adj_app((x_list[i + 1][0] - x_list[i][0], x_list[i + 1][1], x_list[i][1]))
        adj_app((y_list[i + 1][0] - y_list[i][0], y_list[i + 1][1], y_list[i][1]))

    adj.sort(key=lambda x: x[0])
    uf = UnionFind(N)
    ans = 0
    for edge in adj:
        if not uf.same(edge[1], edge[2]):
            ans += edge[0]
            uf.unite(edge[1], edge[2])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


import sys
input = sys.stdin.readline

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

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

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

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

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

def main():
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app((xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app((yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))


    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(N)
    weight = 0

    for edge in edges:
        if not uf.same(edge[0], edge[1]):
            uf.unite(edge[0], edge[1])
            weight+=edge[2]
    print(weight)

if __name__ == '__main__':
    main()

Solution (Python):


import array
import sys
input = sys.stdin.readline

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

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

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

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

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

def main():
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app((xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app((yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))


    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(N)
    weight = 0

    for edge in edges:
        if not uf.same(edge[0], edge[1]):
            uf.unite(edge[0], edge[1])
            weight+=edge[2]
    print(weight)

if __name__ == '__main__':
    main()