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 networkx.utils import UnionFind
from operator import itemgetter
def input(): return sys.stdin.readline().rstrip()


def main():
    n = int(input())
    city = []
    for i in range(n):
        x, y = map(int, input().split())
        city.append((x, y, i))
    city.sort(key=itemgetter(0))
    kouho = []
    for i in range(n-1):
        kouho.append((city[i+1][0]-city[i][0], city[i][2], city[i+1][2]))
    city.sort(key=itemgetter(1))
    for i in range(n-1):
        kouho.append((city[i+1][1]-city[i][1], city[i][2], city[i+1][2]))
    kouho.sort(key=itemgetter(0))
    ans = 0
    num = n
    uf = UnionFind()
    for road in kouho:
        if uf[road[1]] != uf[road[2]]:
            uf.union(road[1],road[2])
            ans+=road[0]
            num-=1
            if num==1:
                print(ans)
                break


if __name__ == '__main__':
    main()

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 __str__(self):  return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def kruskal(G):

    G = sorted(G, key = lambda x: x[2])
    U = UnionFind(len(G))
    res = 0
    for e in G:
        s, t, w = e
        if not U.same(s, t):
            res += w
            U.union(s, t)
    return res

N = int(input())
in_list = []
for i in range(N):
    in1, in2 = list(map(int,input().split()))
    in_list.append([i, in1, in2])
    
x = sorted(in_list, key = lambda x: x[1])
y = sorted(in_list, key = lambda x: x[2])

G = []
for i in range(1, N):
    G.append([x[i - 1][0], x[i][0], x[i][1] - x[i - 1][1]])
    G.append([y[i - 1][0], y[i][0], y[i][2] - y[i - 1][2]])
    
ans = kruskal(G)
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) 
        self.size = [1]*n 
 
    def root(self, x): 
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 
 
    def merge(self, x, y): 
        x, y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: x,y=y,x 
        self.size[x] += self.size[y] 
        self.parent[y] = x 
        return True
 
    def issame(self, x, y): 
        return self.root(x) == self.root(y)
        
    def getsize(self,x): 
        return self.size[self.root(x)]



import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*xy = map(int,read().split())

mp = iter(xy)
xyi = [(x,y,i) for i,(x,y) in enumerate(zip(mp,mp))]

res = []

xyi.sort()
for (x,y,i),(z,w,j) in zip(xyi[1:],xyi):
    res.append((x-z,i,j))
xyi.sort(key = lambda x:x[1])
for (x,y,i),(z,w,j) in zip(xyi[1:],xyi):
    res.append((y-w,i,j))


res.sort()
UF = UnionFind(n)

num = 1
ans = 0
for d,i,j in res:
    if UF.merge(i,j):
        num += 1
        ans += d
    if num==n: break

print(ans)

Solution (Python):

n = int(input())
x = []
for i in range(0,n):
    X,Y = [int(_x) for _x in input().split()]
    x.append((i,X,Y))
x = sorted(x, key=lambda x:x[1])
y = sorted(x, key=lambda x:x[2])

g = [[] for _ in range(n)]
for j in range(1, len(x)):
    _i, _xx, _yy = x[j-1]
    i, xx, yy = x[j]
    dis1 = abs(_xx - xx)
    dis2 = abs(_yy - yy)
    g[i].append((dis1, _i))
    g[i].append((dis2, _i))
    g[_i].append((dis1, i))
    g[_i].append((dis2, i))

