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.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)

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

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

        if x == y:
            return

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

    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
"""
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()
E=[]
ans=0
count=1
for i in range(N-1):
    a=X[i]
    b=X[i+1]
    c=Y[i]
    d=Y[i+1]
    E.extend([(b[0]-a[0],X[i][1],X[i+1][1]),(d[0]-c[0],Y[i][1],Y[i+1][1])])
E.sort()
"""
N = int(input())
P = [[i, list(map(int, input().split()))] for i in range(N)]

X = sorted([[i, xy[0]] for i, xy in P], key=lambda x: x[1])
Y = sorted([[i, xy[1]] for i, xy in P], key=lambda y: y[1])

Xe = [[X[i][0], X[i+1][0], abs(X[i][1]-X[i+1][1])] for i in range(N-1)]
Ye = [[Y[i][0], Y[i+1][0], abs(Y[i][1]-Y[i+1][1])] for i in range(N-1)]
E = sorted(Xe + Ye, key=lambda e: e[2])
U=UnionFind(N)
i=0
ans=0
count=1
while(count<N):
    v1,v2,cost=E[i]
    if not U.same_check(v1,v2):
        U.union(v1,v2)
        ans+=cost
        count+=1
    i+=1
print(ans)

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


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * 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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


E = []

Towns.sort(key=lambda t: t[1])
for i in range(1, N):
    t_prev, t_now = Towns[i - 1], Towns[i]
    E.append([t_prev[0], t_now[0], t_now[1] - t_prev[1]])

Towns.sort(key=lambda t: t[2])
for i in range(1, N):
    t_prev, t_now = Towns[i - 1], Towns[i]
    E.append([t_prev[0], t_now[0], t_now[2] - t_prev[2]])

E.sort(reverse=True, key=lambda e: e[2])
UF = UnionFind(N)

MST_cost = 0
i = 0


while i != N - 1:
    x, y, cost = E.pop()
    
    if not UF.same(x, y):
        MST_cost += cost
        UF.union(x, y)
        i += 1

print(MST_cost)

Solution (Python):
n = int(input())
xy = [[int(item) for item in input().split()] + [i] for i in range(n)]
xsort = sorted(xy, key=lambda x : x[0])
ysort = sorted(xy, key=lambda x : x[1])

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

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

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

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

edge = []
for i in range(1, n):
    xdif = abs(xsort[i-1][0] - xsort[i][0])
    ydif = abs(ysort[i-1][1] - ysort[i][1])
    edge.append([xsort[i-1][2], xsort[i][2], xdif])
    edge.append([ysort[i-1][2], ysort[i][2], ydif])
edge.sort(key=lambda x : x[2])

UF = UnionFind(n)
cost = 0
for e in edge:
    if not UF.same_check(e[0], e[1]):
        UF.union(e[0], e[1])
        cost += e[2]

print(cost)

Solution (Python):
import heapq
def prim_heap():
    used = [True] * n
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res
n, *t = map(int, open(0).read().split())
x = sorted((x, i) for i, (x, y) in enumerate(zip(t[::2], t[1::2])))
y = sorted((y, i) for i, (x, y) in enumerate(zip(t[::2], t[1::2])))
edge = [[] for _ in range(n)]
for i, j in zip(x, x[1:]):
    a, b, c = i[1], j[1], j[0] - i[0]
    edge[a].append((c, b))
    edge[b].append((c, a))
for i, j in zip(y, y[1:]):
    a, b, c = i[1], j[1], j[0] - i[0]
    edge[a].append((c, b))
    edge[b].append((c, a))
print(prim_heap())

Solution (Python):
import heapq
def prim_heap():
    used = [True] * n
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res
n, *t = map(int, open(0).read().split())
x = sorted((x, i) for i, (x, y) in enumerate(zip(t[::2], t[1::2])))
y = sorted((y, i) for i, (x, y) in enumerate(zip(t[::2], t[1::2])))
edge = [[] for _ in range(n)]
for i, j in zip(x, x[1:]):
    a, b, c = i[1], j[1], j[0] - i[0]
    edge[a].append((c, b))
    edge[b].append((c, a))
