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):
import sys
from heapq import heappush, heappop, heapify

input = sys.stdin.buffer.readline
in_n = lambda: int(input())
in_nn = lambda: map(int, input().split())
in_s = lambda: input().rstrip().decode('utf-8')
in_map = lambda: [s == ord('.') for s in input() if s != ord('\n')]

MOD = 10**9 + 7
INF = 8 * 10**18



def prims_algorithm(N, cost):

    used = [False] * N
    used[0] = True
    que = [(c, w) for c, w in cost[0]]
    heapify(que)

    ret = 0
    while que:
        cv, v = heappop(que)
        if used[v]:
            continue
        used[v] = True
        ret += cv
        for c, w in cost[v]:
            if used[w]:
                continue
            heappush(que, (c, w))

    return ret


def main():

    N = in_n()
    x = [0] * N
    y = [0] * N

    for i in range(N):
        x[i], y[i] = in_nn()

    sort_ind_x = sorted(range(N), key=lambda i: x[i])
    sort_ind_y = sorted(range(N), key=lambda i: y[i])

    cost = [[] for _ in range(N)]
    for i in range(N - 1):
        j1, j2 = sort_ind_x[i], sort_ind_x[i + 1]
        c = abs(x[j1] - x[j2])
        cost[j1].append((c, j2))
        cost[j2].append((c, j1))

        j1, j2 = sort_ind_y[i], sort_ind_y[i + 1]
        c = abs(y[j1] - y[j2])
        cost[j1].append((c, j2))
        cost[j2].append((c, j1))

    ans = prims_algorithm(N, cost)
    print(ans)


if __name__ == '__main__':
    main()

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

input = sys.stdin.buffer.readline
in_n = lambda: int(input())
in_nn = lambda: map(int, input().split())
in_s = lambda: input().rstrip().decode('utf-8')
in_map = lambda: [s == ord('.') for s in input() if s != ord('\n')]

MOD = 10**9 + 7
INF = 8 * 10**18


def main():

    N = in_n()
    x = [0] * N
    y = [0] * N

    for i in range(N):
        x[i], y[i] = in_nn()

    sort_ind_x = sorted(range(N), key=lambda i: x[i])
    sort_ind_y = sorted(range(N), key=lambda i: y[i])

    cost = [[] for _ in range(N)]
    for i in range(N - 1):
        j1, j2 = sort_ind_x[i], sort_ind_x[i + 1]
        c = abs(x[j1] - x[j2])
        cost[j1].append((c, j2))
        cost[j2].append((c, j1))

        j1, j2 = sort_ind_y[i], sort_ind_y[i + 1]
        c = abs(y[j1] - y[j2])
        cost[j1].append((c, j2))
        cost[j2].append((c, j1))

    used = [0] * N
    used[0] = 1
    que = [(c, w) for c, w in cost[0]]
    heapify(que)

    ans = 0
    while que:
        cv, v = heappop(que)
        if used[v]:
            continue
        used[v] = 1
        ans += cv
        for c, w in cost[v]:
            if used[w]:
                continue
            heappush(que, (c, w))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

input = sys.stdin.buffer.readline
in_n = lambda: int(input())
in_nn = lambda: map(int, input().split())
in_s = lambda: input().rstrip().decode('utf-8')
in_map = lambda: [s == ord('.') for s in input() if s != ord('\n')]

MOD = 10**9 + 7
INF = 8 * 10**18


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):
        ret = dict()
        for i in range(self.n):
            r = self.find(i)
            if r in ret:
                ret[r].append(i)
            else:
                ret[r] = [i]
        return ret

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


def main():

    N = in_n()
    x = [0] * N
    y = [0] * N

    for i in range(N):
        x[i], y[i] = in_nn()

    sort_ind_x = sorted(range(N), key=lambda i: x[i])
    sort_ind_y = sorted(range(N), key=lambda i: y[i])

    cost = []
    for i in range(N - 1):
        j1, j2 = sort_ind_x[i], sort_ind_x[i + 1]
        c = abs(x[j1] - x[j2])
        cost.append((c, j1, j2))

        j1, j2 = sort_ind_y[i], sort_ind_y[i + 1]
        c = abs(y[j1] - y[j2])
        cost.append((c, j1, j2))

    cost.sort()
    uni = UnionFind(N)
    ans = 0

    for c, v1, v2 in cost:
        if not uni.same(v1, v2):
            ans += c
            uni.union(v1, v2)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

from heapq import heappop, heappush

