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.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find(self, x):
        if self.parent[x] != x:
            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 x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[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 kruskal(edges, size):
    uf = UnionFind(size)
    edges = sorted(edges, key=lambda e: e[2])
    ret = 0
    for u, v, weight in edges:
        if not uf.same(u, v):
            uf.unite(u, v)
            ret += weight
    return ret

N = int(input())
x = [0] * N
y = [0] * N
for i in range(N):
    a, b = map(int, input().split())
    x[i] = (a, i)
    y[i] = (b, i)
x.sort()
y.sort()
edges = []
for i in range(N-1):
    x1, u = x[i]
    x2, v = x[i+1]
    edges.append((u, v, x2 - x1))
    y1, u = y[i]
    y2, v = y[i+1]
    edges.append((u, v, y2 - y1))
ans = kruskal(edges, N)
print(ans)

Solution (Python):
INF = 10 ** 7
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from  heapq import heappop,heapify,heappush

def prim(G):
    ans = 0
    used = [0] * len(G)
    used[0] = 1
    q = []
    for e,c in G[0]:
        heappush(q,(c,e))
    
    while len(q):
        c1,e1 = heappop(q)
        if used[e1]:
            continue
        used[e1] = 1
        for e2,c2 in G[e1]:
            if used[e2] == 0:
                heappush(q,(c2,e2))
        ans += c1
    return ans

def main():
    n = int(input())
    G = [[] for _ in range(n)]
    P = []
    Q = []
    for i in range(n):
        x,y = map(int,input().split())
        P.append((i,x))
        Q.append((i,y))
    
    P.sort(key = lambda x:x[1])
    Q.sort(key = lambda x:x[1])
    for index in range(n - 1):
        i,x1 = P[index]
        j,x2 = P[index + 1]
        G[i].append((j,x2 - x1))
        G[j].append((i,x2 - x1))
        i,y1 = Q[index]
        j,y2 = Q[index + 1]
        G[i].append((j,y2 - y1))
        G[j].append((i,y2 - y1))
    
    ans = prim(G)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
def main():
    N = int(input())
    l = []
    for i in range(N):
        x, y = map(int, input().split())
        l.append((x,y,i))
    X = sorted(l, key=lambda x:x[0])
    Y = sorted(l, key=lambda x:x[1])
    d = {}
    for i in range(N-1):
        p = max(X[i][2], X[i+1][2])
        q = min(X[i][2], X[i+1][2])
        if (p, q) in d:
            d[(p, q)] = min(d[(p,q)], abs(X[i][0] - X[i+1][0]))
        else:
            d[(p, q)] = abs(X[i][0] - X[i+1][0])
        p = max(Y[i][2], Y[i+1][2])
        q = min(Y[i][2], Y[i+1][2])
        if (p, q) in d:
            d[(p, q)] = min(d[(p,q)], abs(Y[i][1] - Y[i+1][1]))
        else:
            d[(p, q)] = abs(Y[i][1] - Y[i+1][1])
    p = []
    q = []
    w = []
    for i in d:
        p.append(i[0])
        q.append(i[1])
        w.append(d[i])
    csr = csr_matrix((w, (p,q)), shape=(N,N))
    return int(minimum_spanning_tree(csr).sum())
print(main())

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

def main():
    N = int(input())
    M = 10**10
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    xy = [(x, i) for i, (x, _) in enumerate(XY)]
    yx = [(y, i) for i, (_, y) in enumerate(XY)]
    xy.sort()
    yx.sort()
    d = {}
    x1, i1 = xy[0]
    for x, i in xy[1:]:
        t = (i1, i) if i1 < i else (i, i1)
        d[t] = min(abs(x1 - x), d.get(t, M))
        x1, i1 = x, i
    x1, i1 = yx[0]
    for x, i in yx[1:]:
        t = (i1, i) if i1 < i else (i, i1)
        d[t] = min(abs(x1 - x), d.get(t, M))
        x1, i1 = x, i
    row = list(map(itemgetter(0), d.keys()))
    col = list(map(itemgetter(1), d.keys()))
    c = coo_matrix((list(d.values()), (row, col)), shape=(N, N))
    a = minimum_spanning_tree(c, overwrite=True)
    return int(a.sum())

print(main())

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

def main():
    N = int(input())
    M = 10**10
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    xy = [(x, i) for i, (x, _) in enumerate(XY)]
    yx = [(y, i) for i, (_, y) in enumerate(XY)]
    xy.sort()
    yx.sort()
    d = {}
    x1, i1 = xy[0]
    for x, i in xy[1:]:
        t = (i1, i) if i1 < i else (i, i1)
        d[t] = min(abs(x1 - x), d.get(t, M))
        x1, i1 = x, i
    x1, i1 = yx[0]
    for x, i in yx[1:]:
        t = (i1, i) if i1 < i else (i, i1)
        d[t] = min(abs(x1 - x), d.get(t, M))
        x1, i1 = x, i
    row = list(map(itemgetter(0), d.keys()))
    col = list(map(itemgetter(1), d.keys()))
    c = csr_matrix((list(d.values()), (row, col)), shape=(N, N))
    a = minimum_spanning_tree(c, overwrite=True)
    return int(a.sum())

print(main())

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

xy.sort(key=lambda x:x[0])
for i in range(n-1):
    x1,_,node1 = xy[i]
    x2,_,node2 = xy[i+1]
    cost = abs(x1-x2)
    link.append([node1,node2,cost])

xy.sort(key=lambda x:x[1])
for i in range(n-1):
    _,y1,node1 = xy[i]
    _,y2,node2 = xy[i+1]
    cost = abs(y1-y2)
    link.append([node1,node2,cost])
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 krs(g,num_v):
    g.sort(key=lambda x:x[2])

    uf = UnionFind(num_v)
    mst = []
    for edge in g:
        if not uf.same(edge[0], edge[1]):
            uf.union(edge[0], edge[1])
            mst.append(edge)
    return mst


ret = krs(link,n)
ans=0
for i in range(len(ret)):
    ans+=ret[i][2]
print(ans)

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

    
    def root(self,a):
        if self.parent[a] < 0:return a
        self.parent[a] = self.root(self.parent[a])
        return self.parent[a]
    
    
    def size(self,a):
        return -self.parent[self.root(a)]

    
    def connect(self,a,b):
        if self.root(a) == self.root(b):return False
        a = self.root(a);b = self.root(b)
        if self.size(a) < self.size(b):a,b = b,a
        self.parent[a] += self.parent[b]
        self.parent[b] = a
        return True

n = int(input())
x = [0]*n
y = [0]*n
for i in range(n):
    a,b = list(map(int,input().split()))
    x[i] = [a-1,i]
    y[i] = [b-1,i]
x.sort(key=lambda f: f[0])
y.sort(key=lambda f: f[0])

kouho = []
for i in range(n-1):
    kouho.append([abs(x[i][0] - x[i+1][0]),x[i][1],x[i+1][1]])
    kouho.append([abs(y[i][0] - y[i+1][0]),y[i][1],y[i+1][1]])
kouho.sort(key=lambda x: x[0])
uni = UnionFind(n)

ans = 0
for i in range(len(kouho)):
    c,f,t = kouho[i]
    if uni.root(f) == uni.root(t):continue
    ans += c
    uni.connect(f,t)
print(ans)

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

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

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

P.sort()
edge = [[] for _ in range(n)]
for i in range(n-1):
    d = min(abs(P[i+1][0]-P[i][0]), abs(P[i+1][1]-P[i][1]))
    edge[P[i][2]].append((d, P[i+1][2]))
    edge[P[i+1][2]].append((d, P[i][2]))

P.sort(key = lambda x: x[1])
for i in range(n-1):
    d = min(abs(P[i+1][0]-P[i][0]), abs(P[i+1][1]-P[i][1]))
    edge[P[i][2]].append((d, P[i+1][2]))
    edge[P[i+1][2]].append((d, P[i][2]))

print(prim_heap())

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

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

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

P.sort()
edge = [[] for _ in range(n)]
for i in range(n-1):
    d = min(abs(P[i+1][0]-P[i][0]), abs(P[i+1][1]-P[i][1]))
    edge[P[i][2]].append((d, P[i+1][2]))
    edge[P[i+1][2]].append((d, P[i][2]))

P.sort(key = lambda x: x[1])
for i in range(n-1):
    d = min(abs(P[i+1][0]-P[i][0]), abs(P[i+1][1]-P[i][1]))
    edge[P[i][2]].append((d, P[i+1][2]))
    edge[P[i+1][2]].append((d, P[i][2]))

print(prim_heap())

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

xi = [(i,x[i]) for i in range(n)]
yi = [(i,y[i]) for i in range(n)]

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

INF = float('inf')








xycost = []

for i in range(n-1):
    tmp = (xi[i][0], xi[i+1][0], xi[i+1][1] -xi[i][1])
    xycost.append(tmp)
    tmp = (yi[i][0], yi[i+1][0], yi[i+1][1] -yi[i][1])
    xycost.append(tmp)

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

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

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

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

        if x == y:
            return

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

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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

    def all_roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

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

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

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

uf = UnionFind(n)
ans = 0
for i,j, cost in xycost:
    if not uf.is_same(i,j):
        uf.union(i,j)
        ans += cost
    if uf.size == n: break

print(ans)

Solution (Python):

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


n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
b=[]
a.sort()

for i in range(n):
    a[i].append(i)



for i in range(n-1):
    b.append([a[i][2], a[i + 1][2], a[i + 1][0] - a[i][0]])

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

for i in range(n-1):
    b.append([a[i][2], a[i + 1][2], a[i + 1][1] - a[i][1]])

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

uf=UnionFind(n)
ans=0
cnt=0

for x,y,z in b:
    if not uf.same(x,y):
        uf.union(x,y)
        cnt+=1
        ans+=z
        if cnt==n-1:
            break
print(ans)

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


n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
b=[]
a.sort()

for i in range(n):
    a[i].append(i)



for i in range(n-1):
    b.append([a[i][2], a[i + 1][2], a[i + 1][0] - a[i][0]])

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

for i in range(n-1):
    b.append([a[i][2], a[i + 1][2], a[i + 1][1] - a[i][1]])

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

uf=UnionFind(n)
ans=0
cnt=0

for x,y,z in b:
    if not uf.same(x,y):
        uf.union(x,y)
        cnt+=1
        ans+=z
        if cnt==n-1:
            break
print(ans)

Solution (Python):

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

n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
b=[]
a.sort()

for i in range(n):
    a[i].append(i)



for i in range(n-1):
    b.append([a[i][2], a[i + 1][2], a[i + 1][0] - a[i][0]])

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

for i in range(n-1):
    b.append([a[i][2], a[i + 1][2], a[i + 1][1] - a[i][1]])

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

uf=UnionFind(n)
ans=0
cnt=0

for x,y,z in b:
    if not uf.same(x,y):
        uf.union(x,y)
        cnt+=1
        ans+=z
        if cnt==n-1:
            break
print(ans)

Solution (Python):

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

n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
b=[]
a.sort()

for i in range(n):
    a[i].append(i)



for i in range(n):
    if i==0:
        b.append([a[i][2],a[i+1][2], a[i+1][0]-a[i][0]])
    elif i==n-1:
        b.append([a[i][2],a[i-1][2], a[i][0]-a[i-1][0]])
    else:
        b.append([a[i][2],a[i-1][2], a[i][0]-a[i-1][0]])
        b.append([a[i][2], a[i + 1][2], a[i + 1][0] - a[i][0]])

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

for i in range(n):
    if i==0:
        b.append([a[i][2],a[i+1][2], a[i+1][1]-a[i][1]])
    elif i==n-1:
        b.append([a[i][2],a[i-1][2], a[i][1]-a[i-1][1]])
    else:
        b.append([a[i][2],a[i-1][2], a[i][1]-a[i-1][1]])
        b.append([a[i][2], a[i + 1][2], a[i + 1][1] - a[i][1]])

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

uf=UnionFind(n)
ans=0
cnt=0

for x,y,z in b:
    if not uf.same(x,y):
        uf.union(x,y)
        cnt+=1
        ans+=z
        if cnt==n-1:
            break
print(ans)

Solution (Python):
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 = int(input())
    uf = UnionFind(n)
    xs = [None]*n
    ys = [None]*n
    ps = [None]*n
    for i in range(n):
        x, y = map(int, input().split())
        ps[i] = [x, y]
        xs[i] = [x, i]
        ys[i] = [y, i]
    xs.sort()
    ys.sort()
    dist_xs = [None]*(n-1)
    dist_ys = [None]*(n-1)
    for i in range(n-1):
        dist_xs[i] = [xs[i+1][0] - xs[i][0], xs[i+1][1], xs[i][1]]
        dist_ys[i] = [ys[i+1][0] - ys[i][0], ys[i+1][1], ys[i][1]]
    dist_xs.sort()
    dist_ys.sort()
    x_i, y_i = 0, 0
    ans = 0
    while x_i < len(dist_xs) or y_i < len(dist_ys):
        if x_i < len(dist_xs) and y_i < len(dist_ys):
            if dist_xs[x_i][0] < dist_ys[y_i][0]:
                if not uf.same(dist_xs[x_i][1], dist_xs[x_i][2]):
                    uf.union(dist_xs[x_i][1], dist_xs[x_i][2])
                    ans += dist_xs[x_i][0]
                x_i += 1
            else:
                if not uf.same(dist_ys[y_i][1], dist_ys[y_i][2]):
                    uf.union(dist_ys[y_i][1], dist_ys[y_i][2])
                    ans += dist_ys[y_i][0]
                y_i += 1
        elif x_i < len(dist_xs):
            if not uf.same(dist_xs[x_i][1], dist_xs[x_i][2]):
                uf.union(dist_xs[x_i][1], dist_xs[x_i][2])
                ans += dist_xs[x_i][0]
            x_i += 1
        else:
            if not uf.same(dist_ys[y_i][1], dist_ys[y_i][2]):
                uf.union(dist_ys[y_i][1], dist_ys[y_i][2])
                ans += dist_ys[y_i][0]
            y_i += 1
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

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



xy.sort()
edge = [[] for i in range(n)]

for i in range(n-1):
    x1,x2=xy[i][0],xy[i+1][0]
    n1,n2=xy[i][2],xy[i+1][2]
    edge[n1].append((x2-x1,n2))
    edge[n2].append((x2-x1,n1))

xy.sort(key=lambda x: x[1])
for i in range(n-1):
    x1,x2=xy[i][1],xy[i+1][1]
    n1,n2=xy[i][2],xy[i+1][2]
    edge[n1].append((x2-x1,n2))
    edge[n2].append((x2-x1,n1))

print(prim_heap())

Solution (Python):
import sys


class UnionFind():
    def __init__(self, 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


N = int(input())
Px = []
Py = []
for k, s in enumerate(sys.stdin.readlines()):
    x, y = map(int, s.split())
    Px.append((x, k))
    Py.append((y, k))

edge = []

Px.sort()
Py.sort()
for i in range(N - 1):
    x0, k0 = Px[i]
    x1, k1 = Px[i + 1]
    d = abs(x0 - x1)
    edge.append((d, k0, k1))

    y0, k0 = Py[i]
    y1, k1 = Py[i + 1]
    d = abs(y0 - y1)
    edge.append((d, k0, k1))

edge.sort()
uf = UnionFind(N)
cnt = 0
for d, k0, k1 in edge:
    if uf.find(k0) != uf.find(k1):
        uf.union(k0, k1)
        cnt += d

print(cnt)

Solution (Python):
import sys


class UnionFind():
    def __init__(self, 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


N = int(input())
Px = []
Py = []
for k, s in enumerate(sys.stdin.readlines()):
    x, y = map(int, s.split())
    Px.append((x, k))
    Py.append((y, k))

edge = []

Px.sort()
Py.sort()
for i in range(N - 1):
    x0, k0 = Px[i]
    x1, k1 = Px[i + 1]
    d = abs(x0 - x1)
    edge.append((d, k0, k1))

    y0, k0 = Py[i]
    y1, k1 = Py[i + 1]
    d = abs(y0 - y1)
    edge.append((d, k0, k1))

edge.sort()
uf = UnionFind(N)
cnt = 0
for d, k0, k1 in edge:
    if uf.find(k0) != uf.find(k1):
        uf.union(k0, k1)
        cnt += d
    
    if uf.parents[uf.find(0)] == -N:
        break

print(cnt)

Solution (Python):
import sys


class UnionFind():
    def __init__(self, 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


N = int(input())
Px = []
Py = []
for k, s in enumerate(sys.stdin.readlines()):
    x, y = map(int, s.split())
    Px.append((x, k))
    Py.append((y, k))

edge = []

Px.sort()
Py.sort()
for i in range(N - 1):
    x0, k0 = Px[i]
    x1, k1 = Px[i + 1]
    d = abs(x0 - x1)
    edge.append((d, k0, k1))

    y0, k0 = Py[i]
    y1, k1 = Py[i + 1]
    d = abs(y0 - y1)
    edge.append((d, k0, k1))

edge.sort()
uf = UnionFind(N)
cnt = 0
for d, k0, k1 in edge:
    if uf.find(k0) != uf.find(k1):
        uf.union(k0, k1)
        cnt += d

print(cnt)

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


N = int(input())
Px = []
Py = []
for k, s in enumerate(sys.stdin.readlines()):
    x, y = map(int, s.split())
    Px.append((x, k))
    Py.append((y, k))

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

Px.sort()
for i in range(N - 1):
    x0, k0 = Px[i]
    x1, k1 = Px[i + 1]
    d = abs(x0 - x1)
    edge[k0].append((k1, d))
    edge[k1].append((k0, d))

Py.sort()
for i in range(N - 1):
    y0, k0 = Py[i]
    y1, k1 = Py[i + 1]
    d = abs(y0 - y1)
    edge[k0].append((k1, d))
    edge[k1].append((k0, d))

q = []
used = set([0])
for np, nd in edge[0]:
    heappush(q, (nd, np))

cnt = 0
while len(used) < N:
    d, p = heappop(q)
    if p in used:
        continue
    else:
        cnt += d
        used.add(p)
        for np, nd in edge[p]:
            heappush(q, (nd, np))

print(cnt)

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


N = int(input())
Px = []
Py = []
for k, s in enumerate(sys.stdin.readlines()):
    x, y = map(int, s.split())
    Px.append((x, k))
    Py.append((y, k))

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

Px.sort()
for i in range(N - 1):
    x0, k0 = Px[i]
    x1, k1 = Px[i + 1]
    d = abs(x0 - x1)
    edge[k0].append((k1, d))
    edge[k1].append((k0, d))

Py.sort()
for i in range(N - 1):
    y0, k0 = Py[i]
    y1, k1 = Py[i + 1]
    d = abs(y0 - y1)
    edge[k0].append((k1, d))
    edge[k1].append((k0, d))

q = []
used = set([0])
for np, nd in edge[0]:
    heappush(q, (nd, np))

cnt = 0
while len(used) < N:
    d, p = heappop(q)
    if p in used:
        continue
    else:
        cnt += d
        used.add(p)
        for np, nd in edge[p]:
            heappush(q, (nd, np))

print(cnt)

Solution (Python):
def get_root(s):
    if s != root[s]:
        root[s] = get_root(root[s])
        return root[s]
    return s

def unite(s, t):
    root_s = get_root(s)
    root_t = get_root(t)
    if not root_s == root_t:
        if rank[s] == rank[t]:
            root[root_t] = root_s
            rank[root_s] += 1
        elif rank[s] > rank[t]:
            root[root_t] = root_s
        else:
            root[root_s] = root_t

def same(s, t):
    if get_root(s) == get_root(t):
        return True
    else:
        return False

n = int(input())
root = [i for i in range(n)]
rank = [1 for _ in range(n)]
s, t = [], []
for i in range(n):
    x, y = map(int, input().split())
    s.append([x, i])
    t.append([y, i])
s.sort()
t.sort()
u = []
for i in range(n - 1):
    u.append([abs(s[i][0] - s[i + 1][0]), s[i][1], s[i + 1][1]])
    u.append([abs(t[i][0] - t[i + 1][0]), t[i][1], t[i + 1][1]])
u.sort()
c = 0
ans = 0
for v in u:
    if not same(v[1], v[2]):
        unite(v[1], v[2])
        c += 1
        ans += v[0]
    if c == n - 1:
        break
print(ans)

Solution (Python):
from heapq import heappop, heappush
INF = 10 ** 9 + 7

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

Xx = sorted((x, i) for i, (x, _) in enumerate(X))
Xy = sorted((y, i) for i, (_, y) in enumerate(X))

graph = [[] for _ in range(N)]
for i in range(N - 1):
    graph[Xx[i][1]].append((Xx[i + 1][1], Xx[i + 1][0] - Xx[i][0]))
    graph[Xx[i + 1][1]].append((Xx[i][1], Xx[i + 1][0] - Xx[i][0]))
    
    graph[Xy[i][1]].append((Xy[i + 1][1], Xy[i + 1][0] - Xy[i][0]))
    graph[Xy[i + 1][1]].append((Xy[i][1], Xy[i + 1][0] - Xy[i][0]))

min_cost = [INF] * N
visited = [False] * N

pq = []
heappush(pq, (0, 0))
ret = 0

while pq:
    cost, u = heappop(pq)
    if visited[u]:
        continue
    visited[u] = True
    min_cost[u] = cost
    ret += cost
    for v, c in graph[u]:
        if min_cost[v] > c:
            heappush(pq, (c, v))
            
print(ret)

Solution (Python):
def set(a, b):
  R[a].append(b)
  R[b].append(a)

N = int(input())
xy = [[i] + list(map(int, input().split())) for i in range(N)]
R = [[] for _ in range(N)]
xy.sort(key = lambda x: x[1])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  set(a[0], b[0])
xy.sort(key = lambda x: x[2])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  set(a[0], b[0])

xy.sort()
import heapq
q = [[0, 0]]
L = [True] * N
pop = heapq.heappop
push = heapq.heappush
ans = 0

for _ in range(N):
  k, t = pop(q)
  while not L[t]:
    k, t = pop(q)
  L[t] = False
  ans += k
  for i in R[t]:
    if L[i]:
      x = abs(xy[t][1] - xy[i][1])
      x = min(x, abs(xy[t][2] - xy[i][2]))
      push(q, [x, i])
print(ans)