for i, j in zip(y, y[1:]):
    a, b, c = i[1], j[1], j[0] - i[0]
    edge[a].append((c, b))
    edge[b].append((c, a))
print(prim_heap())

Solution (Python):
import sys
from heapq import heappush, heappop

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)  
        self.weight = [0] * (n+1)  

    def find(self, x):
        if self.root[x] == x:
            return x
        else:
            y = self.find(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            self.root[x] = y
            return self.root[x]

    def unite(self, x, y, w=0):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.root[rx] = ry
            self.size[ry] += self.size[rx]
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.root[ry] = rx
            self.size[rx] += self.size[ry]
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def diff(self, x, y):
        return self.weight[y] - self.weight[x]


def kruskal(D, n):
    G = []
    UF = UnionFind(n)
    while len(D) > 0:
        cost, n1, n2 = heappop(D)

        if UF.is_same(n1, n2):
            continue
        else:
            G.append((cost, n1, n2))
            UF.unite(n1, n2)

    return G

def main():
    input = sys.stdin.readline
    N = int(input())
    C = []
    for i in range(N):
        x, y = map(int, input().split())
        C.append((i, x, y))

    X = sorted(C, key=lambda x: x[1])
    Y = sorted(C, key=lambda x: x[2])

    D = []
    for i in range(N-1):
        a, xa, _ = X[i]
        b, xb, _ = X[i+1]

        c, _, yc = Y[i]
        d, _, yd = Y[i+1]


        heappush(D, (xb - xa, a, b))
        heappush(D, (yd - yc, c, d))

    G = kruskal(D, N)
    ans = 0
    for g in G:
        ans += g[0]

    return ans


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

Solution (Python):
import sys
from heapq import heappush, heappop

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

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

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

def kruskal(D, n):
    G = []
    UF = UnionFind(n)
    while len(D) > 0:
        cost, n1, n2 = heappop(D)

        if UF.is_same(n1, n2):
            continue
        else:
            G.append((cost, n1, n2))
            UF.unite(n1, n2)

    return G

def main():
    input = sys.stdin.readline
    N = int(input())
    C = []
    for i in range(N):
        x, y = map(int, input().split())
        C.append((i, x, y))

    X = sorted(C, key=lambda x: x[1])
    Y = sorted(C, key=lambda x: x[2])

    D = []
    for i in range(N-1):
        a, xa, _ = X[i]
        b, xb, _ = X[i+1]

        c, _, yc = Y[i]
        d, _, yd = Y[i+1]


        heappush(D, (xb - xa, a, b))
        heappush(D, (yd - yc, c, d))

    G = kruskal(D, N)
    ans = 0
    for g in G:
        ans += g[0]

    return ans


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

Solution (Python):
import heapq


class UnionFind:
    def __init__(self, size: int):
        self.__size = size
        self.__root = [-1] * size

    def find(self, x: int)->int:
        if self.__root[x] < 0:
            return x

        root = self.find(self.__root[x])
        self.__root[x] = root

        return root

    def same(self, x: int, y: int)->bool:
        return self.find(x) == self.find(y)

    def union(self, x: int, y: int):
        rx, ry = self.find(x), self.find(y)

        if rx == ry:
            return

        if self.__root[ry] < self.__root[rx]:
            rx, ry = ry, rx

        self.__root[rx] += self.__root[ry]
        self.__root[ry] = rx


class PriorityQueue:
    def __init__(self):
        self.__heap = []
        self.__count = 0

    def empty(self) -> bool:
        return self.__count == 0

    def dequeue(self):
        if self.empty():
            raise Exception('empty')
        self.__count -= 1
        return heapq.heappop(self.__heap)

    def enqueue(self, v):
        self.__count += 1
        heapq.heappush(self.__heap, v)

    def __len__(self):
        return self.__count


def kruskal(edges: list, size: int)->list:
    q = PriorityQueue()
    for c, u, v in edges:
        q.enqueue((c, u, v))
    uf = UnionFind(size)

    min_tree = []
    while not q.empty():
        c, u, v = q.dequeue()

        if not uf.same(u, v):
            uf.union(u, v)
            min_tree.append((c, u, v))

    return min_tree


def built(N: int, points: list)->int:
    edges = []
    points = [(i, x, y) for i, (x, y) in enumerate(points)]
    sorted_x = sorted(points, key=lambda p: p[1])
    sorted_y = sorted(points, key=lambda p: p[2])

    for i in range(N-1):
        u, ux, _ = sorted_x[i]
        v, vx, _ = sorted_x[i+1]
        edges.append((vx-ux, u, v))

        u, _, uy = sorted_y[i]
        v, _, vy = sorted_y[i+1]
        edges.append((vy-uy, u, v))

    tree = kruskal(edges, 2*(N-1))

    return sum(c for c, _, _ in tree)


if __name__ == "__main__":
    N = int(input())
    points = [tuple(map(int, input().split())) for _ in range(N)]
    ans = built(N, points)
    print(ans)

Solution (Python):

def kruskal(v_count: int, edges: list) -> int:
    """
    :param v_count: 頂点数
    :param edges: [(weight, from, to), ... ]
    """
    from itertools import islice
    tree = [-1]*v_count

    def get_root(x) -> int:
        if tree[x] < 0:
            return x
        tree[x] = get_root(tree[x])
        return tree[x]

    def unite(a) -> bool:
        x, y = get_root(a[1]), get_root(a[2])
        if x != y:
            big, small = (x, y) if tree[x] < tree[y] else (y, x)
            tree[big] += tree[small]
            tree[small] = big
        return x != y

    cost = 0
    for w, _s, _t in islice(filter(unite, sorted(edges)), v_count-1):
        cost += w
    return cost

import sys
from operator import itemgetter
N = int(input())

a = []
for i in range(N):
  ta,tb =map(int,input().split())
  a.append([i,ta,tb])

x_sorted, y_sorted = sorted(a, key=itemgetter(1)), sorted(a, key=itemgetter(2))
edges = []
append = edges.append
for (i, x1, y1), (j, x2, y2) in zip(x_sorted, x_sorted[1:]):
    append((x2-x1, i, j))
for (i, x1, y1), (j, x2, y2) in zip(y_sorted, y_sorted[1:]):
    append((y2-y1, i, j))

print(kruskal(N, edges))

Solution (Python):
def d_built(N, P):
    class UnionFind(object):
        def __init__(self, n):
            self.p = list(range(n))  
            self.rank = [0] * n  
            self.size = [1] * n  

        def union(self, x, y):  
            u = self.find(x)
            v = self.find(y)
            if u == v:  
                return
            if self.rank[u] < self.rank[v]:
                self.p[u] = v  
                self.size[v] += self.size[u]  
                self.size[u] = 0  
            else:
                
                self.p[v] = u
                self.size[u] += self.size[v]
                self.size[v] = 0
                if self.rank[u] == self.rank[v]:
                    
                    self.rank[u] += 1
            
            self.find(x)
            self.find(y)
            return None

        def find(self, x):  
            if self.p[x] != x:  
                self.p[x] = self.find(self.p[x])  
            return self.p[x]

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

    xs, ys = [], []
    for i, (x, y) in enumerate(P):
        xs.append((x, i))
        ys.append((y, i))
    xs.sort()
    ys.sort()

    
    x_edge, y_edge = [], []
    for i in range(N - 1):
        
        x_edge.append((xs[i][1], xs[i + 1][1], xs[i + 1][0] - xs[i][0]))
        y_edge.append((ys[i][1], ys[i + 1][1], ys[i + 1][0] - ys[i][0]))
    x_edge.extend(y_edge)  
    x_edge.sort(key=lambda x: x[2])  

    
    uf = UnionFind(N)
    edges = []  
    for x1, x2, cost in x_edge:
        if not uf.is_same(x1, x2):
            
            uf.union(x1, x2)
            edges.append(cost)
        if len(edges) == N - 1:
            break
    return sum(edges)

N = int(input())
P = [[int(i) for i in input().split()] for j in range(N)]
print(d_built(N, P))

Solution (Python):
N=int(input())
city=[]
for i in range(N):
    x,y=map(int,input().split())
    city.append((i,x,y))
city.sort(key=lambda x:x[1])
data=[]
for i in range(N-1):
    data.append((city[i][0],city[i+1][0],city[i+1][1]-city[i][1]))
city.sort(key=lambda y:y[2])
for i in range(N-1):
    data.append((city[i][0],city[i+1][0],city[i+1][2]-city[i][2]))
data.sort(key=lambda d:d[2])
idx=[-1]*N
def find(idx,x):
    if idx[x]<0:
        return x
    elif idx[x]>=0:
        idx[x]=find(idx,idx[x])
        return idx[x]
ans=0
for q in range(len(data)):
    i,j,d=data[q]
    iidx=find(idx,i)
    jidx=find(idx,j)
    if iidx==jidx:
        continue
    elif idx[iidx]<=idx[jidx]:
        idx[iidx]+=idx[jidx]
        idx[jidx]=iidx
        ans+=d
    elif idx[iidx]>idx[jidx]:
        idx[jidx]+=idx[iidx]
        idx[iidx]=jidx
        ans+=d
print(ans)

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

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

idx=[-1]*N
def find(idx,x):
    if idx[x]<0:
        return x
    elif idx[x]>=0:
        idx[x]=find(idx,idx[x])
        return idx[x]

ans=0
for q in range(len(data)):
    i,j,d=data[q]
    iidx=find(idx,i)
    jidx=find(idx,j)
    if iidx==jidx:
        continue
    elif idx[iidx]<=idx[jidx]:
        idx[iidx]+=idx[jidx]
        idx[jidx]=iidx
        ans+=d
    elif idx[iidx]>idx[jidx]:
        idx[jidx]+=idx[iidx]
        idx[iidx]=jidx
        ans+=d
print(ans)

Solution (Python):
n = int(input())
unil = [i for i in range(n)]
unih = [0 for _ in range(n)]

def root(p):
  if unil[p] == p:
    return p
  else:
    unil[p] = root(unil[p])
    return unil[p]

def union(p, q):
  pp, qp = root(p), root(q)
  if pp == qp:
    return
  else:
    if unih[pp] > unih[qp]:
      unil[qp] = pp
    elif unih[pp] < unih[qp]:
      unil[pp] = qp
    else:
      unil[max(pp, qp)] = min(pp, qp)
      unih[min(pp, qp)] += 1

xlist, ylist = [], []
for _ in range(n):
  x, y = map(int, input().split())
  xlist.append(x)
  ylist.append(y)

xsort = list(sorted(enumerate(xlist), key=lambda x: x[1]))
xd = [(i, j, x - prevx) for (i, prevx), (j, x) in zip(xsort, xsort[1:])]
ysort = list(sorted(enumerate(ylist), key=lambda x: x[1]))
yd = [(i, j, y - prevy) for (i, prevy), (j, y) in zip(ysort, ysort[1:])]
xyd = sorted(xd + yd, key=lambda x: x[2])

ans = 0
for i, j, d in xyd:
  if root(i) == root(j):
    continue
  else:
    ans += d
    union(i, j)
print(ans)

Solution (Python):
import sys
N = int(input())
city_ls = list()
for i in range(N):
    city_ls.append([int(i) for i in sys.stdin.readline().split()])
sort_by_x = sorted([[i, j] for i,j in city_ls], key=lambda x:x[0])
G = []
pos2id = {tuple(j) : i for i, j in enumerate(city_ls)}
for i in range(len(sort_by_x)-1):
    current_by_x = sort_by_x[i]
    next_by_x = sort_by_x[i + 1]
    G.append((abs(current_by_x[0] - next_by_x[0]),current_by_x, next_by_x))
sort_by_x.sort(key=lambda x:x[1])
for i in range(len(sort_by_x) - 1):
    current_by_x = sort_by_x[i]
    next_by_x = sort_by_x[i + 1]
    G.append((abs(current_by_x[1] - next_by_x[1]), current_by_x, next_by_x))
G.sort(key=lambda x:x[0])
sum_cost = 0
par = [i for i in range(N)]
rank = [1 for i in range(N)]
def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        pass
    else:
        if rank[x] > rank[y]:
            par[y] = x
            rank[x] += rank[y]
        else:
            par[x] = par[y]
            rank[y] += rank[x]

def is_same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False

for i in G:
    (cost, _from, _to) = i
    _from = pos2id[tuple(_from)]
    _to = pos2id[tuple(_to)]
    if is_same(_from, _to):
        continue
    unite(_from, _to)
    sum_cost += cost
print(sum_cost)

Solution (Python):
import array
import collections


Edge = collections.namedtuple("Edge", "start end weight")


class UnionFind(object):

    def __init__(self, number_of_nodes):  
        self.par = array.array("L", range(number_of_nodes))
        self.rank = array.array("L", (0 for i in range(number_of_nodes)))

    def root(self, node):  
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r  
            return r

    def in_the_same_set(self, node1, node2):  
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):  
        x = self.root(node1)
        y = self.root(node2)
        if x == y:
            pass
        elif self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1



