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):
from operator import itemgetter
N = int(input())
cities = []

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


edge = []
for k in (itemgetter(1), itemgetter(2)):
    cities.sort(key=k)
    for j in range(N-1):
        d = min(abs(cities[j+1][1]-cities[j][1]),
                abs(cities[j+1][2]-cities[j][2]))
        edge.append((cities[j][0], cities[j+1][0], d))
edge.sort(key=itemgetter(2))


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 Count(self, x):
        return -self.root[self.Find_Root(x)]


uf = UnionFind(N)

ans = 0
for e in edge:
    if not uf.isSameGroup(e[0], e[1]):
        ans += e[2]
        uf.Unite(e[0], e[1])
print(ans)

Solution (Python):
from heapq import *

def find(A, x):
    p = A[x]
    if p == x:
        return x
    a = find(A, p)
    A[x] = a
    return a

def union(A, x, y):
    if find(A, x) < find(A, y):
        bx, by = find(A, x), find(A, y)
    else:
        bx, by = find(A, y), find(A, x)
    A[by] = bx

N = int(input())
X, Y = [], []

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

X.sort()
Y.sort()
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))

V = [i for i in range(N)]
answer = 0
while H:
    w, s, t = heappop(H)
    if find(V, s) != find(V, t):
        union(V, s, t)
        answer += w
print(answer)

Solution (Python):

from heapq import *


def find(A, x):
    p = A[x]
    if p == x:
        return x
    a = find(A, p)
    A[x] = a
    return a


def union(A, x, y):
    if find(A, x) > find(A, y):
        bx, by = find(A, y), find(A, x)
    else:
        bx, by = find(A, x), find(A, y)
    
    A[by] = bx

N = int(input())
X = [(0,0)] * N
Y = [(0,0)] * N

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

answer = 0
V = [i for i in range(N)]

while H:
    w, s, t = heappop(H)
    
    if find(V, s) != find(V, t):
        union(V, s, t)
        answer += w

print(answer)

Solution (Python):
from heapq import *


def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a


def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    
    A[by] = bx

N = int(input())
X = [(0,0)] * N
Y = [(0,0)] * N
E = [(0,0)] * N

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

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

answer = 0
V = [i for i in range(N)]

while H:
    w, s, t = heappop(H)
    
    if find(V, s) != find(V, t):
        union(V, s, t)
        answer += w

print(answer)

Solution (Python):
from heapq import *


def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a


def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    
    A[bx] = bx
    A[by] = bx

N = int(input())
X = [(0,0)] * N
Y = [(0,0)] * N
E = [(0,0)] * N

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

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

answer = 0
V = [i for i in range(N)]

while H:
    w, s, t = heappop(H)
    
    if find(V, s) != find(V, t):
        union(V, s, t)
        answer += w

print(answer)

Solution (Python):
from heapq import *


def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a


def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

N = int(input())
X = [(0,0)] * N
Y = [(0,0)] * N
E = [(0,0)] * N

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

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

answer = 0
V = [i for i in range(N)]

while H:
    w, s, t = heappop(H)
    if find(V, s) != find(V, t):
        union(V, s, t)
        answer += w

print(answer)

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

XY.sort(key=lambda x:(x[0],x[1]))
edges=[]
for i in range(1,n):
  a,b,c,d=XY[i-1][0],XY[i-1][1],XY[i][0],XY[i][1]
  edges.append((abs(a-c),XY[i-1][2],XY[i][2]))
XY.sort(key=lambda x:(x[1],x[0]))
for i in range(1,n):
  a,b,c,d=XY[i-1][0],XY[i-1][1],XY[i][0],XY[i][1]
  edges.append((abs(b-d),XY[i-1][2],XY[i][2]))
  
group=[i for i in range(n)]
def find(x):
  while group[x]!=x:
    x=group[x]
  return x
def union(x,y):
  if find(x)!=find(y):
    group[find(y)]=group[find(x)]=min(find(y),find(x))
    
edges.sort()
ans=0
for c,x,y in edges:
  if find(x)!=find(y):
    union(x,y)
    ans+=c
print(ans)

Solution (Python):
import itertools
import heapq
from heapq import heappush, heappop
global G, inp_x, inp_y

