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

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

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(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.root(x)]

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

    def members(self, x):
        root = self.root(x)
        return [i for i in range(self.n) if self.root(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(input())
    
    x, y = [[0, 0] for _ in range(N)], [[0, 0] for _ in range(N)]
    for i in range(N):
        x[i][0], y[i][0] = map(int, input().split())
        x[i][1], y[i][1] = i, i
    x, y = sorted(x), sorted(y)
    
    L = [[0, 0, 0] for _ in range((N - 1) * 2)]
    for i in range(N - 1):
        L[i * 2][0] = x[i + 1][0] - x[i][0]
        L[i * 2][1] = x[i][1]
        L[i * 2][2] = x[i + 1][1]
        L[i * 2 + 1][0] = y[i + 1][0] - y[i][0]
        L[i * 2 + 1][1] = y[i][1]
        L[i * 2 + 1][2] = y[i + 1][1]
    L = sorted(L)

    tree = UnionFind(N)
    ans = 0
    for i in range((N - 1) * 2):
        if not tree.same(L[i][1], L[i][2]):
            ans += L[i][0]
            tree.unite(L[i][1], L[i][2])
    print(ans)
    

if __name__ == '__main__':
    main()

Solution (Python):
from heapq import *
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 -size.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())
n=int(input())
X=[]
Y=[]
edge=[] 
for i in range(n):
  x,y=map(int,input().split())
  X.append((x,i))
  Y.append((y,i))
  edge.append((x,y))
X.sort()
Y.sort()
hq=[]
heapify(hq)
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(hq,(x2-x1,j1,j2))
  heappush(hq,(y2-y1,k1,k2))
uf=UnionFind(n)
ans=0
while hq:
  w,s,t=heappop(hq)
  if uf.find(s)!=uf.find(t):
    uf.unite(s,t)
    ans+=w
print(ans)

Solution (Python):
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.par=[i for i in range(n)]
        self.size=[1]*n
    def find(self,x):
        if x==self.par[x]:
            return self.par[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.size[x]>self.size[y]:
            self.size[x]+=self.size[y]
            self.par[y]=x
        else:
            self.size[y]+=self.size[x]
            self.par[x]=y

n=int(input())

x_list=[]
y_list=[]

for i in range(n):
    x,y=map(int,input().split())
    x_list.append((x,i))
    y_list.append((y,i))
x_list.sort()
y_list.sort()
edges=[]

for i in range(1,n):
    edges.append((x_list[i][0]-x_list[i-1][0],x_list[i][1],x_list[i-1][1]))

    edges.append((y_list[i][0]-y_list[i-1][0],y_list[i][1],y_list[i-1][1]))

edges.sort()
uf=UnionFind(n)
ans=0
for e in edges:
    wt=e[0]
    x=e[1]
    y=e[2]
    if uf.find(x)==uf.find(y):
        continue
    ans+=wt
    uf.unite(x,y)
print(ans)

Solution (Python):
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.par=[i for i in range(n)]
        self.size=[1]*n
    def find(self,x):
        if x==self.par[x]:
            return self.par[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.size[x]>self.size[y]:
            self.size[x]+=self.size[y]
            self.par[y]=x
        else:
            self.size[y]+=self.size[x]
            self.par[x]=y

import sys
input=sys.stdin.buffer.readline
n=int(input())

x_list=[]
y_list=[]

for i in range(n):
    x,y=map(int,input().split())
    x_list.append((x,i))
    y_list.append((y,i))
x_list.sort()
y_list.sort()
edges=[]

for i in range(1,n):
    edges.append((x_list[i][0]-x_list[i-1][0],x_list[i][1],x_list[i-1][1]))

    edges.append((y_list[i][0]-y_list[i-1][0],y_list[i][1],y_list[i-1][1]))

edges.sort()
uf=UnionFind(n)
ans=0
for e in edges:
    wt=e[0]
    x=e[1]
    y=e[2]
    if uf.find(x)==uf.find(y):
        continue
    ans+=wt
    uf.unite(x,y)
print(ans)

Solution (Python):
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.par=[i for i in range(n)]
        self.size=[1]*n
    def find(self,x):
        if x==self.par[x]:
            return self.par[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.size[x]>self.size[y]:
            self.size[x]+=self.size[y]
            self.par[y]=x
        else:
            self.size[y]+=self.size[x]
            self.par[x]=y

import sys
input=sys.stdin.buffer.readline
n=int(input())

x_list=[]
y_list=[]

for i in range(n):
    x,y=map(int,input().split())
    x_list.append((x,i))
    y_list.append((y,i))
x_list.sort()
y_list.sort()
edges=[]

for i in range(1,n):
    edges.append((x_list[i][0]-x_list[i-1][0],x_list[i][1],x_list[i-1][1]))

    edges.append((y_list[i][0]-y_list[i-1][0],y_list[i][1],y_list[i-1][1]))

edges.sort()
uf=UnionFind(n)
ans=0
for e in edges:
    wt=e[0]
    x=e[1]
    y=e[2]
    if uf.find(x)==uf.find(y):
        continue
    ans+=wt
    uf.unite(x,y)
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self,n):
        super().__init__()
        self.par = [-1]*n
        self.rank = [0]*n
        self.tsize = [1]*n
    
    def root(self,x):
        if self.par[x] == -1:
            return x 
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x_r = self.root(x)
        y_r = self.root(y)
        
        if self.rank[x_r]>self.rank[y_r]:
            self.par[y_r] = x_r

        elif self.rank[x_r]<self.rank[y_r]:
            self.par[x_r] = y_r

        elif x_r != y_r:
            self.par[y_r] = x_r
            self.rank[x_r] += 1

        if x_r != y_r:
            size = self.tsize[x_r]+self.tsize[y_r]
            self.tsize[x_r] = size
            self.tsize[y_r] = size

    def isSame(self,x,y):
        return self.root(x) == self.root(y)

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

def main():

    n= int(input())
    edge = []
    for i in range(n):
      x,y = list(map(int,input().split()))
      edge.append((x,y,i))
    
    xs = sorted(edge,key=lambda a:a[0])
    ys = sorted(edge,key=lambda a:a[1])

    edge = []
    
    for i in range(n-1):
      x1,y1,p1 = xs[i]
      x2,y2,p2 = xs[i+1]
      edge.append((p1,p2,min(x2-x1,abs(y2-y1))))
      
      x1,y1,p1 = ys[i]
      x2,y2,p2 = ys[i+1]
      edge.append((p1,p2,min(abs(x2-x1),y2-y1)))
    edge.sort(key = lambda a:a[2])  
    uf = UnionFind(n)
    
    ans = 0
    for x,y,w in edge:
      if uf.isSame(x,y):continue
      uf.unite(x,y)
      ans+=w
    print(ans)
      
if __name__ == "__main__":
    main()

Solution (Python):
from operator import itemgetter
from collections import defaultdict
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix

n = int(input())
xy = [list(map(int, input().split())) + [i] for i in range(n)]
INF = 10 ** 9 + 1

d = defaultdict(lambda: INF)

for key in (itemgetter(0), itemgetter(1)):
    xy.sort(key=key)
    for (x1, y1, i1), (x2, y2, i2) in zip(xy, xy[1:]):
        c = min(abs(x1 - x2), abs(y1 - y2))
        d[(i1, i2)] = min(d[(i1, i2)], c)

row = []
col = []
cost = []
for (k1, k2), c in d.items():
    row.append(k1)
    col.append(k2)
    cost.append(c)

graph = csr_matrix((cost, (row, col)), shape=(n, n))
mst = minimum_spanning_tree(graph, overwrite=True).astype(int)
ans = mst.sum()
print(ans)

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

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

xyi = [[x, y, i] for i, (x, y) in enumerate(xy)]
edge = set()

xyi.sort()
for (x1, y1, i1), (x2, y2, i2) in zip(xyi, xyi[1:]):
    c = min(abs(x1 - x2), abs(y1 - y2))
    edge.add((i1, i2, c))

xyi.sort(key=itemgetter(1))
for (x1, y1, i1), (x2, y2, i2) in zip(xyi, xyi[1:]):
    c = min(abs(x1 - x2), abs(y1 - y2))
    edge.add((i1, i2, c))

row, col, cost = zip(*edge)

graph = csr_matrix((cost, (row, col)), shape=(n, n))
mst = minimum_spanning_tree(graph, overwrite=True).astype(int)
ans = mst.sum()
print(ans)

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

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

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



x_sort = sorted(xy, key=lambda x: x[0])
y_sort = sorted(xy, key=lambda x: x[1])

edge = [] 
for i in range(n-1):
    edge.append([x_sort[i][2],x_sort[i+1][2],x_sort[i+1][0]-x_sort[i][0]])
    edge.append([y_sort[i][2],y_sort[i+1][2],y_sort[i+1][1]-y_sort[i][1]])



ans = 0
edge.sort(key=lambda x:x[2])
u=UnionFind(n)
for i,j,cost in edge:
    if u.isSame(i,j) == False:
        u.unite(i,j)
        ans+=cost

print(ans)

Solution (Python):

from heapq import *

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



x_sort = sorted(xy, key=lambda x: x[0])
y_sort = sorted(xy, key=lambda x: x[1])

cost = [[]for _ in range(n+3)] 
for i in range(n-1):
    cost[x_sort[i][2]].append((x_sort[i+1][2],x_sort[i+1][0]-x_sort[i][0]))
    cost[x_sort[i+1][2]].append((x_sort[i][2],x_sort[i+1][0]-x_sort[i][0]))

    cost[y_sort[i][2]].append((y_sort[i+1][2],y_sort[i+1][1]-y_sort[i][1]))
    cost[y_sort[i+1][2]].append((y_sort[i][2],y_sort[i+1][1]-y_sort[i][1]))


used=[False]*(n+3)
q=[]






used[0] = True
ans = 0


for to,cst in cost[0]:
    heappush(q,(cst,to))



while(len(q)!=0):
    c,ver=heappop(q)

    if used[ver] == True:
        continue


    ans += c
    used[ver] = True

    for to,cst in cost[ver]:
        heappush(q,(cst,to))

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(2147483647)

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
x = [(i, xy[i][0]) for i in range(n)]
y = [(i, xy[i][1]) for i in range(n)]

x.sort(key = lambda x:x[1])
y.sort(key = lambda x:x[1])

x_dif = [((x[i][0], x[i+1][0]), abs(x[i+1][1]-x[i][1])) for i in range(n-1)]
y_dif = [((y[i][0], y[i+1][0]), abs(y[i+1][1]-y[i][1])) for i in range(n-1)]

xy_dif = x_dif + y_dif
xy_dif.sort(key = lambda x:x[1])

p = [-1]*n

def root(x):
  if p[x]<0:
    return x
  p[x] = root(p[x])
  return p[x]

ans = 0
for ab, cost in xy_dif:
  a, b = ab
  
  if root(a)!=root(b):
    p[root(a)] = root(b)
    ans += cost

print(ans)

Solution (Python):

import heapq
n = int(input())
stw = []
x_list = []
y_list = []
for i in range(n):
  x, y = map(int, input().split())
  x_list += [[x, i]]
  y_list += [[y, i]]

x_list.sort()
y_list.sort()

for i in range(n-1):
  stw += [[x_list[i][1], x_list[i+1][1], abs(x_list[i][0]-x_list[i+1][0])]]
for i in range(n-1):
  stw += [[y_list[i][1], y_list[i+1][1], abs(y_list[i][0]-y_list[i+1][0])]]

stw.sort(key=lambda x:x[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 
    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():
  
  
  
  
  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

ans = kruskal()
print(ans)

Solution (Python):
from heapq import *
from collections import defaultdict
INF = float('inf')
class Prim:

    def __init__(self,N):
        self.N = N
        self.cost = defaultdict(list)
        self.used = [False for _ in range(N)]
    
    def setcost(self,u,v,w):
        self.cost[u].append((v,w))
        self.cost[v].append((u,w))
    
    def prim(self):
        que = []
        heapify(que)
        used = self.used
        for e in self.cost[0]:
            heappush(que,[e[1],e[0]])
        used[0] = True
        res = 0
        while que:
            p = heappop(que)
            cos,v = p
            if used[v]:continue
            self.used[v] = True
            for e in self.cost[v]:
                if not used[e[0]]:
                    heappush(que,[e[1],e[0]])      
            res += cos
        return res

def main():
    N = int(input())
    cost = []
    for i in range(N):
        x,y = map(int,input().split())
        cost.append((x,y,i))
    prim = Prim(N)
    x = tuple(sorted(cost,key=lambda x: x[0]))
    y = tuple(sorted(cost,key=lambda x: x[1]))
    for i in range(N-1):
        a,b,u = x[i]
        c,d,v = x[i+1]
        w = min(abs(a-c),abs(b-d))
        prim.setcost(u,v,w)
        e,f,s = y[i]
        g,h,t = y[i+1]
        u = min(abs(e-g),abs(f-h))
        prim.setcost(s,t,u)
    ans = prim.prim()
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
import heapq
from collections import defaultdict
N=int(input())
X=[]
Y=[]
dic_x=defaultdict(list)
dic_y=defaultdict(list)
for i in range(N):
  x,y=map(int,input().split())
  dic_x[x].append(i)
  dic_y[y].append(i)
  X.append(x)
  Y.append(y)
X=sorted(X)
Y=sorted(Y)
V=N
E=(V-1)*2
G=[]
for i in range(N-1):
  heapq.heappush(G,(X[i+1]-X[i],dic_x[X[i]].pop(),dic_x[X[i+1]][0]))
  heapq.heappush(G,(Y[i+1]-Y[i],dic_y[Y[i]].pop(),dic_y[Y[i+1]][0]))
 
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]

def Minmum_Spanning_Tree(G,V,E):
  uf=UnionFind(V)
  cnt=0
  tot_weight=0
  while cnt!=V-1:
    w,u,v=heapq.heappop(G)
    if uf.same(u-1,v-1)==False:
      uf.unite(u-1,v-1)
      tot_weight+=w
      cnt+=1
  return tot_weight

weight=Minmum_Spanning_Tree(G,V,E)
print(weight)

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

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

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

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

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

    def union(self,x,y):
        x_root = self.find(x)
        y_root = self.find(y)
        if(x == y):
            return

        if( self.parents[x_root] <= self.parents[y_root] ):
            self.parents[x_root] += self.parents[y_root]
            self.parents[y_root] = x_root
        else:
            self.parents[y_root] += self.parents[x_root]
            self.parents[x_root] = y_root

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

    def roots(self):
        ret = [ i for i in range(self.n) if self.parents[i] < 0]
        return ret

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

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

n = int(input())
xs = []
ys = []
for i in range(n):
    x,y = map(int, input().split())
    xs.append([x,i])
    ys.append([y,i])

xs.sort()
ys.sort()

edges = []
for tmp in [xs,ys]:
    for i in range(n-1):
        tmp_0 = tmp[i]
        tmp_1 = tmp[i+1]
        edges.append([ tmp_1[0] - tmp_0[0], tmp_1[1], tmp_0[1] ])

edges.sort()

ans = 0
uf = UnionFind(n)

for edge in edges:
    cost, a, b = edge
    if uf.same(a,b) == False:
        uf.union(a,b)
        ans += cost

    if( uf.size(a) == n):
        print(ans)
        exit()

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

edge = []
for i in range(n):
    x, a = X[i]
    y, s = Y[i]
    if i > 0:
        xb, b = X[i-1]
        ty, t = Y[i-1]
        edge.append((a, b, abs(x - xb)))
        edge.append((s, t, abs(y - ty)))
    if i + 1 < n:
        xb, b = X[i+1]
        ty, t = Y[i+1]
        edge.append((a, b, abs(x - xb)))
        edge.append((s, t, abs(y - ty)))

class Unionfind():
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x

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

    def union(self, x, y):
        xp = self.find(x)
        yp = self.find(y)
        if xp != yp:
            if self.table[xp] < self.table[yp]:
                self.table[xp] += self.table[yp]
                self.table[yp] = xp
            else:
                self.table[yp] += self.table[xp]
                self.table[xp] = yp

u = Unionfind(n)
ans = 0
for a, b, c in sorted(edge, key = lambda x: x[2]):
    if not u.same(a, b):
        ans += c
        u.union(a, b)
print(ans)

Solution (Python):
import bisect
import collections
import sys
import heapq

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 32


class UnionFind(object):
    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 members_dict(self):
        pass

    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 lmi():
    return list(map(int, input().split()))


def llmi_index(n):
    return [[i] + lmi() for i in range(n)]


N = int(input())
XY = llmi_index(N)
x_sorted = sorted(XY, key=lambda v: v[1])
y_sorted = sorted(XY, key=lambda v: v[2])



uf = UnionFind(N)
cost_hq = []  
for i in range(N - 1):
    cost = x_sorted[i + 1][1] - x_sorted[i][1]
    heapq.heappush(cost_hq, (cost, x_sorted[i][0], x_sorted[i + 1][0]))
for i in range(N - 1):
    cost = y_sorted[i + 1][2] - y_sorted[i][2]
    heapq.heappush(cost_hq, (cost, y_sorted[i][0], y_sorted[i + 1][0]))

ans = 0
while cost_hq:
    cost, index1, index2 = heapq.heappop(cost_hq)
    
    if uf.same(index1, index2):
        continue
    
    uf.union(index1, index2)
    ans += cost

print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
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()
edges=[]
for i in range(n-1):
  edges.append((abs(x[i][0]-x[i+1][0]),x[i][1],x[i+1][1]))
  edges.append((abs(y[i][0]-y[i+1][0]),y[i][1],y[i+1][1]))
edges.sort()
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 kruskal(n, edges):
    uf = UnionFind(n)
    res = 0
    for e in edges:
        w, s, t = e
        if not uf.same(s, t):
            res+=w
            uf.union(s, t)
    return res
print(kruskal(n, edges))

Solution (Python):
n = int(input())
stw = []
x_list = []
y_list = []
for i in range(n):
  x, y = map(int, input().split())
  x_list += [[x, i]]
  y_list += [[y, i]]
x_list.sort()
y_list.sort()

for [u, fr], [v, to] in zip(x_list, x_list[1:]):
  stw += [[abs(u-v), fr, to]]
for [u, fr], [v, to] in zip(y_list, y_list[1:]):
  stw += [[abs(u-v), fr, to]]

stw = sorted(stw, key=lambda x:x[0])

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():
  
  
  
  res = 0
  uf = UnionFind(n)
  
  for i in range(len(stw)):
    
    w, s, t = stw[i]
    if not uf.isSameGroup(s, t):
      uf.Unite(s, t)
      res += w
  return res

print(kruskal())

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):
from heapq import heappop, heapify
import sys
input = sys.stdin.buffer.readline

class UnionFind :
    """
    Union Find木
    ---
    頂点のインデックスは0~

    Attributes
    ---
    parent : list<int>
        親のリスト．parent[頂点のインデックス] = 親のインデックス
    height : list<int>
        各木の高さ
    size : list<int>
        各木の頂点数
    component : int
        連結成分の数
    """

    def __init__(self, size) :
        """
        Parameters
        ---
        size : int
            頂点数
        """
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        """
        親のインデックスの取得

        Parameters
        ---
        index : int
            取得する頂点のインデックス

        Returns
        ---
        rootIndex : int
            指定した頂点の根のインデックス
        """
        if self.parent[index] == index :  
            return index
        rootIndex = self.root(self.parent[index])  
        self.parent[index] = rootIndex  
        return rootIndex

    def union(self, index1, index2) :  
        """
        木の結合

        Parameters
        ---
        index1 : int
        index2 : int
            結合する頂点のインデックス
        """
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  
            return

        self.component -= 1  

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        """
        同じ木に属するかを判定する

        Parameters
        ---
        index1 : int
        index2 : int

        Returns
        ---
        boolean
        """
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        """
        指定した頂点の属する木の大きさを取得する
        """
        return self.size[self.root(index)]

    def getComponent(self) :
        """
        連結成分数を取得する
        """
        return self.component

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()
edges = []

for (u, fr), (v, to) in zip(X, X[1:]):
    edges.append((abs(u - v), fr, to,))
for (u, fr), (v, to) in zip(Y, Y[1:]):
    edges.append((abs(u - v), fr, to,))

heapify(edges)
tree = UnionFind(N)
ans = 0
while edges:
    cost, fr, to = heappop(edges)
    if not tree.isSameRoot(fr, to):
        ans += cost
        tree.union(fr, to)

print(ans)