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):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7

dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1



class UnionFind():
    def __init__(self, n):
        self.n = n
        
        self.parents = [-1] * n

    def find(self, x): 
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n = int(ipt())
    xs = []
    ys = []
    for i in range(n):
        x,y = map(int,ipt().split())
        xs.append(x*n+i)
        ys.append(y*n+i)
    xs.sort()
    ys.sort()
    ways = []
    x0 = xs[0]//n
    xi = xs[0]%n
    y0 = ys[0]//n
    yi = ys[0]%n
    for i in xs[1::]:
        x = i//n
        j = i%n
        ways.append((x-x0)*(n**2)+xi*n+j)
        x0 = x
        xi = j
    for i in ys[1::]:
        y = i//n
        j = i%n
        ways.append((y-y0)*(n**2)+yi*n+j)
        y0 = y
        yi = j

    ways.sort()
    ans = 0
    uf = UnionFind(n)
    for i in ways:
        d = i//(n**2)
        i1 = (i//n)%n
        i2 = i%n
        
        if not uf.same(i1,i2):
            uf.union(i1,i2)
            ans += d

    print(ans)

    return None

if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappop, heappush

class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
        self.size = [1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.size[x] < self.size[y]:
                x,y = y,x
            self.parents[y] = x
            self.size[x] += self.size[y]

N = int(input())
x = [None] * N
y = [None] * N
for i in range(N):
    a, b = map(int, input().split())
    x[i] = (a,i)
    y[i] = (b,i)

x.sort()
y.sort()
q = []
for i in range(N-1):
    heappush(q, (abs(x[i][0]-x[i+1][0]), x[i][1], x[i+1][1]))
    heappush(q, (abs(y[i][0]-y[i+1][0]), y[i][1], y[i+1][1]))

uf = UnionFind(N)
ans = 0

while len(q) > 0:
    w, s, t = heappop(q)
    if uf.find(s) != uf.find(t):
        ans += w
        uf.union(s,t)
print(ans)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N = I()
X,Y = [],[]
for i in range(N):
    x,y = MI()
    X.append((x,i+1))
    Y.append((y,i+1))

X.sort()
Y.sort()





class Kruskal():
    def __init__(self,n):
        self.e = []
        self.par = [i for i in range(n+1)]  
        self.rank = [0]*(n+1)
    def add(self,u,v,d):  
        self.e.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 same_check(self,x,y):  
        return self.find(x) == self.find(y)
    def unite(self,x,y):  
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1
    def Kruskal(self):
        edges = sorted(self.e,key=lambda x: x[2])  
        a = 0
        for e in edges:
            if not self.same_check(e[0],e[1]):
                self.unite(e[0],e[1])
                a += e[2]
        return a


K = Kruskal(N)
for j in range(N-1):
    x0,i0 = X[j]
    x1,i1 = X[j+1]
    K.add(i0,i1,x1-x0)
for j in range(N-1):
    y0,i0 = Y[j]
    y1,i1 = Y[j+1]
    K.add(i0,i1,y1-y0)

print(K.Kruskal())

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

from heapq import heapify, heappop, heappush
N = int(input())
X = [];Y = []
for i in range(N):
  a,b = map(int,input().split())
  X.append((a,b,i))
  Y.append((a,b,i))
X.sort(key=lambda x:x[0])
Y.sort(key=lambda x:x[1])

PQ = []
for i in range(N-1):
  difx = (X[i+1][0]-X[i][0],X[i][2],X[i+1][2])
  dify = (Y[i+1][1]-Y[i][1],Y[i][2],Y[i+1][2])
  
  heappush(PQ,difx);heappush(PQ,dify)
uf = UnionFind(N)
ans = 0
while PQ:
  dis,a,b = heappop(PQ)
  if uf.is_same(a, b):
    continue
  ans += dis
  uf.union(a,b)
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  


N = I()
X,Y = [],[]
for i in range(N):
    x,y = MI()
    X.append((x,i+1))
    Y.append((y,i+1))

X.sort()
Y.sort()





class Kruskal():
    def __init__(self,n):
        self.e = []
        self.par = [i for i in range(n+1)]  
        self.rank = [0]*(n+1)
    def add(self,u,v,d):  
        self.e.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 same_check(self,x,y):  
        return self.find(x) == self.find(y)
    def unite(self,x,y):  
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1
    def Kruskal(self):
        edges = sorted(self.e,key=lambda x: x[2])  
        a = 0
        for e in edges:
            if not self.same_check(e[0],e[1]):
                self.unite(e[0],e[1])
                a += e[2]
        return a


K = Kruskal(N)
for j in range(N-1):
    x0,i0 = X[j]
    x1,i1 = X[j+1]
    K.add(i0,i1,x1-x0)
for j in range(N-1):
    y0,i0 = Y[j]
    y1,i1 = Y[j+1]
    K.add(i0,i1,y1-y0)

print(K.Kruskal())

Solution (Python):
import heapq

n=int(input())
def deka(a,b,c):
    return a*10**12+b*10**6+c
parents=[-1 for i in range(n)] 
HEN=[] 
MST=[[] for i in range(n)] 
A=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append([i,a,b])
A=sorted(A,key=lambda x:x[1])
for i in range(1,n):
    heapq.heappush(HEN, deka(A[i][1]-A[i-1][1],A[i][0],A[i-1][0]))
A=sorted(A,key=lambda x:x[2])
for i in range(1,n):
    heapq.heappush(HEN, deka(A[i][2]-A[i-1][2],A[i][0],A[i-1][0]))




def find(x): 
    if parents[x] <0 : return x  
    parents[x]=find(parents[x])
    return parents[x]
def union(x,y): 
    xx=find(x) ; yy=find(y)
    if xx==yy: return 
    size_xx=abs(parents[xx])
    size_yy=abs(parents[yy]) 
    if size_xx>size_yy: xx,yy=yy,xx 
    parents[yy]+=parents[xx]
    parents[xx]=yy  

ans=0
while HEN:
    dd= heapq.heappop(HEN)
    d=dd//(10**12) ; a=(dd-d*10**12)//(10**6) ; b=dd%(10**6)
    if find(a)==find(b):continue
    union(a,b) 
    
    
    ans+=d
    

print(ans)

Solution (Python):
class UnionFind():
    """
    UnionFindTreeのクラス
    
    Attributes:
    n: int: ノード数
    parents: そのノードが属する木の根を格納, 根の場合は-1

    """
    def __init__(self, n):
        """ノード数nで初期化"""
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """ノードxが属するグループの根を返す"""
        if self.parents[x] < 0:
            return x
        else:
            
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """xが属するグループとyが属するグループを併合"""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

    def same(self, x, y):
        """x, yが同じグループに属するかどうかを返す"""
        return self.find(x) == self.find(y)

    def members(self, x):
        """xが属するグループ内の要素をリストで返す"""
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """全ての根に対する要素をリストで返す"""
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """グループの総数を返す"""
        return len(self.roots())

    def all_group_members(self):
        """{root: [そのグループの要素リスト]}の辞書を返す"""
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        """printデバッグ用. root: [要素リスト]をstrで返す"""
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def kruskal(edge_list: list, n_V: int):
    """
    クラスカル法
    edge_list: 各要素が(weight, node1, node2)のリスト
    n_V: ノード数
    sortがボトルネックとなりO(|E|log(|E|))
    """
    edge_list = sorted(edge_list) 
    ret = 0
    uf = UnionFind(n_V) 
    n_edges = 0
    for w, s, t in edge_list:
        if n_edges == n_V-1: 
            break
        if uf.same(s, t):
            
            
            
            continue
        
        uf.union(s, t) 
        ret += w
        n_edges += 1
    
    return ret

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

edges = []
x.sort()
y.sort()
for i in range(N-1):
    id1 = x[i][1]
    id2 = x[i+1][1]
    cost = abs(x[i][0]-x[i+1][0])
    edges.append((cost, id1, id2))
for i in range(N-1):
    id1 = y[i][1]
    id2 = y[i+1][1]
    cost = abs(y[i][0]-y[i+1][0])
    edges.append((cost, id1, id2))

ret = kruskal(edges, N)
print(ret)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7



    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n
    
        def find(self, x):
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]
    
        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)
    
            if x == y:
                return
    
            if self.parents[x] > self.parents[y]:
                x, y = y, x
    
            self.parents[x] += self.parents[y]
            self.parents[y] = x
    
        def size(self, x):
            return -self.parents[self.find(x)]
    
        def same(self, x, y):
            return self.find(x) == self.find(y)
    
        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]
    
        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]
    
        def group_count(self):
            return len(self.roots())
    
        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}
    
        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    n=I()
    lisx=[]
    lisy=[]
    edge=[]
    for i in range(n):
        x,y=MI()
        lisx.append([x,i])
        lisy.append([y,i])
    lisx.sort(key=lambda x:x[0])
    lisy.sort(key=lambda x:x[0])
    for i in range(n-1):
        edge.append([lisx[i][1],lisx[i+1][1],lisx[i+1][0]-lisx[i][0]])
        edge.append([lisy[i][1],lisy[i+1][1],lisy[i+1][0]-lisy[i][0]])
    edge.sort(key=lambda x:x[2])
    
    ans=0
    uf=UnionFind(n)
    count=0
    for x,y,z in edge:
        if uf.same(x,y):
            continue
        else:
            uf.union(x,y)
            ans+=z
            count+=1
        if count==n-1:
            break
    print(ans)
        
        
    