for j in range(1, len(y)):
    _i, _xx, _yy = y[j-1]
    i, xx, yy = y[j]
    dis1 = abs(_xx - xx)
    dis2 = abs(_yy - yy)
    g[i].append((dis1, _i))
    g[i].append((dis2, _i))
    g[_i].append((dis1, i))
    g[_i].append((dis2, 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

edge = g
print(prim_heap())

Solution (Python):
from heapq import *

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

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

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

H = []
heapify(H)
for i in range(N-1):
    x1, j1 = X[i][0], X[i][2]
    x2, j2 = X[i+1][0], X[i+1][2]
    heappush(H,(x2-x1, j1, j2))
    
    

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


for i in range(N-1):
    y1, j1 = X[i][1], X[i][2]
    y2, j2 = X[i+1][1], X[i+1][2]
    heappush(H,(y2-y1, j1, j2))
    

ans = 0

uf = UnionFind(N)
while H:
    w,s,t = heappop(H)
    if uf.find(s) != uf.find(t):
        uf.union(s,t)
        ans += w
print(ans)

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal



sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
MAX = float('inf')


class UnionFind:
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, N):
        if self.tree[N] == N:
            return N
        else:
            self.tree[N] = self.root(self.tree[N])
            return self.tree[N]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.tree[x] = y


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    uf = UnionFind(N)
    X, Y = [], []

    
    
    for n in range(N):
        x, y = il()
        X.append((x, n))
        Y.append((y, n))
    X.sort()
    Y.sort()

    
    
    dist = []
    for n in range(1, N):
        dist.append((abs(X[n][0] - X[n - 1][0]), X[n][1], X[n - 1][1]))
        dist.append((abs(Y[n][0] - Y[n - 1][0]), Y[n][1], Y[n - 1][1]))
    dist.sort()

    
    
    
    ret = 0
    for d, s, u in dist:
        if not uf.same(s, u):
            ret += d
            uf.unite(s, u)
    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

import copy






input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.root[self.find(x)]


n = ri()
d1=[tuple(rl())+tuple((i,)) for i in range(n)]
d2=d1[:]

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


    
edge.sort(key=lambda x: x[2])
res=0
uf = UnionFind(n)
for e in edge:
    if uf.same(e[0], e[1]):
        continue
    uf.unite(e[0], e[1])
    res+=e[2]
print(res)

Solution (Python):
import sys

import copy






input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.root[self.find(x)]


n = ri()
d1=[tuple(rl())+tuple((i,)) for i in range(n)]
d2=copy.deepcopy(d1)

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


    
edge.sort(key=lambda x: x[2])
res=0
uf = UnionFind(n)
for e in edge:
    if uf.same(e[0], e[1]):
        continue
    uf.unite(e[0], e[1])
    res+=e[2]
print(res)

Solution (Python):
import sys

import copy






input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.root[self.find(x)]


n = ri()
d1=[tuple(rl())+tuple((i,)) for i in range(n)]
d2=copy.deepcopy(d1)

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


    
edge.sort(key=lambda x: x[2])
res=0
uf = UnionFind(n)
for e in edge:
    if uf.same(e[0], e[1]):
        continue
    uf.unite(e[0], e[1])
    res+=e[2]
print(res)

Solution (Python):
import sys

import copy






input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.root[self.find(x)]


n = ri()
d=[tuple(rl())+tuple((i,)) for i in range(n)]

d.sort(key=lambda x: x[0])
edge=[]
for i in range(n-1):
    edge.append((d[i+1][2], d[i][2],d[i+1][0]-d[i][0]))
d.sort(key=lambda x:x[1])
for i in range(n-1):
    edge.append((d[i+1][2], d[i][2],d[i+1][1]-d[i][1]))
edge.sort(key=lambda x: x[2])
res=0
uf = UnionFind(n)
for e in edge:
    if uf.same(e[0], e[1]):
        continue
    uf.unite(e[0], e[1])
    res+=e[2]
print(res)

Solution (Python):
import sys

import copy






input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return -self.root[self.find(x)]


n = ri()
d=[tuple(rl())+tuple((i,)) for i in range(n)]

d.sort(key=lambda x: x[0])
edge=[]
for i in range(n-1):
    edge.append((d[i+1][2], d[i][2],d[i+1][0]-d[i][0]))
d.sort(key=lambda x:x[1])
for i in range(n-1):
    edge.append((d[i+1][2], d[i][2],d[i+1][1]-d[i][1]))
edge.sort(key=lambda x: x[2])
res=0
uf = UnionFind(n)
for e in edge:
    if uf.same(e[0], e[1]):
        continue
    uf.unite(e[0], e[1])
    res+=e[2]
print(res)

Solution (Python):

import sys

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())
    nodes = []
    for i in range(N):
        x, y = map(int, input().split())
        nodes.append((x, y, i))

    uf = UnionFind(N)
    nodes_sorted_by_x = sorted(nodes)
    nodes_sorted_by_y = sorted(nodes, key=lambda i: i[1])

    edges = []
    for i in range(N - 1):
        dx = abs(nodes_sorted_by_x[i][0] - nodes_sorted_by_x[i + 1][0])
        dy = abs(nodes_sorted_by_x[i][1] - nodes_sorted_by_x[i + 1][1])
        cost = min(dx, dy)
        edges.append((cost, nodes_sorted_by_x[i][2],  nodes_sorted_by_x[i + 1][2]))

    for i in range(N - 1):
        dx = abs(nodes_sorted_by_y[i][0] - nodes_sorted_by_y[i + 1][0])
        dy = abs(nodes_sorted_by_y[i][1] - nodes_sorted_by_y[i + 1][1])
        cost = min(dx, dy)
        edges.append((cost, nodes_sorted_by_y[i][2],  nodes_sorted_by_y[i + 1][2]))

    edges.sort()
        
    ans = 0
    for edge in edges:
        w, s, t = edge
        if not uf.same(s, t):
            ans += w
            uf.union(s, t)
    print(ans)

    
    