def compute_mst_kruskal(max_v, edges):
    edges.sort(key=lambda edge: edge.weight)
    uf = UnionFind(max_v)
    mst = []
    for edge in edges:
        if not uf.in_the_same_set(edge.start, edge.end):
            uf.unite(edge.start, edge.end)
            mst.append(edge)
    return mst



N = int(input())
xy = [list(map(int, input().split())) + [i] for i in range(N)]
sort_x = sorted(xy,key = lambda x:x[0])
sort_y = sorted(xy,key = lambda x:x[1])


max_v, max_e = N,2*N
entire = []
for i in range(1,N):
    entire.append([sort_x[i][2], sort_x[i-1][2],sort_x[i][0] - sort_x[i-1][0]])
    entire.append([sort_y[i][2], sort_y[i-1][2],sort_y[i][1] - sort_y[i-1][1]])

edges = [Edge(*k) for k in entire]



mst = compute_mst_kruskal(max_v, edges)
print(sum(edge.weight for edge in mst))

Solution (Python):

from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007








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

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

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()
v = LIR(n)
l = [None for i in range(2*n-2)]
for i in range(n):
    v[i].append(i)
par = [i for i in range(n)]
rank = [0 for i in range(n)]
v.sort(key = lambda x:x[0])
for i in range(n-1):
    l[i] = [v[i][2],v[i+1][2],v[i+1][0]-v[i][0]]