if __name__=="__main__":
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7



    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n
    
        def find(self, x):
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]
    
        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)
    
            if x == y:
                return
    
            if self.parents[x] > self.parents[y]:
                x, y = y, x
    
            self.parents[x] += self.parents[y]
            self.parents[y] = x
    
        def size(self, x):
            return -self.parents[self.find(x)]
    
        def same(self, x, y):
            return self.find(x) == self.find(y)
    
        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]
    
        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]
    
        def group_count(self):
            return len(self.roots())
    
        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}
    
        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    n=I()
    lisx=[]
    lisy=[]
    edge=[]
    for i in range(n):
        x,y=MI()
        lisx.append([x,i])
        lisy.append([y,i])
    lisx.sort(key=lambda x:x[0])
    lisy.sort(key=lambda x:x[0])
    for i in range(n-1):
        edge.append([lisx[i][1],lisx[i+1][1],lisx[i+1][0]-lisx[i][0]])
        edge.append([lisy[i][1],lisy[i+1][1],lisy[i+1][0]-lisy[i][0]])
    edge.sort(key=lambda x:x[2])
    
    ans=0
    uf=UnionFind(n)
    for x,y,z in edge:
        if uf.same(x,y):
            continue
        else:
            uf.union(x,y)
            ans+=z
    print(ans)
        
        
    