if __name__ == '__main__':
    main()

Solution (Python):








INF = float('inf')

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

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

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

        if x == y:
            return

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

def kruskal(n, edges):
    uf = UnionFind(n)
    ret = 0
    for w, u, v in edges:
        if not uf.same(u, v):
            ret += w
            uf.unite(u, v)
    return ret

def main():
    N = int(input())
    
    L = [None]*N
    for i in range(N):
        x, y = map(int,input().split())
        L[i]=(x, y, i)
    Edges = []
    for i in range(2):
        L.sort(key=lambda x:x[i])
        for j in range(N-1):
            Edges.append( (L[j+1][i]-L[j][i], L[j][2], L[j+1][2]) )
    Edges.sort()

    print(kruskal(N, Edges))

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
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 0
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        
N = int(input())
xseq = []
yseq = []
uf = UnionFind(N)
ans = 0

for i in range(N):
    x,y = (int(x) for x in input().split())
    xseq.append((x,i))
    yseq.append((y,i))
xseq.sort()
yseq.sort()
xdiff = [(xseq[i][0]-xseq[i-1][0],(xseq[i][1],xseq[i-1][1])) for i in range(1,N)]
ydiff = [(yseq[i][0]-yseq[i-1][0],(yseq[i][1],yseq[i-1][1])) for i in range(1,N)]
diff = xdiff + ydiff
diff.sort()
d = deque(diff)

for i in range(len(d)):
    temp = d.popleft()
    if uf.find(temp[1][0]) != uf.find(temp[1][1]):
        uf.union(temp[1][0],temp[1][1])
        ans += temp[0]
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

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


def main():
    N = int(input())
    coord = {}
    for i in range(N):
        x, y = map(int, input().split())
        coord[i] = (x, y)

    coord_x_sort = sorted(coord.items(), key=lambda x: x[1][0])
    coord_y_sort = sorted(coord.items(), key=lambda x: x[1][1])
    dist = []
    for i in range(N - 1):
        dx = abs(coord_x_sort[i][1][0] - coord_x_sort[i + 1][1][0])
        c1 = coord_x_sort[i][0]
        c2 = coord_x_sort[i + 1][0]
        dist.append((dx, c1, c2))

        dy = abs(coord_y_sort[i][1][1] - coord_y_sort[i + 1][1][1])
        c1 = coord_y_sort[i][0]
        c2 = coord_y_sort[i + 1][0]
        dist.append((dy, c1, c2))

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

    tree = UnionFind(N)

    ans = 0
    for d, i, j in dist:
        if not tree.check(i, j):
            ans += d
            tree.unite(i, j)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):