def input_graph(N):
  global G, inp_x, inp_y
  inp_x = []
  inp_y = []
  for i in range(N):
    x, y = map(int, input().split())
    inp_x.append((x, i))
    inp_y.append((y, i))
  inp_x.sort()
  inp_y.sort()
  for i in range(N-1):
    xa = inp_x[i][1]
    xb = inp_x[i+1][1]
    ya = inp_y[i][1]
    yb = inp_y[i+1][1]
    cost_x = abs(inp_x[i][0]-inp_x[i+1][0])
    cost_y = abs(inp_y[i][0]-inp_y[i+1][0])
    G[xa] += [(cost_x, xb)]
    G[xb] += [(cost_x, xa)]
    G[ya] += [(cost_y, yb)]
    G[yb] += [(cost_y, ya)]

  
def prim(V):
  global G, used
  edgelist = []
  for e in G[0]:
    heappush(edgelist, e)
  used[0] = True
  res = 0
  while edgelist:
    minedge = heappop(edgelist)
    if used[minedge[1]]:
      continue 
    v = minedge[1]
    used[v] = True 
    for e in G[v]:
      if not used[e[1]]:
        heappush(edgelist, e)
    res += minedge[0]
  return res

def main():
  global G, used
  N = int(input())
  G = [[] for _ in range(N)]
  used = [False for _ in range(N)]
  input_graph(N)
  print(prim(N))

if __name__ == "__main__":
  main()

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):
from collections import deque
import sys
 
sys.setrecursionlimit(2000000000)
 
n = int(input())
nodes = []
done = [0 for _ in range(n)]
par = {}
for _ in range(n):
    x, y = map(int,input().split())
    nodes.append((x,y))
    par[(x,y)]=(x,y)
nodesx = sorted(nodes)
nodesy = sorted(nodes,key=lambda z:z[1])
s = []
m = len(set(nodes))
for i in range(n-1):
    xcost =nodesx[i+1][0]-nodesx[i][0]
    ycost =nodesy[i+1][1]-nodesy[i][1]
    s.append((xcost,(nodesx[i+1],nodesx[i])))
    s.append((ycost,(nodesy[i+1],nodesy[i])))
s.sort()
s = deque(s)
def root(node,par):
    if node == par[node]:
        return node
    else:
        par[node] =root(par[node],par)
        return par[node]
def unite(node1,node2,par):
    par[root(node1,par)] = root(node2,par)
ans = 0
count =0
while count < m-1 :
    cost,(node1,node2) = s.popleft()
    root1 =root(node1,par)
    root2 =root(node2,par)
    if root1 != root2:
        unite(node1,node2,par)
        ans +=cost
        count += 1
print(ans)

Solution (Python):
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
G = [[]for i in range(n)]   
position = [[]for i in range(n)]
for i in range(n):
    a, b= MAP()
    position[i] = (i, a, b)
position_x = sorted(position, key = lambda x:x[1])
position_y = sorted(position, key = lambda x:x[2])

for i in range(1,n):
    G[position_x[i][0]].append((position_x[i][1]-position_x[i-1][1], position_x[i-1][0]))
    G[position_x[i-1][0]].append((position_x[i][1]-position_x[i-1][1], position_x[i][0]))
    G[position_y[i][0]].append((position_y[i][2]-position_y[i-1][2], position_y[i-1][0]))
    G[position_y[i-1][0]].append((position_y[i][2]-position_y[i-1][2], position_y[i][0]))

def prim(G):
    res = 0
    used = [False]*n
    que = []
    heapq.heapify(que)
    used[0] = True
    for Gs in G[0]:
        heapq.heappush(que,Gs)
    while(len(que) > 0):
        cost, vertex = heapq.heappop(que)
        if used[vertex]:continue
        res += cost
        used[vertex] = True
        for Gs in G[vertex]:
            if used[Gs[1]]:continue
            heapq.heappush(que,Gs)
    return res

print(prim(G))

Solution (Python):
from operator import itemgetter
import heapq
def prim_heap():
  used=[True]*n
  edgelist=[]
  for e in edge[0]:
    heapq.heappush(edgelist,e)
  used[0] = False
  res = 0
  while len(edgelist) != 0:
    minedge = heapq.heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v = minedge[1]
    used[v] = False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,e)
    res += minedge[0]
  return res

import sys
input=sys.stdin.readline
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
edge=[[] for i in range(n)]
l.sort()
for i in range(n):
  l[i]=[l[i][0],l[i][1],i]