v.sort(key = lambda x:x[1])
for i in range(n-1):
    l[i+n-1] = [v[i][2],v[i+1][2],v[i+1][1]-v[i][1]]
l.sort(key = lambda x:x[2])
k = 0
ans = 0
for i in range(2*n-2):
    x,y,c = l[i]
    if not same(x,y):
        k += 1
        ans += c
        unite(x,y)
    if k == n-1:break
print(ans)

Solution (Python):

from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007








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

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

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()
v = LIR(n)
l = defaultdict(int)
for i in range(n):
    v[i].append(i)
par = [i for i in range(n)]
rank = [0 for i in range(n)]
v.sort(key = lambda x:x[0])
for i in range(n-1):
    l[i] = [v[i][2],v[i+1][2],v[i+1][0]-v[i][0]]
v.sort(key = lambda x:x[1])
for i in range(n-1):
    l[i+n-1] = [v[i][2],v[i+1][2],v[i+1][1]-v[i][1]]
l = list(l.values())
l.sort(key = lambda x:x[2])
k = 0
ans = 0
for i in range(2*n-2):
    x,y,c = l[i]
    if not same(x,y):
        k += 1
        ans += c
        unite(x,y)
    if k == n-1:break
print(ans)

Solution (Python):

from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007








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

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

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()
v = LIR(n)
l = [None for i in range(2*n-2)]
for i in range(n):
    v[i].append(i)