import heapq

def main():
    n = int(input())
    nodes = []
    for i in range(n):
        xi, yi = map(int, input().split())
        nodes.append((i, xi, yi))

    adj = [[] for i in range(n)]
    nodesx = sorted(nodes, key=(lambda x: x[1]))
    for j in range(n - 1):
        i1 = nodesx[j][0]
        i2 = nodesx[j + 1][0]
        adj[i1].append(i2)
        adj[i2].append(i1)
    nodesy = sorted(nodes, key=(lambda x: x[2]))
    for j in range(n - 1):
        i1 = nodesy[j][0]
        i2 = nodesy[j + 1][0]
        adj[i1].append(i2)
        adj[i2].append(i1)

    res = 0
    q = [(0, 0)]
    visited = [False for i in range(n)]
    while q:
        d, i = heapq.heappop(q)
        if visited[i]:
            continue
        visited[i] = True
        res += d
        for j in adj[i]:
            if visited[j]:
                continue
            heapq.heappush(q, (dist(i, j, nodes), j))
    print(res)

def dist(i, j, nodes):
    _, xi, yi = nodes[i]
    _, xj, yj = nodes[j]
    res = min(abs(xi - xj), abs(yi - yj))
    return res

if __name__ == "__main__":
    main()

Solution (Python):


import heapq

def main():
    n = int(input())
    nodes = []
    for i in range(n):
        xi, yi = map(int, input().split())
        nodes.append((i, xi, yi))

    adj = [[] for i in range(n)]
    nodes.sort(key=(lambda x: x[1]))
    for j in range(n):
        i = nodes[j][0]
        if j - 1 >= 0:
            i1 = nodes[j - 1][0]
            adj[i].append(i1)
        if j + 1 < n:
            i1 = nodes[j + 1][0]
            adj[i].append(i1)
    nodes.sort(key=(lambda x: x[2]))
    for j in range(n):
        i = nodes[j][0]
        if j - 1 >= 0:
            i1 = nodes[j - 1][0]
            adj[i].append(i1)
        if j + 1 < n:
            i1 = nodes[j + 1][0]
            adj[i].append(i1)
    nodes.sort(key=(lambda x: x[0]))

    res = 0
    q = [(0, 0)]
    visited = [False for i in range(n)]
    while q:
        d, i = heapq.heappop(q)
        if visited[i]:
            continue
        visited[i] = True
        res += d
        for j in adj[i]:
            if visited[j]:
                continue
            heapq.heappush(q, (dist(i, j, nodes), j))
    print(res)

def dist(i, j, nodes):
    _, xi, yi = nodes[i]
    _, xj, yj = nodes[j]
    res = min(abs(xi - xj), abs(yi - yj))
    return res

if __name__ == "__main__":
    main()

Solution (Python):


import heapq

def main():
    n = int(input())
    nodes = []
    for i in range(n):
        xi, yi = map(int, input().split())
        nodes.append((i, xi, yi))

    adj = [[] for i in range(n)]
    nodes.sort(key=(lambda x: x[1]))
    for j in range(n):
        i = nodes[j][0]
        if j - 1 >= 0:
            i1 = nodes[j - 1][0]
            adj[i].append(i1)
        if j + 1 < n:
            i1 = nodes[j + 1][0]
            adj[i].append(i1)
    nodes.sort(key=(lambda x: x[2]))
    for j in range(n):
        i = nodes[j][0]
        if j - 1 >= 0:
            i1 = nodes[j - 1][0]
            adj[i].append(i1)
        if j + 1 < n:
            i1 = nodes[j + 1][0]
            adj[i].append(i1)
    nodes.sort(key=(lambda x: x[0]))

    res = 0
    q = [(0, 0)]
    visited = [False for i in range(n)]
    while q:
        d, i = heapq.heappop(q)
        if visited[i]:
            continue
        visited[i] = True
        res += d
        for j in adj[i]:
            if visited[j]:
                continue
            heapq.heappush(q, (dist(i, j, nodes), j))
    print(res)