for i in range(n-1):
  edge[i].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i+1))
  edge[i+1].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i))
l=sorted(l,key=itemgetter(1))
for i in range(n-1):
  edge[l[i][2]].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i+1][2]))
  edge[l[i+1][2]].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i][2]))
print(prim_heap())

Solution (Python):
def want_p(n):
 
    Q = []
 
    while n != p[n]:
        Q.append(n)
        n = p[n]
 
    for i in Q:
        p[i] = n
 
    return n
 
 
N = int(input())
 
xyi = []
yxi = []
 
for i in range(N):
 
    x,y = map(int,input().split())
    xyi.append([x,y,i])
    yxi.append([y,x,i])
 
xyi.sort()
yxi.sort()
 
line = []
 
 
for i in range(N-1):
 
    line.append([ xyi[i+1][0]-xyi[i][0] , xyi[i][2] , xyi[i+1][2] ])
    line.append([ yxi[i+1][0]-yxi[i][0] , yxi[i][2] , yxi[i+1][2] ])
 
line.sort()
 
p = [i for i in range(N)]
rank = [1] * N
num = [1] * N
ans = 0
 
for j in range(len(line)):
 
    e = line[j]
    cost = e[0]
    a = e[1]
    b = e[2]
 
    ap = want_p(a)
    bp = want_p(b)
 
    if ap != bp:
        ans += cost

        k = num[ap]
        num[ap] += num[bp]
        num[bp] += k

        if num[ap] == N or num[bp] == N:
            break
 
        if rank[ap] > rank[bp]:
            p[bp] = ap
 
        elif rank[ap] == rank[bp]:
            p[bp] = ap
            rank[ap] += 1
 
        else:
            p[ap] = bp
 
print (ans)

Solution (Python):
n=int(input())
a=sorted([[i]+list(map(int,input().split()))for i in range(n)],key=lambda x:x[1])
s=[]
for i in range(n-1):
    s.append((a[i+1][1]-a[i][1],a[i][0],a[i+1][0]))
a=sorted(a,key=lambda x:x[2])
for i in range(n-1):
    s.append((a[i+1][2]-a[i][2],a[i][0],a[i+1][0]))
s.sort()
t=[i for i in range(n)]
def f(x):
    if x==t[x]:
        return x
    t[x]=f(t[x])
    return f(t[x])
c=0
for i,j,h in s:
    j,h=f(j),f(h)
    if h!=j:
        t[j]=h
        c+=i
print(c)

Solution (Python):

import sys
input = sys.stdin.readline
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_check(self, x, y):
        return self.find(x) == self.find(y)

def MST(n, E):
    E = sorted(E, key=lambda x: x[2])
    uf = UnionFind(n)
    ct = 0
    for i,j,cost in E:
      if uf.same_check(i,j):
        continue
      else:
        uf.union(i,j)
        ct += cost
    return ct
  
def solve():
  N = int(input())
  X = []
  append=X.append
  for i in range(N):
    x, y = map(int, input().split())
    append((i, x, y))
 
  F = []
  append = F.append
  Y = sorted(X, key = lambda x: x[1])
  for i in range(len(Y)-1):
    append((Y[i][0], Y[i+1][0], abs(Y[i+1][1]-Y[i][1])))
 
  Y = sorted(X, key = lambda x: x[2])
  for i in range(len(Y)-1):
    append((Y[i][0], Y[i+1][0], abs(Y[i+1][2]-Y[i][2])))
 
  print(MST(N, F))

solve()

Solution (Python):
import heapq
import sys
input = sys.stdin.readline
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_check(self, x, y):
        return self.find(x) == self.find(y)

def solve():
  n = int(input())
  query = []
  xquery = []
  yquery = []
  for i in range(n):
    x,y = (int(i) for i in input().split())
    xquery.append((x,y,i))
    yquery.append((y,x,i))
  xquery = sorted(xquery)
  yquery = sorted(yquery)
  for i in range(n-1):
    tx,ty,place = xquery[i]
    tx2,ty2,place2 = xquery[i+1]
    cost = min(abs(tx2-tx),abs(ty2-ty))
    heapq.heappush(query,(cost,place,place2))
    
    ty,tx,place = yquery[i]
    ty2,tx2,place2 = yquery[i+1]
    cost = min(abs(tx2-tx),abs(ty2-ty))
    heapq.heappush(query,(cost,place,place2))
  ct = 0
  uf = UnionFind(n)
  while len(query) > 0:
    cost,place1,place2 = heapq.heappop(query)
    if uf.same_check(place1,place2):
      continue
    else:
      uf.union(int(place1),int(place2))
      ct += cost
  print(ct)
      