def prim(adjacent:list, root=0):
    '''
    Prim法。最小全域木のコストを求める。負の閉路も可
    --------
        adjacent : 隣接リスト
        root     : 探索開始頂点
    --------
        min_cost : 最小コスト
    '''
    n = len(adjacent)
    visited = [False] * n
    min_cost = 0
    q = [(0, root)]
    while q:
        weight, vi = heappop(q)
        if visited[vi]:
            continue
        visited[vi] = True
        min_cost += weight
        for vj, weight in adjacent[vi]:
            if not visited[vj]:
                heappush(q, (weight, vj))
    return min_cost

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

adjacent = [[] for _ in range(n)]
for i in range(n-1):
    x0, y0, v0 = xordered[i]
    x1, y1, v1 = xordered[i+1]
    weight = min(abs(x0-x1), abs(y0-y1))
    adjacent[v0].append((v1, weight))
    adjacent[v1].append((v0, weight))
    x0, y0, v0 = yordered[i]
    x1, y1, v1 = yordered[i+1]
    weight = min(abs(x0-x1), abs(y0-y1))
    adjacent[v0].append((v1, weight))
    adjacent[v1].append((v0, weight))

print(prim(adjacent))

Solution (Python):
from heapq import heappop, heappush

def prim(adjacent:list, root=0):
    n = len(adjacent)
    visited = [False] * n
    min_cost = 0
    q = [(0, root)]

    count = 0
    while q and count < n:
        weight, vi = heappop(q)
        if visited[vi]:
            continue
        visited[vi] = True
        min_cost += weight
        count += 1
        for vj, weight in adjacent[vi]:
            heappush(q, (weight, vj))
    return min_cost

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

adjacent = [[] for _ in range(n)]
for i in range(n-1):
    x0, y0, v0 = xordered[i]
    x1, y1, v1 = xordered[i+1]
    weight = min(abs(x0-x1), abs(y0-y1))
    adjacent[v0].append((v1, weight))
    adjacent[v1].append((v0, weight))
    x0, y0, v0 = yordered[i]
    x1, y1, v1 = yordered[i+1]
    weight = min(abs(x0-x1), abs(y0-y1))
    adjacent[v0].append((v1, weight))
    adjacent[v1].append((v0, weight))

print(prim(adjacent))

Solution (Python):
from heapq import heappop, heappush

def prim(adjacent:list, root=0):
    n = len(adjacent)
    visited = [False] * n
    min_cost = 0
    q = [(0, root)]
    while q:
        weight, vi = heappop(q)
        if visited[vi]:
            continue
        visited[vi] = True
        min_cost += weight
        for vj, weight in adjacent[vi]:
            heappush(q, (weight, vj))
    return min_cost

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

adjacent = [[] for _ in range(n)]
for i in range(n-1):
    x0, y0, v0 = xordered[i]
    x1, y1, v1 = xordered[i+1]
    weight = min(abs(x0-x1), abs(y0-y1))
    adjacent[v0].append((v1, weight))
    adjacent[v1].append((v0, weight))
    x0, y0, v0 = yordered[i]
    x1, y1, v1 = yordered[i+1]
    weight = min(abs(x0-x1), abs(y0-y1))
    adjacent[v0].append((v1, weight))
    adjacent[v1].append((v0, weight))