def dist(i, j, nodes):
    _, xi, yi = nodes[i]
    _, xj, yj = nodes[j]
    res = min(abs(xi - xj), abs(yi - yj))
    return res

if __name__ == "__main__":
    main()

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

class Unionfind:
    def __init__(self, n):
        self.par = [-1]*n
        self.rank = [1]*n
    
    def root(self, x):
        r = x
        
        while not self.par[r]<0:
            r = self.par[r]
        
        t = x
        
        while t!=r:
            tmp = t
            t = self.par[t]
            self.par[tmp] = r
        
        return r
    
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        
        if rx==ry:
            return
        
        if self.rank[rx]<=self.rank[ry]:
            self.par[ry] += self.par[rx]
            self.par[rx] = ry
            
            if self.rank[rx]==self.rank[ry]:
                self.rank[ry] += 1
        else:
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
    
    def is_same(self, x, y):
        return self.root(x)==self.root(y)
    
    def count(self, x):
        return -self.par[self.root(x)]

N = int(input())
xy = [(i,)+tuple(map(int, input().split())) for i in range(N)]
xy.sort(key=lambda t: t[1])
edges = []

for i in range(N-1):
    edges.append((xy[i][0], xy[i+1][0], xy[i+1][1]-xy[i][1]))

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

for i in range(N-1):
    edges.append((xy[i][0], xy[i+1][0], xy[i+1][2]-xy[i][2]))

edges.sort(key=lambda t: t[2])
uf = Unionfind(N)
ans = 0

for s, t, w in edges:
    if not uf.is_same(s, t):
        uf.unite(s, t)
        ans += w

print(ans)

Solution (Python):
from heapq import *

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

n=int(input())
X=[[0,0] for i in range(n)]
Y=[[0,0] for i in range(n)]
edge=[[0,0] for i in range(n)]
for i in range(n):
  x,y=map(int,input().split())
  X[i]=[x,i]
  Y[i]=[y,i]
  edge[i]=[x,y]
X.sort()
Y.sort()
hq=[]
heapify(hq)
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(hq,(x2-x1,j1,j2))
  heappush(hq,(y2-y1,k1,k2))
ans=0
uf=UnionFind(n)
while hq:
  w,s,t=heappop(hq)
  if uf.find(s)!=uf.find(t):
    uf.unite(s,t)
    ans+=w
print(ans)

Solution (Python):
class UnionFindNode:
    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1
        self.member_num_ = 1

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                n_root, child = root, unite_root
            else:
                n_root, child = unite_root, root
            child.parent_ = n_root
            n_root.rank_ = max(n_root.rank_, child.rank_ + 1)
            n_root.member_num_ = n_root.member_num_ + child.member_num_

N, = map(int, input().split())
X,Y = [],[]
for i in range(1, N+1):
    x, y = map(int, input().split())
    X.append((x,i))
    Y.append((y,i))
X = sorted(X, key=lambda x:x[0])
Y = sorted(Y, key=lambda x:x[0])
Es = set()
for i in range(N-1):
    Es.add((tuple(sorted([X[i][1], X[i+1][1]])), abs(X[i][0]-X[i+1][0])))
    Es.add((tuple(sorted([Y[i][1], Y[i+1][1]])), abs(Y[i][0]-Y[i+1][0])))
node_list = [UnionFindNode(i) for i in range(N+1)]
Es = sorted(Es, key=lambda x:x[1])
r = 0
for (x, y), c in Es:
    if node_list[x].find() == node_list[y].find():
        continue
    r += c
    node_list[x].unite(node_list[y])
print(r)