solve()

Solution (Python):
import heapq
import sys
input = sys.stdin.readline
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_check(self, x, y):
        return self.find(x) == self.find(y)

def solve():
  n = int(input())
  query = []
  xquery = []
  yquery = []
  for i in range(n):
    x,y = (int(i) for i in input().split())
    xquery.append((x,y,i))
    yquery.append((y,x,i))
  xquery.sort()
  yquery.sort()
  for i in range(n-1):
    tx,ty,place = xquery[i]
    tx2,ty2,place2 = xquery[i+1]
    cost = min(abs(tx2-tx),abs(ty2-ty))
    if place > place2:
      place,place2 = place2,place
    heapq.heappush(query,(cost,place,place2))
    
    ty,tx,place = yquery[i]
    ty2,tx2,place2 = yquery[i+1]
    cost = min(abs(tx2-tx),abs(ty2-ty))
    if place > place2:
      place,place2 = place2,place
    heapq.heappush(query,(cost,place,place2))
  ct = 0
  uf = UnionFind(n)

  while len(query) > 0:
    cost,place1,place2 = heapq.heappop(query)
    if uf.same_check(place1,place2):
      continue
    else:
      uf.union(int(place1),int(place2))
      ct += cost
  print(ct)
      

solve()

Solution (Python):
n=int(input())
lx=[]
ly=[]
for i in range(n):
    x,y=[int(j) for j in input().split()]
    lx.append((i,x,y))
    ly.append((i,x,y))
from operator import itemgetter
lx.sort(key=itemgetter(1))
ly.sort(key=itemgetter(2))

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
edge=set()
for i in range(n-1):
    i1,x1,y1=lx[i]
    i2,x2,y2=lx[i+1]
    d=min(abs(x1-x2),abs(y1-y2))
    edge.add((i1,i2,d))
for i in range(n-1):
    i1,x1,y1=ly[i]
    i2,x2,y2=ly[i+1]
    d=min(abs(x1-x2),abs(y1-y2))
    edge.add((i1,i2,d))
row,col,value = zip(*edge)
value = np.array(value,dtype=int)
graph = csr_matrix((value,(row,col)),shape=(n,n))

tree = minimum_spanning_tree(graph,overwrite = True).astype(int)
print(tree.sum())

Solution (Python):
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
from operator import itemgetter
import sys
input = sys.stdin.readline
n=int(input())
lx=[]
ly=[]
XY = [[i] + [int(x) for x in input().split()] for i in range(n)]
edge = set()
for key in [itemgetter(1),itemgetter(2)]:
    XY.sort(key = key)
    for i in range(n-1):
        i1,x1,y1 = XY[i]
        i2,x2,y2 = XY[i+1]
        d = min(abs(x1-x2),abs(y1-y2))
        edge.add((i1,i2,d))

row,col,value = zip(*edge)
value = np.array(value,dtype=int)
graph = csr_matrix((value,(row,col)),shape=(n,n))

tree = minimum_spanning_tree(graph,overwrite = True).astype(int)
print(tree.sum())

Solution (Python):
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree
from operator import itemgetter
n=int(input())
lx=[]
ly=[]
XY = [[i] + [int(x) for x in input().split()] for i in range(n)]
edge = set()
for key in [itemgetter(1),itemgetter(2)]:
    XY.sort(key = key)
    for i in range(n-1):
        i1,x1,y1 = XY[i]
        i2,x2,y2 = XY[i+1]
        d = min(abs(x1-x2),abs(y1-y2))
        edge.add((i1,i2,d))

row,col,value = zip(*edge)
value = np.array(value,dtype=int)
graph = csr_matrix((value,(row,col)),shape=(n,n))

tree = minimum_spanning_tree(graph,overwrite = True).astype(int)
print(tree.sum())

Solution (Python):

import sys
from collections import deque, defaultdict
import copy
import bisect

import math
import heapq
from itertools import combinations, permutations

import sys
def input():
	return sys.stdin.readline().strip()


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

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