par = [i for i in range(n)]
rank = [0 for i in range(n)]
v.sort(key = lambda x:x[0])
for i in range(n-1):
    l[i] = [v[i][2],v[i+1][2],v[i+1][0]-v[i][0]]
v.sort(key = lambda x:x[1])
for i in range(n-1):
    l[i+n-1] = [v[i][2],v[i+1][2],v[i+1][1]-v[i][1]]
l.sort(key = lambda x:x[2])
k = 0
ans = 0
for i in range(2*n-2):
    x,y,c = l[i]
    if not same(x,y):
        k += 1
        ans += c
        unite(x,y)
    if k == n-1:break
print(ans)

Solution (Python):

from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007








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

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

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()
v = LIR(n)
l = []
for i in range(n):
    v[i].append(i)
par = [i for i in range(n)]
rank = [0 for i in range(n)]
v.sort(key = lambda x:x[0])
for i in range(n-1):
    l.append([v[i][2],v[i+1][2],v[i+1][0]-v[i][0]])
v.sort(key = lambda x:x[1])
for i in range(n-1):
    l.append([v[i][2],v[i+1][2],v[i+1][1]-v[i][1]])
l.sort(key = lambda x:x[2])
k = 0
ans = 0
for i in range(len(l)):
    x,y,c = l[i]
    if not same(x,y):
        k += 1
        ans += c
        unite(x,y)
    if k == n-1:break
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

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

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

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