print(prim(adjacent))

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
import sys
input=sys.stdin.readline
class unionfind():
    def __init__(self,n):
        self.par = list(range(n))
        self.size = [1]*n
        self.rank = [0]*n
        self.n = n
        
    def root(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

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

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x==y:return
        else:
            if self.rank[x] < self.rank[y]:
                 x,y = y,x
            if self.rank[x] == self.rank[y]:
                self.rank[x]+=1
            self.par[y] = x
            
            self.size[x] +=self.size[y]
    def get_size(self,x):
        x = self.root(x)
        return self.size[x]
    def parent_set(self):
        for x in range(self.n):
            self.root(x)
        s = set()
        for par in self.par:
            s.add(par)
        return s

"""
edges :: [(cost,u,v) for every Edge]
"""
def Kruskal(edges,n):
    tot=0
    edges.sort()
    uf = unionfind(n)
    for cost,u,v in edges:
        if uf.same(u,v):
            pass
        else:
            uf.unite(u,v)
            tot+=cost
    return tot

xy=[]
n = ni()
for i in range(n):
    x,y=lma()
    xy.append((i,x,y))
xy.sort(key=lambda x:x[1])

ed=[]
INF=10**15
ip=INF
xp=INF
yp=INF
for i,x,y in xy:
    if ip!=INF:
        ed.append((x-xp,i,ip))
    ip=i;xp=x;yp=y

xy.sort(key=lambda x:x[2])

ip=INF
xp=INF
yp=INF
for i,x,y in xy:
    if ip!=INF:
        ed.append((y-yp,i,ip))
    ip=i;xp=x;yp=y

print(Kruskal(ed,n))

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

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

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

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


def kruskal(n, edges):
    """
    Solve Minimum Spanning Tree by Kruskal's algorithm.
    :param n: Number of nodes
    :param edges: [u, v, cost]
    :return: Total cost
    """
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    total_cost = 0
    for u, v, c in edges:
        if not uf.is_same(u, v):
            total_cost += c
            uf.union(u, v)
    return total_cost


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 x1, x2 in zip(X[:-1], X[1:]):
    edges.append([x1[1], x2[1], x2[0] - x1[0]])

for y1, y2 in zip(Y[:-1], Y[1:]):
    edges.append([y1[1], y2[1], y2[0] - y1[0]])

print(kruskal(N, edges))

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

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


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

diff_list = []
for i in range(N-1):
    diff = x_list[i+1][0] - x_list[i][0]
    diff_list.append((diff,x_list[i+1][1],x_list[i][1]))
    diff = y_list[i+1][0] - y_list[i][0]
    diff_list.append((diff,y_list[i+1][1],y_list[i][1]))

diff_list.sort()
uf = UnionFind(N)

cost = 0
for w,f,t in diff_list:
    if uf.same(f-1,t-1):
        continue
    cost += w
    uf.union(f-1,t-1)
    if uf.group_count == 1:
        break

print(cost)

Solution (Python):

import sys
import heapq


N = int(input())

X, Y = [], []
for n in range(N):
    x, y = map(int, sys.stdin.readline().strip().split())
    X.append((x, n))
    Y.append((y, n))


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

X.sort()
Y.sort()
for i in range(N - 1):
    d_u, u = X[i]
    d_v, v = X[i + 1]

    G[u].append((d_v - d_u, v))
    G[v].append((d_v - d_u, u))

    d_u, u = Y[i]
    d_v, v = Y[i + 1]

    G[u].append((d_v - d_u, v))
    G[v].append((d_v - d_u, u))



q = []
fp = [False] * N  
fp[0] = True

for d, u in G[0]:
    heapq.heappush(q, (d, u))

ans = 0
while q:
    d, u = heapq.heappop(q)

    if fp[u]:
        continue
    fp[u] = True
    ans += d

    for d_v, v in G[u]:
        if fp[v]:
            continue
        heapq.heappush(q, (d_v, v))

print(ans)

Solution (Python):

import sys
import heapq


N = int(input())

X, Y = [], []
for n in range(N):
    x, y = map(int, sys.stdin.readline().strip().split())
    X.append((x, n))
    Y.append((y, n))


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

X.sort()
Y.sort()
for i in range(N - 1):
    d_u, u = X[i]
    d_v, v = X[i + 1]

    G[u].append((d_v - d_u, v))
    G[v].append((d_v - d_u, u))

    d_u, u = Y[i]
    d_v, v = Y[i + 1]

    G[u].append((d_v - d_u, v))
    G[v].append((d_v - d_u, u))



q = []
fp = [False] * N  
fp[0] = True

for d, u in G[0]:
    heapq.heappush(q, (d, u))

ans = 0
while q:
    d, u = heapq.heappop(q)

    if fp[u]:
        continue
    fp[u] = True
    ans += d

    for d_v, v in G[u]:
        if fp[v]:
            continue
        heapq.heappush(q, (d_v, v))

print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.components = n  

    def root(self, x):
        if self.p[x] != x:
            stack = [x]
            while True:
                top = stack[-1]
                if self.p[top] == top:
                    break
                else:
                    stack.append(self.p[top])
            for v in stack:
                self.p[v] = top
        return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.p[x] = y
            self.components -= 1
    
    def same(self, x,y):
        return (self.root(x) == self.root(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()

edges = []
for i in range(N-1):
    edges.append([X[i+1][0]-X[i][0], X[i][1], X[i+1][1]])
    edges.append([Y[i+1][0]-Y[i][0], Y[i][1], Y[i+1][1]])
edges.sort()

UF = UnionFind(N)
ans = 0
for cost, s, t in edges:
    if UF.same(s,t): continue

    UF.unite(s,t)
    ans += cost
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.components = n  

    def root(self, x):
        if self.p[x] != x:
            x_now = x
            while self.p[x_now] != x_now:
                x_now = self.p[x_now]
            self.p[x] = x_now
        return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.p[x] = y
            self.components -= 1
    
    def same(self, x,y):
        return (self.root(x) == self.root(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()

edges = []
for i in range(N-1):
    edges.append([X[i+1][0]-X[i][0], X[i][1], X[i+1][1]])
    edges.append([Y[i+1][0]-Y[i][0], Y[i][1], Y[i+1][1]])
edges.sort()

UF = UnionFind(N)
ans = 0
for cost, s, t in edges:
    if UF.same(s,t): continue

    UF.unite(s,t)
    ans += cost
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**5)

class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.components = n  

    def root(self, x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.p[x] = y
            self.components -= 1
    
    def same(self, x,y):
        return (self.root(x) == self.root(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()

edges = []
for i in range(N-1):
    edges.append([X[i+1][0]-X[i][0], X[i][1], X[i+1][1]])
    edges.append([Y[i+1][0]-Y[i][0], Y[i][1], Y[i+1][1]])
edges.sort()

UF = UnionFind(N)
ans = 0
for cost, s, t in edges:
    if UF.same(s,t): continue

    UF.unite(s,t)
    ans += cost
print(ans)

Solution (Python):
N = int(input())
XYI = [tuple(map(int,input().split() + [i])) for i in range(N)]
sx = sorted(XYI, key=lambda x:x[0])
sy = sorted(XYI, key=lambda x:x[1])

es = []
for (x0,_,i0),(x1,_,i1) in zip(sx,sx[1:]):
  es.append((x1-x0, i0, i1))
for (_,y0,i0),(_,y1,i1) in zip(sy,sy[1:]):
  es.append((y1-y0, i0, i1))
es.sort(key=lambda x:x[0])
 
class UnionFind:
  def __init__(self,N):
    self.parent = [i for i in range(N)]
    self._size = [1] * N
    self.count = 0
  def root(self,a):
    if self.parent[a] == a:
      return a
    else:
      self.parent[a] = self.root(self.parent[a])
      return self.parent[a]
  def is_same(self,a,b):
    return self.root(a) == self.root(b)
  def unite(self,a,b):
    ra = self.root(a)
    rb = self.root(b)
    if ra == rb: return
    if self._size[ra] < self._size[rb]: ra,rb = rb,ra
    self._size[ra] += self._size[rb]
    self.parent[rb] = ra
    self.count += 1
  def size(self,a):
    return self._size[self.root(a)]

uf = UnionFind(N)
ans = 0
for d,a,b in es:
  if uf.is_same(a,b): continue
  uf.unite(a,b)
  ans += d
print(ans)

Solution (Python):
N = int(input())

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



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)


def size(x):
    return -par[find(x)]


V = N
v=[]

xy.sort()
for i in range(1,N):
    v.append([xy[i-1][2],xy[i][2],min(abs(xy[i][0]-xy[i-1][0]),abs(xy[i][1]-xy[i-1][1]))])
xy.sort(key = lambda x:x[1])
for i in range(1,N):
    v.append([xy[i-1][2],xy[i][2],min(abs(xy[i][0]-xy[i-1][0]),abs(xy[i][1]-xy[i-1][1]))])

v.sort(key = lambda x:x[2])



par = [-1]*V

cost = 0

for i in range(0,len(v),1):
    if not same(v[i][0],v[i][1]):
        unite(v[i][0],v[i][1])
        cost+=v[i][2]

print(cost)

Solution (Python):
from heapq import *
N = int(input())
X,Y=[],[]
for n in range(N):
  x,y=map(int,input().split())
  X.append((x, n))
  Y.append((y, n))
X.sort()
Y.sort()
D=[[] for v in range(N)]
for n in range(N-1):
  cost = X[n+1][0]-X[n][0]
  D[X[n+1][1]].append((cost,X[n][1]))
  D[X[n][1]].append((cost,X[n+1][1]))
  cost=Y[n+1][0]-Y[n][0]
  D[Y[n+1][1]].append((cost,Y[n][1]))
  D[Y[n][1]].append((cost,Y[n+1][1]))

visited=[0]*N
pq = []
for w, t in D[0]:
  heappush(pq,(w,t))
visited[0]=1

ans = 0
while pq:
  w,t=heappop(pq)
  if visited[t]:
    continue
  visited[t]=1
  ans+=w
  for w,s in D[t]:
    if visited[s]==0:
      heappush(pq,(w,s))
print (ans)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    xy = [LI() for _ in range(N)]

    x = [(xy[i][0],i) for i in range(N)]
    y = [(xy[i][1],i) for i in range(N)]

    x.sort()
    y.sort()

    edge = []
    p,i = x[0]
    for q,j in x[1:]:
        edge.append((q-p,i,j))
        p,i = q,j

    p,i = y[0]
    for q,j in y[1:]:
        edge.append((q-p,i,j))
        p,i = q,j

    edge.sort()

    g = [i for i in range(N + 1)]
    g_num = [1 for i in range(N + 1)]

    def find(x):
        if g[x] == x: return x
        g[x] = find(g[x])
        return g[x]

    def union(x, y):
        if find(x) == find(y): return
        if g_num[g[x]] < g_num[g[y]]: x, y = y, x
        g_num[g[x]] += g_num[g[y]]
        g_num[g[y]] = 0
        g[g[y]] = g[x]

    ans = 0
    for v,i,j in edge:
        if find(i) != find(j):
            ans += v
            union(i,j)

    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):


class UnionFind:

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

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

    def unite(self, u, v):  
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        if self.parents[u] > self.parents[v]:  
            u, v = v, u
        self.parents[u] += self.parents[v]
        self.parents[v] = u

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

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

import sys
input = sys.stdin.readline

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

X = sorted(XY, key=lambda x: x[0])
Y = sorted(XY, key=lambda x: x[1])

dist = []
for i in range(N - 1):
    
    dist.append([X[i + 1][0] - X[i][0], X[i][2], X[i + 1][2]])
    dist.append([Y[i + 1][1] - Y[i][1], Y[i][2], Y[i + 1][2]])

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

uf = UnionFind(N)

for cost, i, j in dist:
    if uf.same(i, j):
        continue
    uf.unite(i, j)
    ans += cost

print(ans)

Solution (Python):


class UnionFind:

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

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

    def unite(self, u, v):  
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        if self.parents[u] > self.parents[v]:  
            u, v = v, u
        self.parents[u] += self.parents[v]
        self.parents[v] = u

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

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


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

X = sorted(XY, key=lambda x: x[0])
Y = sorted(XY, key=lambda x: x[1])

dist = []
for i in range(N - 1):
    
    dist.append([X[i + 1][0] - X[i][0], X[i][2], X[i + 1][2]])
    dist.append([Y[i + 1][1] - Y[i][1], Y[i][2], Y[i + 1][2]])

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

uf = UnionFind(N)

for cost, i, j in dist:
    if uf.same(i, j):
        continue
    uf.unite(i, j)
    ans += cost

print(ans)

Solution (Python):


class UnionFind:

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

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

    def unite(self, u, v):  
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        if self.parents[u] > self.parents[v]:  
            u, v = v, u
        self.parents[u] += self.parents[v]
        self.parents[v] = u

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

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


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

X = sorted(XY, key=lambda x: x[0])
Y = sorted(XY, key=lambda x: x[1])

side = []
for i in range(N - 1):
    
    side.append([X[i + 1][0] - X[i][0], X[i][2], X[i + 1][2]])
    side.append([Y[i + 1][1] - Y[i][1], Y[i][2], Y[i + 1][2]])

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

uf = UnionFind(N)

for cost, i, j in side:
    if uf.same(i, j):
        continue
    uf.unite(i, j)
    ans += cost

print(ans)

Solution (Python):
with open(0) as f:
    N, *xy = map(int, f.read().split())

from collections import namedtuple
v = namedtuple('v',['coordinate','num'])


X = sorted([v(x,i) for x,i in zip(xy[::2], range(N))])
Y = sorted([v(y,i) for y,i in zip(xy[1::2], range(N))])

diffiter = lambda X:zip(X[:len(X)-1], X[1:]) 
cost = lambda u,v:abs(u.coordinate - v.coordinate)
from itertools import chain
Edge = sorted([(cost(u,v), u.num, v.num) for u,v in chain(diffiter(X),diffiter(Y))])

root = namedtuple('root',['num', 'rank']) 
Root = [root(i,0) for i in range(N)]

def fr(i): 
    if i == Root[i].num:
        return Root[i]
    Root[i] = fr(Root[i].num)
    return Root[i]


def unionT(i, j): 
    p, q = fr(i), fr(j)
    if p.rank < q.rank:
        Root[p.num] = q
    elif p.rank > q.rank:
        Root[q.num] = p
    elif p.rank == q.rank:
        r, s = min(p, q), max(p, q)
        Root[r.num] = Root[s.num] = root(r.num, r.rank+1)
    

ans = 0

for w, i, j in Edge:
    if fr(i).num == fr(j).num: 
        continue
    else:
        unionT(i,j)
        ans += w
print(ans)