for i in range(N - 1):
	edge_list[xy1[i][1]].append((xy1[i + 1][0] - xy1[i][0], xy1[i + 1][1]))
	edge_list[xy1[i + 1][1]].append((xy1[i + 1][0] - xy1[i][0], xy1[i][1]))
	edge_list[xy2[i][1]].append((xy2[i + 1][0] - xy2[i][0], xy2[i + 1][1]))
	edge_list[xy2[i + 1][1]].append((xy2[i + 1][0] - xy2[i][0], xy2[i][1]))

judge = [0]*N
G = []
heapq.heapify(G)
for edge in edge_list[0]:
	heapq.heappush(G, edge)

judge[0] = 1
total = 0
num = 0
while num < N - 1:
	edge = heapq.heappop(G)
	if judge[edge[1]] == 0:
		judge[edge[1]] = 1
		total += edge[0]
		num += 1
		for add in edge_list[edge[1]]:
			if judge[add[1]] == 0:
				heapq.heappush(G, add)

print(total)

Solution (Python):

import collections
def main():

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

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

    parent = [a for a in range(N)]
    def find(a):
        if parent[a] != a:
            parent[a] = find(parent[a])
        return parent[a]
    def union(a, b, c):
        pa, pb = find(a), find(b)
        if pa != pb:
            parent[pb] = pa
            return c, 1
        else:
            return 0, 0

    cost = 0
    connected = N
    for a, b, c in edges:
        cst, cmp = union(a, b, c)
        cost += cst
        connected -= cmp
        if connected == 1:
            return cost



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

Solution (Python):
from operator import itemgetter
from bisect import bisect_left, bisect_right
import heapq as hp
import sys
input = sys.stdin.readline




'''
def graph_ABC065D(N, max_xy):
    print(N)
    XY = []
    for _ in range(N):
        xi = np.random.randint(0, max_xy)
        yi = np.random.randint(0, max_xy)
        XY.append([xi, yi])
        print(xi, yi)
    return N, XY


def plot(N, XY, max_xy):
    X, Y = zip(*XY)
    plt.scatter(X, Y)
    plt.grid(b=True)
    plt.xlim((0, max_xy))
    plt.ylim((0, max_xy))
    plt.xticks(np.arange(0, max_xy, 1))
    plt.yticks(np.arange(0, max_xy, 1))
    plt.show()
'''

def main():
    N = int(input())
    XY = [list(map(int, input().split())) for _ in range(N)]

    Xs = []
    Ys = []
    for i, (x, y) in enumerate(XY):
        Xs.append((i, x))
        Ys.append((i, y))
    Xs.sort(key=itemgetter(1))
    Ys.sort(key=itemgetter(1))

    Ix, X = zip(*Xs)
    Iy, Y = zip(*Ys)
    
    Rx = [None]*N
    Ry = [None]*N
    for i, (ix, iy) in enumerate(zip(Ix, Iy)):
        Rx[ix] = i
        Ry[iy] = i

    
    graph = [[] for _ in range(N)]
    for i, (x, y) in enumerate(XY):
        nexts = set()
        ix = Rx[i]
        if ix != 0:
            nexts.add(Ix[ix-1])
        if ix != N-1:
            nexts.add(Ix[ix+1])
        
        iy = Ry[i]
        if iy != 0:
            nexts.add(Iy[iy-1])
        if iy != N-1:
            nexts.add(Iy[iy+1])
        
        for n in nexts:
            d = min(abs(XY[n][0]-XY[i][0]), abs(XY[n][1]-XY[i][1]))
            graph[i].append((d, n))



    checked = [False for _ in range(N)]
    checked[0] = True 
    q = [] 
    for d, n in graph[0]:
        hp.heappush(q, (d, n))
    ans = 0

    
    while q:
        nd, np = hp.heappop(q) 
        
        if checked[np]: 
            continue
        ans += nd
        
        checked[np] = True
        for d, p in graph[np]:
            if not checked[p]:
                hp.heappush(q, (d, p))

    print(ans)
            

if __name__ == "__main__":
    
    
    
    
    
    
    

    main()

Solution (Python):
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 Count(self, x):
        return -self.root[self.Find_Root(x)]

n = int(input())
arr = []
ans = 0
for i in range(n):
    arr.append([i] + list(map(int,input().split())))