N = int(input())

res = 0
pos = []
for i in range(N):
    p = tuple(int(x) for x in input().split())
    p = (p[0], p[1], i)
    pos.append(p)
x_order = sorted(pos)
y_order = sorted(pos, key=lambda x: x[1])

uf = UnionFind(N)
x_i = y_i = 0
num_edge = 0

edge = []
for i in range(len(x_order) - 1):
    v1 = x_order[i+1]
    v2 = x_order[i]
    edge.append((v1[0] - v2[0], v1[2], v2[2]))
    v1 = y_order[i+1]
    v2 = y_order[i]
    edge.append((v1[1] - v2[1], v1[2], v2[2]))

edge.sort()
i = 0
while num_edge < N-1:
    e = edge[i]
    i += 1
    if uf.same_check(e[1], e[2]):
        continue
    else:
        res += e[0]
        uf.union(e[1], e[2])
        num_edge += 1

print(res)

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

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

roads = []
for i in range(n - 1):
    i1, x1, y1 = ixy[i]
    i2, x2, y2 = ixy[i + 1]
    roads.append((x2 - x1, i1, i2))

ixy.sort(key=lambda x: x[2])
for i in range(n - 1):
    i1, x1, y1 = ixy[i]
    i2, x2, y2 = ixy[i + 1]
    roads.append((y2 - y1, i1, i2))

p = [i for i in range(n)]


def f_p(x):
    if x == p[x]:
        return x
    p[x] = f_p(p[x])
    return p[x]


roads.sort()
total_c = 0
for c, i1, i2 in roads:
    p1 = f_p(i1)
    p2 = f_p(i2)
    if p1 != p2:
        p[p1] = p2
        total_c += c

print(total_c)

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]

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

    def union(self, s1, s2):
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]


n = int(input())

x = dict()
y = dict()

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

x = sorted(x.items(), key=lambda t:t[1])
y = sorted(y.items(), key=lambda t:t[1])

r = []

for i in range(n - 1):
    r.append([x[i][0], x[i + 1][0], x[i + 1][1] - x[i][1]])
    r.append([y[i][0], y[i + 1][0], y[i + 1][1] - y[i][1]])

r = sorted(r, key=lambda t:t[2])

uft = UnionFind(n)

ans = 0
for a, b, c in r:
    ra = uft.find(a)
    rb = uft.find(b)
    if ra != rb:
        ans += c
        uft.union(ra, rb)

print(ans)