if __name__=="__main__":
    main()

Solution (Python):
from scipy.sparse import *
from scipy.sparse.csgraph import *
N = int(input())
T = [[n]+list(map(int,input().split())) for n in range(N)]
P = set()

for i in [1,2]:
  T.sort(key=lambda a: a[i])
  for j in range(1,N):
    i0,x0,y0 =  T[j-1]
    i1,x1,y1 =  T[j]
    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))
print(int(minimum_spanning_tree(G).sum()))

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 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  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)]
  def Members(self, x): 
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): 
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): 
    return len(self.Roots())


def kruskal(N, stw):
  
  
  
  
  res = 0
  uf = UnionFind(N)
  for i in range(len(stw)):
    s, t, w = stw[i]
    if not uf.isSameGroup(s, t):
      uf.Unite(s, t)
      res += w
  return res

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

stw = []

ixy = sorted(ixy, key=lambda x:x[1])
for j in range(N-1):
  i, x, y = ixy[j]
  ii, xx, yy = ixy[j+1]
  stw += [[i, ii, min(abs(x-xx), abs(y-yy))]]

ixy = sorted(ixy, key=lambda x:x[2])
for j in range(N-1):
  i, x, y = ixy[j]
  ii, xx, yy = ixy[j+1]
  stw += [[i, ii, min(abs(x-xx), abs(y-yy))]]

stw = sorted(stw, key=lambda x:x[2])
print(kruskal(N, stw))

Solution (Python):

import sys

sys.setrecursionlimit(10**9)

N = int(input())

X_L = [None] * N
Y_L = [None] * N
for i in range(N):
    _x, _y = map(int, input().split())
    X_L[i] = [_x, i]
    Y_L[i] = [_y, i]