x_sort = sorted(arr, key = lambda x:x[1])
y_sort = sorted(arr, key = lambda x:x[2])

import heapq as hq

q = []

for i in range(n-1):
    costx = x_sort[i+1][1] - x_sort[i][1]
    costy = y_sort[i+1][2] - y_sort[i][2]
    hq.heappush(q, [costx, x_sort[i][0], x_sort[i+1][0] ])
    hq.heappush(q, [costy, y_sort[i][0], y_sort[i+1][0] ])

uf = UnionFind(n)
for rep in range(3*10**5):
    cost, a, b = hq.heappop(q)
    if uf.isSameGroup(a, b):
        continue
    else:
        uf.Unite(a, b)
        ans += cost
    if uf.Count(0) == n:
        break
print(ans)

Solution (Python):
import sys,bisect as bs,collections as cl,heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
n = onem()
data = []
edges = []
for i in range(n):
    kkk = l()
    data.append([i]+ kkk)
ddd = sorted(data,key = lambda x:x[1])
bbb = sorted(data,key = lambda x:x[2])

Ne = cl.defaultdict(list)
for i in range(1,n):
    Ne[ddd[i-1][0]].append((ddd[i][0],ddd[i][1]-ddd[i-1][1]))
    Ne[ddd[i][0]].append((ddd[i-1][0],ddd[i][1]-ddd[i-1][1]))
    Ne[bbb[i-1][0]].append((bbb[i][0],bbb[i][2]-bbb[i-1][2]))
    Ne[bbb[i][0]].append((bbb[i-1][0],bbb[i][2]-bbb[i-1][2]))

is_used = [False for i in range(n+1)]
h = []
hq.heappush(h,(0,1))
ans = 0

while h:
    d,n = hq.heappop(h)
    if is_used[n]:
        continue
    ans += d
    is_used[n] = True
    for z,x in Ne[n]:

        if not is_used[z]:
            hq.heappush(h,(x,z))

print(ans)

Solution (Python):
def find(u,x):
    if u[x]<0:
        return x
    u[x] = find(u,u[x])
    return u[x]

def unite(u,a,b):
    a = find(u,a)
    b = find(u,b)
    if a == b:
        return False
    if u[b] < u[a]:
        a,b = b,a
    u[a] += u[b]
    u[b] = a
    return True

def same(u,x,y):
    return find(u,x) == find(u,y)

n = int(input())
l = list()
for i in range(n):
  x,y = map(int,input().split())
  l.append((x,y,i))
l.sort()
uf = [-1]*(n+1)
ed = list()
for i in range(n-1):
  ed.append((l[i][2],l[i+1][2],l[i+1][0]-l[i][0]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
  ed.append((l[i][2],l[i+1][2],l[i+1][1]-l[i][1]))
ed.sort(key=lambda x:x[2])
ans = 0
for x,y,d in ed:
  if not same(uf,x,y):
    unite(uf,x,y)
    ans += d
print(ans)

Solution (Python):

def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a

def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

import heapq

N = int(input())

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

XY0.sort()
XY1 = sorted(XY1, key=lambda x: x[1])

E = []
for i,x in enumerate(XY0):
    if i == 0:
        ox = x[0]
        oi = x[2]
    else:
        dx = x[0]-ox
        ox = x[0]
        heapq.heappush(E,[dx,oi,x[2]])
        oi = x[2]

for i,y in enumerate(XY1):
    if i == 0:
        oy = y[1]
        oi = y[2]
    else:
        dy = y[1]-oy
        oy = y[1]
        heapq.heappush(E,[dy,oi,y[2]])
        oi = y[2]



V = [i for i in range(N)]
ans = 0
while E:
    w,s,t = heapq.heappop(E)
    if find(V,s) != find(V,t):
        union(V,s,t)
        ans+=w
        
print(ans)

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

E=[]

T.sort()
for i in range(1,N):
    E.append((T[i][0]-T[i-1][0],T[i-1][2],T[i][2]))

T.sort(key=lambda x:x[1])
for i in range(1,N):
    E.append((T[i][1]-T[i-1][1],T[i-1][2],T[i][2]))



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

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):  
    if find(x) != find(y):
        Group[find(y)]=Group[find(x)]=min(find(y),find(x))


E.sort()
ANS=0
for c,x,y in E:
    if find(x)!=find(y):
        Union(x,y)
        ANS+=c

print(ANS)