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):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    

    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 i in range(N-1):
        cost.append([x_sort[i+1][0]-x_sort[i][0], x_sort[i][2], x_sort[i+1][2]])
        cost.append([y_sort[i+1][1]-y_sort[i][1], y_sort[i][2], y_sort[i+1][2]])
    cost.sort()
    

    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    
    def unite(x,y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True
    
    def same(x,y):
        return find(x) == find(y)

    par = [-1]*N

    res = 0
    for c, v1, v2 in cost:
        if not same(v1, v2):
            unite(v1, v2)
            res += c
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    

    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 i in range(N-1):
        cost.append([x_sort[i+1][0]-x_sort[i][0], x_sort[i][2], x_sort[i+1][2]])
        cost.append([y_sort[i+1][1]-y_sort[i][1], y_sort[i][2], y_sort[i+1][2]])
    cost = sorted(cost, key=lambda x: x[0])

    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    
    def unite(x,y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True
    
    def same(x,y):
        return find(x) == find(y)

    par = [-1]*N

    res = 0
    for c, v1, v2 in cost:
        if not same(v1, v2):
            unite(v1, v2)
            res += c
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
'''
https://atcoder.jp/contests/abc065/tasks/arc076_b
最小全域木を考える際にある頂点について他の頂点への最小コストを
考えて繋げていくのは間違い(全域木になる保証がない)
考えたいのはあくまでも全辺のコスト

今回はxとyでそれぞれソートして隣り合う2点のコストのみを考えれば良い
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    

    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 i in range(N-1):
        cost.append([abs(x_sort[i][0]-x_sort[i+1][0]), x_sort[i][2], x_sort[i+1][2]])
        cost.append([abs(y_sort[i][1]-y_sort[i+1][1]), y_sort[i][2], y_sort[i+1][2]])
    cost = sorted(cost, key=lambda x: x[0])

    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    
    def unite(x,y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True
    
    def same(x,y):
        return find(x) == find(y)

    par = [-1]*N

    res = 0
    for c, v1, v2 in cost:
        if not same(v1, v2):
            unite(v1, v2)
            res += c
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
'''
https://atcoder.jp/contests/abc065/tasks/arc076_b
最小全域木を考える際にある頂点について他の頂点への最小コストを
考えて繋げていくのは間違い(全域木になる保証がない)
考えたいのはあくまでも全辺のコスト

今回はxとyでそれぞれソートして隣り合う2点のコストのみを考えれば良い
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    

    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 i in range(N-1):
        cost.append([abs(x_sort[i][0]-x_sort[i+1][0]), x_sort[i][2], x_sort[i+1][2]])
        cost.append([abs(y_sort[i][1]-y_sort[i+1][1]), y_sort[i][2], y_sort[i+1][2]])
    cost = sorted(cost, key=lambda x: x[0])

    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    
    def unite(x,y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True
    
    def same(x,y):
        return find(x) == find(y)

    par = [-1]*N

    res = 0
    for c, v1, v2 in cost:
        if not same(v1, v2):
            unite(v1, v2)
            res += c
    print(res)


if __name__ == '__main__':
    main()

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

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

def union(x, y):

    x = find(x)
    y = find(y)

    if x == y:
        return

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

    parents[x] += parents[y]
    parents[y] = x

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

N = int(input())

parents = [-1] * N
ver_x = []
ver_y = []
for i in range(N):
    x,y = map(int, input().split())
    ver_x.append((x,i))
    ver_y.append((y,i))

ver_x.sort()
ver_y.sort()

edge_list = []

for i in range(N-1):
    x_dist = ver_x[i+1][0]-ver_x[i][0]
    y_dist = ver_y[i+1][0]-ver_y[i][0]

    edge_list.append((x_dist, ver_x[i+1][1], ver_x[i][1]))
    edge_list.append((y_dist, ver_y[i+1][1], ver_y[i][1]))

ans = 0

edge_list.sort()

for w,s,t in edge_list:
    if not same(s,t):
        union(s,t)
        ans += w
print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    n = I()
    p = LIR(n)
    for i in range(n):
        p[i].append(i)
    p.sort()
    v = []
    for i in range(n-1):
        x,y,c = p[i]
        a,b,d = p[i+1]
        v.append((min(abs(x-a),abs(y-b)),c,d))
    p.sort(key = lambda x:x[1])
    for i in range(n-1):
        x,y,c = p[i]
        a,b,d = p[i+1]
        v.append((min(abs(x-a),abs(y-b)),c,d))
    v.sort()
    par = [i for i in range(n)]
    rank = [0]*n
    ans = 0
    s = 1
    for c,a,b in v:
        if root(a) != root(b):
            ans += c
            s += 1
            if s >= n:
                break
            unite(a,b)
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    n = I()
    p = LIR(n)
    for i in range(n):
        p[i].append(i)
    p.sort()
    v = []
    for i in range(n-1):
        x,y,c = p[i]
        a,b,d = p[i+1]
        v.append((min(abs(x-a),abs(y-b)),c,d))
    p.sort(key = lambda x:x[1])
    for i in range(n-1):
        x,y,c = p[i]
        a,b,d = p[i+1]
        v.append((min(abs(x-a),abs(y-b)),c,d))
    v.sort()
    par = [i for i in range(n)]
    rank = [0]*n
    ans = 0
    s = 0
    for c,a,b in v:
        if root(a) != root(b):
            ans += c
            s += 1
            if s >= n:
                break
            unite(a,b)
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    n = I()
    p = LIR(n)
    for i in range(n):
        p[i].append(i)
    p.sort()
    v = []
    for i in range(n-1):
        x,y,c = p[i]
        a,b,d = p[i+1]
        v.append((min(abs(x-a),abs(y-b)),c,d))
    p.sort(key = lambda x:x[1])
    for i in range(n-1):
        x,y,c = p[i]
        a,b,d = p[i+1]
        v.append((min(abs(x-a),abs(y-b)),c,d))
    v.sort()
    par = [i for i in range(n)]
    rank = [0]*n
    ans = 0
    for c,a,b in v:
        if root(a) != root(b):
            ans += c
            unite(a,b)
    print(ans)
    return


if __name__ == "__main__":
    solve()

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

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

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

u, v, c = zip(*edge)

graph = csr_matrix((c, (u, v)), shape=(n, n))
mst = minimum_spanning_tree(graph, overwrite=True).astype(int)
ans = mst.sum()
print(ans)

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

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

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

u, v, c = zip(*edge)

graph = csr_matrix((c, (u, v)), shape=(n, n), dtype=int)
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(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(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 same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
import sys
input=sys.stdin.readline
n=int(input())
l=[tuple(map(int,input().split())) for i in range(n)]
l.sort()
import collections
d=collections.defaultdict(int)
j=1
for i in l:
    if d[i]==0:
        d[i]=j
        j+=1
pq=[]
for i in range(n-1):
    pq.append((l[i+1][0]-l[i][0],d[l[i]],d[l[i+1]]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
    pq.append((l[i+1][1]-l[i][1],d[l[i]],d[l[i+1]]))
ans=0
pq.sort()
uf=unionfind(n)
for c,x,y in pq:
    if not uf.same(x,y):
        ans+=c
        uf.unite(x,y)
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(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(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 same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
import sys
input=sys.stdin.readline
n=int(input())
l=[tuple(map(int,input().split())) for i in range(n)]
l.sort()
import collections
d=collections.defaultdict(int)
j=1
for i in l:
    if d[i]==0:
        d[i]=j
        j+=1
pq=[]
for i in range(n-1):
    pq.append((l[i+1][0]-l[i][0],d[l[i]],d[l[i+1]]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
    pq.append((l[i+1][1]-l[i][1],d[l[i]],d[l[i+1]]))
ans=0
pq.sort(key=lambda x:x[0])
uf=unionfind(n)
for c,x,y in pq:
    if not uf.same(x,y):
        ans+=c
        uf.unite(x,y)
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(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(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 same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
import sys
input=sys.stdin.readline
n=int(input())
l=[tuple(map(int,input().split())) for i in range(n)]
l.sort(key=lambda x:x[0])
import collections
d=collections.defaultdict(int)
j=1
for i in l:
    if d[i]==0:
        d[i]=j
        j+=1
pq=[]
for i in range(n-1):
    pq.append((l[i+1][0]-l[i][0],d[l[i]],d[l[i+1]]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
    pq.append((l[i+1][1]-l[i][1],d[l[i]],d[l[i+1]]))
ans=0
pq.sort(key=lambda x:x[0])
uf=unionfind(n)
for c,x,y in pq:
    if not uf.same(x,y):
        ans+=c
        uf.unite(x,y)
print(ans)

Solution (Python):

import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, x: "List[int]", y: "List[int]"):
    par = [-1] * N

    def getroot(a: int):
        if par[a] != -1:
            par[a] = getroot(par[a])
            return par[a]
        else:
            return a

    def union(a: int, b: int):
        par[getroot(b)] = getroot(a)

    xpts = sorted((xi, i) for i, xi in enumerate(x))
    ypts = sorted((yi, i) for i, yi in enumerate(y))
    edges = [
        (xj - xi, i, j) for (xi, i), (xj, j) in zip(xpts, xpts[1:])
    ] + [
        (yj - yi, i, j) for (yi, i), (yj, j) in zip(ypts, ypts[1:])
    ]
    edges.sort()
    ans = 0
    for cost, i, j in edges:
        if getroot(i) == getroot(j):
            continue
        union(i, j)
        ans += cost
    print(ans)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    x = [int()] * (N)  
    y = [int()] * (N)  
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)


if __name__ == '__main__':
    main()

Solution (Python):
def solve_abc065d():
    from collections import namedtuple
    from heapq import heappush, heappop
    from operator import attrgetter
    from itertools import tee
    import sys

    input = sys.stdin.readline

    City = namedtuple('City', 'x y idx')
    Edge = namedtuple('Edge', 'cost to')
    N = int(input())

    cities = []
    for city_idx in range(N):
        x, y = map(int, input().split())
        c_ = City(x, y, city_idx)
        cities.append(c_)
    cities_x_asc = sorted(cities, key=attrgetter('x'))
    cities_y_asc = sorted(cities, key=attrgetter('y'))

    graph = tuple(set() for _ in range(N))

    it_x = iter(cities_x_asc)
    gx1, gx2 = tee(it_x, 2)
    next(gx2)
    for c1, c2 in zip(gx1, gx2):
        d_ = c2.x - c1.x
        graph[c1.idx].add(Edge(d_, c2.idx))
        graph[c2.idx].add(Edge(d_, c1.idx))
    

    it_y = iter(cities_y_asc)
    gy1, gy2 = tee(it_y, 2)
    next(gy2)
    for c1, c2 in zip(gy1, gy2):
        d_ = c2.y - c1.y
        graph[c1.idx].add(Edge(d_, c2.idx))
        graph[c2.idx].add(Edge(d_, c1.idx))
    

    
    
    
    
    
    
    
    

    start = 0  

    used = [-1] * N
    used[start] = 1

    h = []
    for e_ in graph[start]:
        heappush(h, e_)

    mi = 0
    while h:
        e_ = heappop(h)
        if ~used[e_.to]: continue

        used[e_.to] = 1
        mi += e_.cost

        for ne_ in graph[e_.to]:
            if ~used[ne_.to]: continue
            heappush(h, ne_)

    

    print(mi)
    return


if __name__ == '__main__':
    solve_abc065d()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


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 = I()
    points = []
    G = [[] for _ in range(N)]
    Point = collections.namedtuple('Point', ['n', 'x', 'y'])
    Edge = collections.namedtuple('Edge', ['fr', 'to', 'cost'])
    for i in range(N):
        x, y = LI()
        points.append(Point(i, x, y))
    x_sorted = sorted(points, key=lambda p: p.x)
    y_sorted = sorted(points, key=lambda p: p.y)
    edges = []
    for i in range(N-1):
        p1, p2 = x_sorted[i], x_sorted[i+1]
        cost = p2.x - p1.x
        assert cost >= 0
        edges.append(Edge(p1.n, p2.n, cost))
        edges.append(Edge(p2.n, p1.n, cost))

        p3, p4 = y_sorted[i], y_sorted[i+1]
        cost = p4.y - p3.y
        assert cost >= 0
        edges.append(Edge(p3.n, p4.n, cost))
        edges.append(Edge(p4.n, p3.n, cost))

    
    sorted_edge = sorted(edges, key=lambda x: x.cost)
    uf = UnionFind(N)
    res = 0
    for i in range(len(sorted_edge)):
        edge = sorted_edge[i]
        if not uf.same(edge.fr, edge.to):
            uf.union(edge.fr, edge.to)
            res += edge.cost
    print(res)

main()

Solution (Python):



class UnionFind(object):
    '''Represents a data structure that tracks a set of elements partitioned
       into a number of disjoint (non-overlapping) subsets.
    Landau notation: O(α(n)), where α(n) is the inverse Ackermann function.
    See:
    https://www.youtube.com/watch?v=zV3Ul2pA2Fw
    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
    https://atcoder.jp/contests/abc120/submissions/4444942
    '''

    def __init__(self, number_count: int):
        '''
        Args:
            number_count: The size of elements (greater than 2).
        '''
        self.parent_numbers = [-1 for _ in range(number_count)]

    def find_root(self, number: int) -> int:
        '''Follows the chain of parent pointers from number up the tree until
           it reaches a root element, whose parent is itself.
        Args:
            number: The trees id (0-index).
        Returns:
            The index of a root element.
        '''
        if self.parent_numbers[number] < 0:
            return number

        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])
        return self.parent_numbers[number]

    def get_group_size(self, number: int) -> int:
        '''
        Args:
            number: The trees id (0-index).
        Returns:
            The size of group.
        '''
        return -self.parent_numbers[self.find_root(number)]

    def is_same_group(self, number_x: int, number_y: int) -> bool:
        '''Represents the roots of tree number_x and number_y are in the same
           group.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        return self.find_root(number_x) == self.find_root(number_y)

    def merge_if_needs(self, number_x: int, number_y: int) -> bool:
        '''Uses find_root to determine the roots of the tree number_x and
           number_y belong to. If the roots are distinct, the trees are combined
           by attaching the roots of one to the root of the other.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        x = self.find_root(number_x)
        y = self.find_root(number_y)

        if x == y:
            return False

        if self.get_group_size(x) >= self.get_group_size(y):
            self.parent_numbers[x] += self.parent_numbers[y]
            self.parent_numbers[y] = x
        else:
            self.parent_numbers[y] += self.parent_numbers[x]
            self.parent_numbers[x] = y
        return True


def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    x = [None for _ in range(n)]
    y = [None for _ in range(n)]

    for i in range(n):
        xi, yi = map(int, input().split())
        xi -= 1
        yi -= 1

        x[i] = (xi, i)
        y[i] = (yi, i)

    
    
    new_x = sorted(x)
    new_y = sorted(y)
    road = list()

    
    
    for _from, _to in zip(new_x, new_x[1:]):
        cost = abs(_from[0] - _to[0])
        road.append((_from[1], _to[1], cost))

    for _from, _to in zip(new_y, new_y[1:]):
        cost = abs(_from[0] - _to[0])
        road.append((_from[1], _to[1], cost))

    
    new_road = sorted(road, key=lambda x: x[2])
    uf = UnionFind(n)
    ans = 0

    
    for nr in new_road:
        if uf.merge_if_needs(nr[0], nr[1]):
            ans += nr[2]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):



class UnionFind(object):
    '''Represents a data structure that tracks a set of elements partitioned
       into a number of disjoint (non-overlapping) subsets.
    Landau notation: O(α(n)), where α(n) is the inverse Ackermann function.
    See:
    https://www.youtube.com/watch?v=zV3Ul2pA2Fw
    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
    https://atcoder.jp/contests/abc120/submissions/4444942
    '''

    def __init__(self, number_count: int):
        '''
        Args:
            number_count: The size of elements (greater than 2).
        '''
        self.parent_numbers = [-1 for _ in range(number_count)]

    def find_root(self, number: int) -> int:
        '''Follows the chain of parent pointers from number up the tree until
           it reaches a root element, whose parent is itself.
        Args:
            number: The trees id (0-index).
        Returns:
            The index of a root element.
        '''
        if self.parent_numbers[number] < 0:
            return number

        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])
        return self.parent_numbers[number]

    def get_group_size(self, number: int) -> int:
        '''
        Args:
            number: The trees id (0-index).
        Returns:
            The size of group.
        '''
        return -self.parent_numbers[self.find_root(number)]

    def is_same_group(self, number_x: int, number_y: int) -> bool:
        '''Represents the roots of tree number_x and number_y are in the same
           group.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        return self.find_root(number_x) == self.find_root(number_y)

    def merge_if_needs(self, number_x: int, number_y: int) -> bool:
        '''Uses find_root to determine the roots of the tree number_x and
           number_y belong to. If the roots are distinct, the trees are combined
           by attaching the roots of one to the root of the other.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        x = self.find_root(number_x)
        y = self.find_root(number_y)

        if x == y:
            return False

        if self.get_group_size(x) >= self.get_group_size(y):
            self.parent_numbers[x] += self.parent_numbers[y]
            self.parent_numbers[y] = x
        else:
            self.parent_numbers[y] += self.parent_numbers[x]
            self.parent_numbers[x] = y
        return True


def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    x = [None for _ in range(n)]
    y = [None for _ in range(n)]

    for i in range(n):
        xi, yi = map(int, input().split())
        xi -= 1
        yi -= 1

        x[i] = (xi, i)
        y[i] = (yi, i)

    new_x = sorted(x)
    new_y = sorted(y)
    road = list()

    for _from, _to in zip(new_x, new_x[1:]):
        cost = abs(_from[0] - _to[0])
        road.append((_from[1], _to[1], cost))

    for _from, _to in zip(new_y, new_y[1:]):
        cost = abs(_from[0] - _to[0])
        road.append((_from[1], _to[1], cost))

    new_road = sorted(road, key=lambda x: x[2])
    uf = UnionFind(n)
    ans = 0

    for nr in new_road:
        if uf.merge_if_needs(nr[0], nr[1]):
            ans += nr[2]

    print(ans)


if __name__ == '__main__':
    main()