class UnionFind():
    def __init__(self, n):
        self.rank = [1] * n
        self.par = [int(_) 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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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



X_L.sort()
Y_L.sort()
dx_l = [None] * (N-1)
dy_l = [None] * (N-1)
for i in range(N-1):
    dx_l[i] = [X_L[i+1][0] - X_L[i][0], X_L[i][1], X_L[i+1][1]]
    dy_l[i] = [Y_L[i+1][0] - Y_L[i][0], Y_L[i][1], Y_L[i+1][1]]

tmp_l = dx_l+dy_l
tmp_l.sort()

UF = UnionFind(N)
ans = 0

for _ in range(2*N-2):
    _d, _i, _j = tmp_l[_]
    if _i >= N or _j >= N:
        print(_i, _j)
    if UF.same(_i, _j):
        continue
    UF.unite(_i, _j)
    ans += _d

print(ans)

Solution (Python):

import sys

sys.setrecursionlimit(10**9)

N = int(input())

X_L = [None] * N
Y_L = [None] * N
for i in range(N):
    _x, _y = map(int, input().split())
    X_L[i] = [_x, i]
    Y_L[i] = [_y, i]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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

























    






X_L.sort()
Y_L.sort()
dx_l = [None] * (N-1)
dy_l = [None] * (N-1)
for i in range(N-1):
    dx_l[i] = [X_L[i+1][0] - X_L[i][0], X_L[i][1], X_L[i+1][1]]
    dy_l[i] = [Y_L[i+1][0] - Y_L[i][0], Y_L[i][1], Y_L[i+1][1]]

tmp_l = dx_l+dy_l
tmp_l.sort()

UF = UnionFind(N)
ans = 0

for _ in range(2*N-2):
    _d, _i, _j = tmp_l[_]
    if UF.same(_i, _j):
        continue
    UF.unite(_i, _j)
    ans += _d
    
    



print(ans)

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
from operator import itemgetter

N = int(input())
P = []
for i in range(N):
  x,y = map(int, input().split())
  P.append((x,y,i))
  
data = [10, 20, 30, 40]
row = [0, 0, 1, 1]
col = [1, 2, 0, 2]


  
data = []
row = []
col = []

P.sort() 
D = {}
for i in range(N-1):
  a,b,p = P[i]
  c,d,q = P[i+1]
  cost = min(abs(a-c), abs(b-d))
  data.append(cost)
  row.append(p)
  col.append(q)
  data.append(cost)
  row.append(q)
  col.append(p)
  D[(p,q)] = cost
  D[(q,p)] = cost

P.sort(key=itemgetter(1))
for i in range(N-1):
  a,b,p = P[i]
  c,d,q = P[i+1]
  if (p,q) in D:
    continue
  cost = min(abs(a-c), abs(b-d))
  data.append(cost)
  row.append(p)
  col.append(q)
  data.append(cost)
  row.append(q)
  col.append(p)
  D[(p,q)] = cost
  D[(q,p)] = cost

coo = coo_matrix((data, (row, col)), (N, N))
mst = minimum_spanning_tree(coo)
print(int(mst.sum()))

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

    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.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y] +=1

    def 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 members(self,x):
        root=self.Find_Root(x)
        return [i for i in range(self.n) if self.Find_Root(i)==root]

    def roots(self):
        return[i for i,j in enumerate(self.root) if j<0]

    def group_members(self):
        return {i:self.members(i) for i in self.roots()}

    def group_count(self):
        return len(self.roots())


def kruskal():
    D,M=[],[]

    A,B=sorted(XY),sorted(XY,key=lambda x:x[1])
    for i in range(n-1):
        M.append([abs(A[i][0]-A[i+1][0]),A[i][2],A[i+1][2]])
        M.append([abs(B[i][1]-B[i+1][1]),B[i][2],B[i+1][2]])

    M.sort()
    for i,j,k in M:
        if UnionFind.isSameGroup(j,k) is False:
            UnionFind.Unite(j,k)
            D.append(i)

    return D


n=int(input())
XY=[list(map(int,input().split()))+[i+1] for i in range(n)]
UnionFind=UnionFind(n+1)
print(sum(kruskal()))

Solution (Python):

import sys
from heapq import heappush,heappop,heapify

N=int(sys.stdin.readline().strip())
V=[]    
for v in range(N):   
    x,y=tuple(map(int, sys.stdin.readline().split()))
    V.append((x,y,v+1))


V.sort(key=lambda x:(x[0]) )
E=[]    
for i in range(N-1):
    fro_x,fro=V[i][0],V[i][2]
    to_x,to=V[i+1][0],V[i+1][2]
    E.append( (abs(fro_x-to_x),fro,to))


V.sort(key=lambda x:(x[1]) )
for i in range(N-1):
    fro_y,fro=V[i][1],V[i][2]
    to_y,to=V[i+1][1],V[i+1][2]
    E.append( (abs(fro_y-to_y),fro,to))


al=[[] for _ in range(N+1)]
for cost,fro,to in E:
    al[fro].append((cost,to))
    al[to].append((cost,fro))


fixed_v=[ 0 for _ in range(N+1) ]
hq=[]   
V=[1]   

ans=0
while V:
    cur=V.pop()
    
    fixed_v[cur]=1
    
    for cost,to in al[cur]:
        heappush(hq,(cost,to))
    while hq:
        
        cost,to=heappop(hq)
        
        if fixed_v[to]==0:
            ans+=cost
            V.append(to)
            break
        

print ans

Solution (Python):

import sys
from heapq import heappush,heappop,heapify

N=int(sys.stdin.readline().strip())
V=[]    
for v in range(N):   
    x,y=tuple(map(int, sys.stdin.readline().split()))
    V.append((x,y,v+1))


