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):
from operator import itemgetter
import heapq

N = int(input())
X = [[int(p) for p in input().split()] for _ in range(N)]

X.sort()
for i in range(N):
    X[i].append(i)
    
Y = sorted(X, key=itemgetter(1))

h = []
for i in range(N-1):
    heapq.heappush(h, (X[i+1][0]-X[i][0], i+1, i))
    heapq.heappush(h, (Y[i+1][1]-Y[i][1], Y[i+1][2], Y[i][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
        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 isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)
    
    def count(self, x):
        return -self.root[self.find_root(x)]
    
    
UF = UnionFind(N)
ans = 0
while h:
    t = heapq.heappop(h)
    if UF.isSameGroup(t[1], t[2]):
        continue
    ans += t[0]
    UF.unite(t[1], t[2])
    
print(ans)

Solution (Python):

import sys
input = sys.stdin.buffer.readline


from collections import defaultdict


def getlist():
	return list(map(int, input().split()))

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(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 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

class Kruskal:
    def __init__(self, Q, n):
        self.uf = UnionFind(n)
        self.cost = 0
        self.Q = Q
        for i in range(2 * (n - 1)):
            w, u, v = self.Q[i][0], self.Q[i][1], self.Q[i][2] 
            if self.uf.same_check(u, v) != True:
                self.uf.union(u, v)
                self.cost += w


def main():
    N = int(input())
    Lx = []
    Ly = []
    for i in range(N):
        x, y = getlist()
        Lx.append((x, i))
        Ly.append((y, i))
    Lx = sorted(Lx)
    Ly = sorted(Ly)
    Q = []

    for i in range(N - 1):
        u = Lx[i][1]
        v = Lx[i + 1][1]
        w = Lx[i + 1][0] - Lx[i][0]
        Q.append((w, u, v))
        u = Ly[i][1]
        v = Ly[i + 1][1]
        w = Ly[i + 1][0] - Ly[i][0]
        Q.append((w, u, v))
    Q = sorted(Q)
    Km = Kruskal(Q, N)
    print(Km.cost)

if __name__ == '__main__':
    main()

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

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

townx = sorted(town)
towny = sorted(town,key = lambda t : t[1])

road = []

for i in range(N-1):
    road.append([abs(townx[i][0]-townx[i+1][0]),townx[i][2],townx[i+1][2]])
    road.append([abs(towny[i][1]-towny[i+1][1]),towny[i][2],towny[i+1][2]])

road.sort()

uf = UnionFind(N)
ans = 0

for r in road:
    cost,t1,t2 = r
    if uf.same(t1,t2):
        continue
    uf.union(t1,t2)
    ans += cost
    
print(ans)

Solution (Python):
import operator
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = list(range(n))
        self.ranks = [0 for _ in range(n)]

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

    def merge(self, x, y):
        x = self.get_root(x)
        y = self.get_root(y)
        if x != y:
            if self.ranks[x] < self.ranks[y]:
                self.parents[x] = y
            else:
                self.parents[y] = x
                if self.ranks[x] == self.ranks[y]:
                    self.ranks[x] += 1


def kruskal(n_nodes, edges):
    edges.sort(key=operator.itemgetter(2))
    res = []
    uf = UnionFind(n_nodes)
    for e in edges:
        if uf.get_root(e[0]) != uf.get_root(e[1]):
            res.append(e)
            uf.merge(e[0], e[1])
    return res


n = ri()
ls = rils(n)
ls = list(enumerate(ls))

edges = []
ls.sort(key=lambda x: x[1][0])
for (i, (x0, y0)), (j, (x1, y1)) in zip(ls, ls[1:]):
    edges.append((i, j, min(abs(x0 - x1), abs(y0 - y1))))

ls.sort(key=lambda x: x[1][1])
for (i, (x0, y0)), (j, (x1, y1)) in zip(ls, ls[1:]):
    edges.append((i, j, min(abs(x0 - x1), abs(y0 - y1))))

res = kruskal(n, edges)
print(sum(x[2] for x in res))

Solution (Python):
import operator
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = list(range(n + 1))
        self.ranks = [0 for _ in range(n + 1)]

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

    def merge(self, x, y):
        x = self.get_root(x)
        y = self.get_root(y)
        if x != y:
            if self.ranks[x] < self.ranks[y]:
                self.parents[x] = y
            else:
                self.parents[y] = x
                if self.ranks[x] == self.ranks[y]:
                    self.ranks[x] += 1


def kruskal(n_nodes, edges):
    edges.sort(key=operator.itemgetter(2))
    res = []
    uf = UnionFind(n_nodes)
    for e in edges:
        if uf.get_root(e[0]) != uf.get_root(e[1]):
            res.append(e)
            uf.merge(e[0], e[1])
    return res


n = ri()
ls = rils(n)
ls = list(enumerate(ls))

edges = []
ls.sort(key=lambda x: x[1][0])
for (i, (x0, y0)), (j, (x1, y1)) in zip(ls, ls[1:]):
    edges.append((i, j, min(abs(x0 - x1), abs(y0 - y1))))

ls.sort(key=lambda x: x[1][1])
for (i, (x0, y0)), (j, (x1, y1)) in zip(ls, ls[1:]):
    edges.append((i, j, min(abs(x0 - x1), abs(y0 - y1))))

res = kruskal(n, edges)
print(sum(x[2] for x in res))

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


par  =[]
N = int(input())

graph = []

for i in range(N):
    x, y = [int(s) for s in input().split()]
    graph.append((i, x, y))

sort_x = sorted(graph, key=lambda x: x[1])
sort_y = sorted(graph, key=lambda x: x[2])

edges = []

for i in range(len(sort_x)-1):
    i1, a, b = sort_x[i]
    i2, c, d = sort_x[i+1]
    w = min(abs(a-c), abs(b-d))
    edges.append((i1, i2, w))
    i1, a, b = sort_y[i]
    i2, c, d = sort_y[i+1]
    w = min(abs(a-c), abs(b-d))
    edges.append((i1, i2, w))


for i in range(N+1):
    par.append(i)



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

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

def union(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        par[x] = y

ans = 0
edges = sorted(edges, key=lambda x: x[2])
for edge in edges:
    if not same(edge[0], edge[1]):
        union(edge[0], edge[1])
        ans += edge[2]
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
from collections import defaultdict

def init(n):
    return list(range(n+1))

def find(lis, x):
    if lis[x] == x:
        return x
    else:
        lis[x] = find(lis, lis[x])
        return lis[x]

def sameset(lis, x, y):
    return find(lis, x) == find(lis, y)

def union(lis, x, y):
    x = find(lis, x)
    y = find(lis, y)
    if x != y:
        lis[x] = y

N = int(input())
union_find_tree = init(N)

town = []

for i in range(N):
    x, y = map(int, input().split())
    town.append((i, x, y))

x_sorted_town = sorted(town, key=lambda x: x[1])
y_sorted_town = sorted(town, key=lambda x: x[2])

graph = []

pre_tx = x_sorted_town[0]
pre_ty = y_sorted_town[0]
pre_nx = town[pre_tx[0]]
pre_ny = town[pre_ty[0]]
for tx, ty in zip(x_sorted_town[1:], y_sorted_town[1:]):
    nx = town[tx[0]]
    ny = town[ty[0]]
    wx = min(abs(tx[1] - pre_tx[1]), abs(nx[2] - pre_nx[2]))
    wy = min(abs(ty[2] - pre_ty[2]), abs(ny[1] - pre_ny[1]))
    graph.append((nx[0], pre_nx[0], wx))
    graph.append((ny[0], pre_ny[0], wy))
    pre_tx = tx
    pre_ty = ty
    pre_nx = nx
    pre_ny = ny

cost = 0
for (s,t,w) in sorted(graph, key=lambda x: x[2]):
    if not sameset(union_find_tree,s,t):
        union(union_find_tree,s,t)
        cost += w
print(cost)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
from collections import defaultdict

import collections
import itertools
import operator


class UnionFind:
    def __init__(self, elems=None):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

        if elems is not None:
            for elem in elems:
                _, _ = self.parent[elem], self.rank[elem]

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

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

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

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]


'''
def init(n):
    return list(range(n+1))
def find(lis, x):
    if lis[x] == x:
        return x
    else:
        lis[x] = find(lis, lis[x])
        return lis[x]

def sameset(lis, x, y):
    return find(lis, x) == find(lis, y)

def union(lis, x, y):
    x = find(lis, x)
    y = find(lis, y)
    if x != y:
        lis[x] = y
'''

N = int(input())


town = []

for i in range(N):
    x, y = map(int, input().split())
    town.append((i, x, y))

x_sorted_town = sorted(town, key=lambda x: x[1])
y_sorted_town = sorted(town, key=lambda x: x[2])

graph = []

pre_tx = x_sorted_town[0]
pre_ty = y_sorted_town[0]
pre_nx = town[pre_tx[0]]
pre_ny = town[pre_ty[0]]
for tx, ty in zip(x_sorted_town[1:], y_sorted_town[1:]):
    nx = town[tx[0]]
    ny = town[ty[0]]
    wx = min(abs(tx[1] - pre_tx[1]), abs(nx[2] - pre_nx[2]))
    wy = min(abs(ty[2] - pre_ty[2]), abs(ny[1] - pre_ny[1]))
    graph.append((nx[0], pre_nx[0], wx))
    graph.append((ny[0], pre_ny[0], wy))
    pre_tx = tx
    pre_ty = ty
    pre_nx = nx
    pre_ny = ny

uf = UnionFind()

cost = 0
for (s,t,w) in sorted(graph, key=lambda x: x[2]):
    if not uf.are_same(s,t):
        uf.unite(s,t)
        cost += w
print(cost)

Solution (Python):
def find(A,x) -> int:
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a

def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx
def examD():
    N = I()
    x = [[] for _ in range(N)]; y = [[] for _ in range(N)]
    for i in range(N):
        a, b = LI()
        x[i] = (a-1,i)
        y[i] = (b-1,i)
    v = [ i for i in range(N)]
    x.sort(); y.sort()
    H = []
    heapify(H)
    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(H, (x2 - x1, j1, j2))
        heappush(H, (y2 - y1, k1, k2))
    ans = 0


    while H:
        w, s, t = heappop(H)
        if find(v, s) != find(v, t):
            union(v, s, t)
            ans += w
    print(ans)

import sys
import copy
import bisect
from heapq import *
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Solution (Python):
from heapq import heappush,heappop
n=int(input())
xy=[]
yx=[]
for i in range(n):
    x,y=map(int,input().split())
    xy.append([x,y,i])
    yx.append([y,x,i])
xy.sort()
yx.sort()
data=[[0,0] for i in range(n)]
for i in range(n):
    x,y,a=xy[i]
    data[a][0]=i
    y,x,a=yx[i]
    data[a][1]=i
ans=0
que=[[0,0]]
flag=[0]*n
count=0
while count<=n:
    l,a=heappop(que)
    if flag[a]==1:
        continue
    ans+=l
    flag[a]=1
    count+=1
    if count==n:
        break
    b,c=data[a]
    xb=xy[b][0]
    yc=yx[c][0]
    if 1<=b<=n-2:
        xd,yd,d=xy[b-1]
        xe,ye,e=xy[b+1]
        if flag[d]==0:
            heappush(que,[abs(xd-xb),d])
        if flag[e]==0:
            heappush(que,[abs(xe-xb),e])
    elif b==0:
        xe,ye,e=xy[1]
        if flag[e]==0:
            heappush(que,[abs(xb-xe),e])
    else:
        xd,yd,d=xy[n-2]
        if flag[d]==0:
            heappush(que,[abs(xb-xd),d])
    if 1<=c<=n-2:
        yg,xg,g=yx[c+1]
        yf,xf,f=yx[c-1]
        if flag[f]==0:
            heappush(que,[abs(yf-yc),f])
        if flag[g]==0:
            heappush(que,[abs(yg-yc),g])
    elif c==0:
        yg,xg,g=yx[1]
        if flag[g]==0:
            heappush(que,[abs(yg-yc),g])
    else:
        yf,xf,f=yx[n-2]
        if flag[f]==0:
            heappush(que,[abs(yf-yc),f])
print(ans)

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

B = [[j for j in i] for i in A]

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

M = []
for i in range(n-1):
    M.append([A[i][2], A[i+1][2], A[i+1][0]-A[i][0]])
    M.append([B[i][2], B[i+1][2], B[i+1][1]-B[i][1]])

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

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

    def size(self, x):
        if self.parents[x] < 0:
            return -self.parents[x]
        else:
            self.parents[x] = self.size(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


M.sort(key=lambda x:x[2])
ans = 0
U = UnionFind(n+1)
e = 0
for i in range(len(M)):
    if e == n-1:
        break
    if U.find(M[i][0]) != U.find(M[i][1]):
        U.union(M[i][0], M[i][1])
        ans += M[i][2]
        e += 1
        

print(ans)

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

B = [[j for j in i] for i in A]

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

M = []
for i in range(n-1):
    M.append([A[i][2], A[i+1][2], A[i+1][0]-A[i][0]])
    M.append([B[i][2], B[i+1][2], B[i+1][1]-B[i][1]])

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

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

    def size(self, x):
        if self.parents[x] < 0:
            return -self.parents[x]
        else:
            self.parents[x] = self.size(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


M.sort(key=lambda x:x[2])
ans = 0
U = UnionFind(n+1)
for i in range(len(M)):
    if U.find(M[i][0]) != U.find(M[i][1]):
        U.union(M[i][0], M[i][1])
        ans += M[i][2]
        

print(ans)

Solution (Python):
import heapq

class UnionFind:
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rnk = [0]*(n+1)
		self.Maxroot = -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]
			if self.root[x] < self.Maxroot:
				self.Maxroot = self.root[x]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			if self.root[y] < self.Maxroot:
				self.Maxroot = self.root[y]
			self.root[x] = y
			if self.rnk[x] == self.rnk[y]:
				self.rnk[y] += 1

	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)] * (-1)

N = int(input())
P = [list(map(int, input().split()))+[i] for i in range(N)]
Px = sorted(P)
Py = sorted(P, key = lambda x: x[1])

q = []
for i in range(N-1):
	x1, dumy1, p1 = Px[i]
	x2, dumy2, p2 = Px[i+1]

	heapq.heappush(q, [x2-x1, p1, p2])

for i in range(N-1):
	dumy1, y1, p1 = Py[i]
	dumy2, y2, p2 = Py[i+1]

	heapq.heappush(q, [y2-y1, p1, p2])

solve = UnionFind(N)

ans = 0
while not (solve.Maxroot == N * (-1)):
	d, p1, p2 = heapq.heappop(q)
	if not solve.isSameGroup(p1, p2):
		solve.Unite(p1, p2)
		ans += d

print(ans)

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

n = int(input())
x_list, y_list = [], []
for i in range(n):
    a, b = [ int(v) for v in input().split() ]
    x_list.append((a,b))
    y_list.append((b,a))
x_list.sort()
y_list.sort()

def swap(i):
    return (i[1],i[0])

def simplehash(i, r = 0):
    if r == 1:
        a, b = swap(i)
    else:
        a, b = i
    return a*10**10+b

x_node = [ ( (x_list[i+1][0] - x_list[i][0]), simplehash(x_list[i]), simplehash(x_list[i+1]) ) for i in range(n-1) ]
y_node = [ ( (y_list[i+1][0] - y_list[i][0]), simplehash(y_list[i],1), simplehash(y_list[i+1],1) ) for i in range(n-1) ]
node_set = set([])
for i in x_node:
    node_set.add(i[1])
    node_set.add(i[2])
node = list(sorted(node_set))
node_dic = { v : i for i, v in enumerate(node) }

x_list = [ (i[0], node_dic[i[1]], node_dic[i[2]] ) for i in x_node ]
y_list = [ (i[0], node_dic[i[1]], node_dic[i[2]] ) for i in y_node ]

connect_list = [ set([]) for i in range(n) ]
for i in x_list + y_list:
    c, a, b = i
    connect_list[a].add((c,b))
    connect_list[b].add((c,a))

def prim(in_connect_list,p,m):
    total_cost = 0
    connected_node = [ 0 for i in range(m) ]
    connected_node[p] = 1
    search_list = [p]
    search_heap = []
    while search_list != []:
        new_search_list = []
        for i in search_list:
            for c, k in connect_list[i]:
                if connected_node[k] == 0:
                    heapq.heappush(search_heap,(c,k))
          
        while search_heap != []:
            c, k = heapq.heappop(search_heap)
            if connected_node[k] == 0:
                new_search_list = [k]
                connected_node[k] = 1
                total_cost += c
                break
        search_list = new_search_list
    return total_cost

print(prim(connect_list,0,n))

Solution (Python):
class Prim():
    def __init__(self,N):
        import collections
        self.N = N
        self.edge = collections.defaultdict(list)
    def add(self,a,b,cost):
        self.edge[a].append((b,cost))
        self.edge[b].append((a,cost))
    def cut_edge(self,start=0):
        import heapq,collections
        
        edge_sum = 0
        node_flag = [False for _ in range(self.N)]
        node_flag[start] = True
        q = []
        for to,cost in self.edge[start]:
            heapq.heappush(q,(cost,start,to))
        while q :
            c,s,t = heapq.heappop(q)
            if node_flag[t] is False:
                
                edge_sum += c
                node_flag[t] = True
                for to,cost in self.edge[t]:
                    if not node_flag[to]:
                        heapq.heappush(q,(cost,t,to))
        return edge_sum

N = int(input())
graph = Prim(N)
xy = [list(map(int,input().split())) for _ in range(N)]
nx = [(i,xy[i][0]) for i in range(N)]
ny = [(i,xy[i][1]) for i in range(N)]
nx.sort(key=lambda x:x[1])
ny.sort(key=lambda x:x[1])

for i in range(N-1):
    prev_n,prev_x = nx[i]
    next_n,next_x = nx[i+1]
    graph.add(prev_n,next_n,next_x-prev_x)
    prev_n,prev_y = ny[i]
    next_n,next_y = ny[i+1]
    graph.add(prev_n,next_n,next_y-prev_y)
print(graph.cut_edge())

Solution (Python):



class Kruskal_UnionFind():
    
    def __init__(self, N):
        self.edges = []
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

    def add(self, u, v, d):
        """
        u = from, v = to, d = cost
        """
        self.edges.append([u, v, d])

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        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 size(self, x):
        x = self.find(x)
        return self.counter[x]

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

    def Kruskal(self):
        """
        return: 最小全域木のコストの和
        """
        edges = sorted(self.edges, key=lambda x: x[2])  
        res = 0
        for e in edges:
            if not self.same(e[0], e[1]):
                self.unite(e[0], e[1])
                res += e[2]
        return res

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

graph=Kruskal_UnionFind(n)

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

X_costs=[[XY[i-1][0],XY[i][0],abs(XY[i-1][1]-XY[i][1])] for i in range(1,n)]

XY=sorted(XY,key=lambda x: x[2])
Y_costs=[[XY[i-1][0],XY[i][0],abs(XY[i-1][2]-XY[i][2])] for i in range(1,n)]

for i in range(n-1):
    x0,x1,d=X_costs[i]
    graph.add(x0,x1,d)
    y0,y1,d=Y_costs[i]
    graph.add(y0,y1,d)
print(graph.Kruskal())

Solution (Python):
import sys
from operator import itemgetter
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def init(n):
  for i in range(N):
    par[i]=i
    rnk[i]=0
def find(x):
  if par[x]==x:
    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
  if (rnk[x]<rnk[y]):
    par[x]=y
  else:
    par[y]=x
    if(rnk[x]==rnk[y]):
      rnk[x]+=1
def same(x,y):
    return find(x)==find(y)

N = I()
xlist = []
ylist = []

par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
init(N)

for i in range(N):
  x, y = IL()
  xlist.append([x, i])
  ylist.append([y, i])
xlist.sort(key=itemgetter(0))
ylist.sort(key=itemgetter(0))

node = []
for i in range(N-1):
  x, xID = xlist[i]
  nextx, nextxID = xlist[i + 1]
  y, yID = ylist[i]
  nexty, nextyID = ylist[i + 1]
  
  node.append([nextx - x, xID, nextxID])
  node.append([nexty - y, yID, nextyID])
node.sort(key=itemgetter(0), reverse=True)

ans = 0
while node:
  val, i, j = node.pop()
  if same(i, j):
    continue
  else:
    unite(i, j)
    ans += val
print(ans)

Solution (Python):
def union(parent,size,a,b):
    x=find(parent,a)
    y=find(parent,b)
    if x!=y:
        if size[x]<size[y]:
            parent[x]=y 
            size[y]=size[x]+size[y]
        else:
            parent[y]=x 
            size[x]=size[x]+size[y]
    return parent,size 
def find(parent, a):
    while a != parent[a]:
            parent[a]=parent[parent[a]]
            a=parent[a]
    return a
n=int(input())
l=[]
for i in range(n):
    a,b=map(int,input().split())
    l.append([a,b,i])
l.sort(key=lambda x:x[0])
edges=[]
for i in range(1,n):
    edges.append([l[i][2],l[i-1][2],min(abs(l[i][0]-l[i-1][0]),abs(l[i][1]-l[i-1][1]))])
l.sort(key=lambda x:x[1])
for i in range(1,n):
    edges.append([l[i][2],l[i-1][2],min(abs(l[i][0]-l[i-1][0]),abs(l[i][1]-l[i-1][1]))])


parent=[i for i in range(n)]
size=[1]*n

edges.sort(key=lambda x:x[2])
cnt=0 
sm=0
for i in range(len(edges)):
    a=edges[i][0]
    b=edges[i][1]
    if find(parent,a)==find(parent,b):
        pass 
    else:
        parent,size=union(parent,size,a,b)
        sm+=edges[i][2]
        cnt+=1 
        if cnt==n-1:
            break 
print(sm)
parent=[i for i in range(n)]
size=[1]*n

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

N = int(input())
cityx = [[0,i]for i in range(N)]
cityy = [[0,i]for i in range(N)]
for i in range(N):
    x,y = map(int,input().split())
    cityx[i][0] = x
    cityy[i][0] = y

cityx.sort()
cityy.sort()
side = []
for i in range(N-1):
    side.append([cityx[i+1][0]-cityx[i][0], cityx[i+1][1], cityx[i][1]])
    side.append([cityy[i+1][0]-cityy[i][0], cityy[i+1][1], cityy[i][1]])
side.sort()
ans = 0
per = [i for i in range(N)]
rank = [0]*N
def find(x):
    if per[x] == x:
        return x
    else:
        per[x] = find(per[x])
        return per[x]

ans = 0

for cost,x,y in side:
    x = find(x)
    y = find(y)
    if x != y:
        ans += cost
        if rank[x] < rank[y]:
            per[x] = y
        else:
            per[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

print(ans)

Solution (Python):


import sys
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        
        
        self.par = [i for i in range(n+1)]
        
        self.rank = [0] * (n+1)
        
        self.size = [1] * (n+1)
        
        self.tree = [True] * (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:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

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

    def same(self, x, y):
        """ 同じ集合に属するか判定 """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """ あるノードの属する集合のノード数 """
        return self.size[self.find(x)]
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

    def len(self):
        """ 集合の数 """
        res = set()
        for i in range(self.n+1):
            res.add(self.find(i))
        
        return len(res) - 1

N = INT()
XY = []
for i in range(N):
    x, y = MAP()
    XY.append((i, x, y))

edges = []
XY.sort(key=itemgetter(1))
for i in range(N-1):
    i1, x1, _ = XY[i]
    i2, x2, _ = XY[i+1]
    cost = x2 - x1
    edges.append((i1, i2, cost))
XY.sort(key=itemgetter(2))
for i in range(N-1):
    i1, _, y1 = XY[i]
    i2, _, y2 = XY[i+1]
    cost = y2 - y1
    edges.append((i1, i2, cost))

uf = UnionFind(N)
ans = 0
edges.sort(key=itemgetter(2))
for a, b, cost in edges:
    if not uf.same(a, b):
        uf.union(a, b)
        ans += cost
print(ans)