V.sort(key=lambda x:(x[0]) )
E=[]    
for i in range(N-1):
    fro_x,fro=V[i][0],V[i][2]
    to_x,to=V[i+1][0],V[i+1][2]
    E.append( (abs(fro_x-to_x),fro,to))


V.sort(key=lambda x:(x[1]) )
for i in range(N-1):
    fro_y,fro=V[i][1],V[i][2]
    to_y,to=V[i+1][1],V[i+1][2]
    E.append( (abs(fro_y-to_y),fro,to))


al=[[] for _ in range(N+1)]
for cost,fro,to in E:
    al[fro].append((cost,to))
    al[to].append((cost,fro))



fixed_v=[ 0 for _ in range(N+1) ]
hq=[]   
V=[1]   

ans=0
while V:
    cur=V.pop()
    
    fixed_v[cur]=1
    
    for cost,to in al[cur]:
        heappush(hq,(cost,to))
    while hq:
        
        cost,to=heappop(hq)
        
        if fixed_v[to]==0:
            ans+=cost
            V.append(to)
            break
        

print ans

Solution (Python):

import sys
from heapq import heappush,heappop,heapify

N=int(sys.stdin.readline().strip())
V=[]    
for v in range(N):   
    x,y=tuple(map(int, sys.stdin.readline().split()))
    V.append((x,y,v+1))


V.sort(key=lambda x:(x[0]) )
E=[]    
for i in range(N-1):
    fro_x,fro=V[i][0],V[i][2]
    to_x,to=V[i+1][0],V[i+1][2]
    E.append( (abs(fro_x-to_x),fro,to))


V.sort(key=lambda x:(x[1]) )
for i in range(N-1):
    fro_y,fro=V[i][1],V[i][2]
    to_y,to=V[i+1][1],V[i+1][2]
    E.append( (abs(fro_y-to_y),fro,to))


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

al=[[] for _ in range(N+1)]

for cost,fro,to in E:
    al[fro].append((cost,to))
    al[to].append((cost,fro))



fixed_v=[ 0 for _ in range(N+1) ]
hq=[]   
V=[1]   

ans=0
while V:
    cur=V.pop()
    
    fixed_v[cur]=1
    
    for cost,to in al[cur]:
        heappush(hq,(cost,to))
    while hq:
        
        cost,to=heappop(hq)
        
        if fixed_v[to]==0:
            ans+=cost
            V.append(to)
            break
        

print ans

Solution (Python):

import sys
N=int(sys.stdin.readline().strip())
V=[]    
for v in range(N):   
    x,y=tuple(map(int, sys.stdin.readline().split()))
    V.append((x,y,v+1))


V.sort(key=lambda x:(x[0]) )
E=[]    
for i in range(N-1):
    fro_x,fro=V[i][0],V[i][2]
    to_x,to=V[i+1][0],V[i+1][2]
    E.append( (abs(fro_x-to_x),fro,to))


V.sort(key=lambda x:(x[1]) )
for i in range(N-1):
    fro_y,fro=V[i][1],V[i][2]
    to_y,to=V[i+1][1],V[i+1][2]
    E.append( (abs(fro_y-to_y),fro,to))


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


par=[ i for i in range(N+1) ]
size=[ 1 for i in range(N+1) ]


def root(x):
    while par[x]!=x:
        x=par[x]
    return x

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

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y: return
    if size[y]<size[x]: x,y=y,x  
    size[y]+=size[x]
    par[x]=y 

def getsize(x):
	return size[root(x)]

ans=0
for cost,v1,v2 in E:
    if same(v1,v2) is False:
        ans+=cost
        unite(v1,v2)

print ans

Solution (Python):
from heapq import heappop,heappush
import sys
sys.setrecursionlimit(10**6)
n=int(input())
pair=[i for i in range(n)]
que=[]
e=[None]*n
for i in range(n):
  x,y=map(int,input().split())
  e[i]=(i,x,y)
ex=sorted(e,key=lambda x:x[1])
ey=sorted(e,key=lambda x:x[2])
for i in range(n-1):
  w=ex[i+1][1]-ex[i][1]
  heappush(que,(w,ex[i][0],ex[i+1][0]))
for i in range(n-1):
  w=ey[i+1][2]-ey[i][2]
  heappush(que,(w,ey[i][0],ey[i+1][0]))
def find(x):
  if x==pair[x]:return x
  else:
    tmp=find(pair[x])
    pair[x]=tmp
    return tmp
q=[]
ans=0
while que:
  w,s,t=heappop(que)
  root_s=find(s)
  root_t=find(t)
  if root_s!=root_t:
    pair[root_s]=root_t
    ans+=w
print(ans)