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.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
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

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


Xyi = sorted(xyi)
xYi = sorted(xyi, key=lambda x: x[1])

from heapq import *

a = []

for j in range(n-1):
    x,y,i = Xyi[j]
    xx,yy,ii = Xyi[j+1]
    heappush(a,(xx-x,ii,i))
    x,y,i = xYi[j]
    xx,yy,ii = xYi[j+1]
    heappush(a,(yy-y,ii,i))



uf = UnionFind(n)
c = 1
ans = 0
while c < n:
    d,ii,i = heappop(a)

    if uf.merge(ii,i):
        c += 1
        ans += d


print(ans)

Solution (Python):
def solve(query):
    q_x = sorted(query, key=lambda x: x[1])
    q_y = sorted(query, key=lambda x: x[2])

    g = set()

    for a, b in zip(q_x, q_x[1:]):
        s = a[0]
        t = b[0]
        w = min(abs(b[1]-a[1]), abs(b[2] - a[2]))
        g.add((w, s, t))

    for a, b in zip(q_y, q_y[1:]):
        s = a[0]
        t = b[0]
        w = min(abs(b[1]-a[1]), abs(b[2] - a[2]))
        g.add((w, s, t))

    _g = sorted(list(g))

    ans = 0
    for w, a, b in _g:
        if unite(a, b):
            ans += w
    return ans


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


def unite(x, y):
    rt_x = root(x)
    rt_y = root(y)
    if rt_x == rt_y:
        return False
    if rt_x < rt_y:
        par[rt_y] = rt_x
    else:
        par[rt_x] = rt_y

    return True


if __name__ == '__main__':
    n = int(input())
    query = []
    par = [i for i in range(n+1)]
    for i in range(n):
        a, b = map(int, input().split())
        query.append((i, a, b))

    print(solve(query))

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)

Solution (Python):
from collections import defaultdict

import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline

parent_node = []

def get_parent(ind):
    global parent_node
    if ind != parent_node[ind]:
        parent_node[ind] = get_parent(parent_node[ind])
    return parent_node[ind]



def main():
    num = int(input())

    data = defaultdict(tuple)

    for i in range(num):
        x, y = map(int, input().split())
        data[i] = (x, y)

    data_sort = sorted(data.items(), key=lambda x: x[1][0])
    data_x = [ele for ele, ele2 in data_sort]
    data_sort = sorted(data.items(), key=lambda x: x[1][1])
    data_y = [ele for ele, ele2 in data_sort]

    cost_data = [0 for i in range((num - 1) * 2)]
    for i in range(len(data_x) - 1):
        a, b = data_x[i], data_x[i + 1]
        cost = abs(data[a][0] - data[b][0])
        cost_data[i] = a, b, cost
    for i in range(len(data_y) - 1):
        a, b = data_y[i], data_y[i + 1]
        cost = abs(data[a][1] - data[b][1])
        cost_data[i + len(data_x) - 1] = a, b, cost

    cost_data.sort(key=lambda x: x[2])
    global parent_node
    parent_node = [i for i in range(num)]

    ans = 0
    for i in range(len(cost_data)):
        a, b, cost = cost_data[i]
        a_parent = get_parent(a)
        b_parent = get_parent(b)
        if a_parent != b_parent:
            ans += cost
            parent_node[min(a_parent, b_parent)] = max(a_parent, b_parent)

    print(ans)





if __name__ == '__main__':
    main()

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

class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

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

    def find(self,x):
        if(self.parent[x]<0):
            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(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

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

def main():
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app((xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app((yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))


    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(N)
    weight = 0

    for edge in edges:
        if not uf.same(edge[0], edge[1]):
            uf.unite(edge[0], edge[1])
            weight+=edge[2]
    print(weight)

if __name__ == '__main__':
    main()

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

class UnionFind:
    def __init__(self, n):
        self.par = list(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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        elif self.rank[x] < self.rank[y]:
            x, y = y, x
        
        self.par[y] = x
                
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

def kruskal():
    edges.sort(key=lambda x: x[2])
    t = UnionFind(N)
    ret = 0
    
    for u, v, c in edges:
        if not t.is_same(u, v):
            t.unite(u, v)
            ret += c
            
    return ret

edges = []

for k in range(1, 3):
    X.sort(key=lambda x: x[k])
    for i in range(N - 1):
        edges.append((X[i][0], X[i + 1][0], abs(X[i][k] - X[i + 1][k])))

print(kruskal())

Solution (Python):
import heapq

def prim(cost):
    V = len(cost)
    res = 0
    mincost = [float('inf')]*V
    used = [False]*V
    hq = []
    mincost[0] = 0
    heapq.heappush(hq,(0,0))
    while hq:
        weight,u = heapq.heappop(hq)
        if used[u]:
            continue
        used[u] = True
        res += weight
        mincost[u] = weight
        for v, v_cost in cost[u]:
            if not used[v]:
                heapq.heappush(hq,(v_cost,v))
    return res

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

xyi.sort()
cost = [[] for _ in range(N)]
for i in range(N-1):
    xj = xyi[i][0]
    j = xyi[i][2]
    xk = xyi[i+1][0]
    k = xyi[i+1][2]
    cost[j].append((k,xk-xj))
    cost[k].append((j,xk-xj))
xyi.sort(key=lambda x:x[1])
for i in range(N-1):
    yj = xyi[i][1]
    j = xyi[i][2]
    yk = xyi[i+1][1]
    k = xyi[i+1][2]
    cost[j].append((k,yk-yj))
    cost[k].append((j,yk-yj))

print(prim(cost))

Solution (Python):
import sys
input=sys.stdin.readline
class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.size_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.size_)

    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):
        parent = self.root()
        return parent.group_id_

    def size(self):
        parent = self.root()
        return parent.size_

    def unite(self, unite_node):
        parent = self.root()
        unite_parent = unite_node.root()

        if parent.group_id_ != unite_parent.group_id_:
            if parent.size() > unite_parent.size():
                unite_parent.parent_ = parent
                parent.size_ = parent.size_ + unite_parent.size_
            else:
                parent.parent_ = unite_parent
                unite_parent.size_ = parent.size_ + unite_parent.size_
    def is_group(self,other):
        return self.root()==other.root()

N=int(input())
X=[]
Y=[]
for i in range(N):
  x,y=map(int,input().split())
  X.append([x,i])
  Y.append([y,i])
X.sort()
Y.sort()
G=[]
for i in range(N-1):
  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][1],Y[i+1][1]])
G.sort()
U=[UnionFindNode(i) for i in range(N)]
ans=0
for i in range(len(G)):
    c,a,b=G[i]
    if U[a].is_group(U[b]):
        continue
    U[a].unite(U[b])
    ans+=c
    if U[0].size()==N:
        print(ans)
        quit()

Solution (Python):

import sys
sys.setrecursionlimit(300000)


def solve(N: int, x: "List[int]", y: "List[int]"):
    tmp = []
    for i in range(N):
        tmp.append([i, x[i], y[i]])
    tmp.sort(key=lambda x: x[1])
    dis = []
    for i in range(N - 1):
        dis.append([abs(tmp[i + 1][1] - tmp[i][1]), tmp[i][0], tmp[i + 1][0]])

    tmp.sort(key=lambda x: x[2])
    for i in range(N - 1):
        dis.append([abs(tmp[i + 1][2] - tmp[i][2]), tmp[i][0], tmp[i + 1][0]])

    par = list(range(N))
    def find_root(x):
        if par[x] != x:
            par[x] = find_root(par[x])
        return par[x]
    def union(a, b):
        a_root = find_root(a)
        b_root = find_root(b)
        par[a_root] = b_root
        return

    dis.sort(key=lambda x: x[0])
    ret = 0
    for d in dis:
        a = d[1]
        b = d[2]
        if find_root(a) != find_root(b):
            ret += d[0]
            union(a, b)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    x = [int()] * (N)  
    y = [int()] * (N)  
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()

Solution (Python):
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)]
        
n=int(input())
xlist=[]
ylist=[]
rlist=[]
for i in range(n):
  x,y=map(int,input().split())
  xlist.append([x,i])
  ylist.append([y,i])
xlist=sorted(xlist,key=lambda x:x[0])
ylist=sorted(ylist,key=lambda x:x[0])
for i in range(1,n):
  cost=xlist[i][0]-xlist[i-1][0]
  rlist.append([cost,xlist[i][1],xlist[i-1][1]])
  cost=ylist[i][0]-ylist[i-1][0]
  rlist.append([cost,ylist[i][1],ylist[i-1][1]])
rlist=sorted(rlist,key=lambda x:x[0])
cost=0
t=UnionFind(n)
for c,p1,p2 in rlist:
  if t.isSameGroup(p1,p2):
    continue
  else:
    cost+=c
    t.Unite(p1,p2)
print(cost)

Solution (Python):
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)]
        
n=int(input())
xlist=[]
ylist=[]
rlist=[]
checked=[-1]*n
for i in range(n):
  x,y=map(int,input().split())
  xlist.append([x,i])
  ylist.append([y,i])
xlist=sorted(xlist,key=lambda x:x[0])
ylist=sorted(ylist,key=lambda x:x[0])
for i in range(1,n):
  cost=xlist[i][0]-xlist[i-1][0]
  rlist.append([cost,xlist[i][1],xlist[i-1][1]])
  cost=ylist[i][0]-ylist[i-1][0]
  rlist.append([cost,ylist[i][1],ylist[i-1][1]])
rlist=sorted(rlist,key=lambda x:x[0])
cnt=0
cost=0
groupn=0
groupc=0
t=UnionFind(n)
for c,p1,p2 in rlist:
  if cnt==n and groupn-groupc==1:
    break
  if checked[p1]==-1 and checked[p2]==-1:
    checked[p1]=groupn
    checked[p2]=groupn
    cost+=c
    cnt+=2
    groupn+=1
    t.Unite(p1,p2)
  elif checked[p1]==-1:
    checked[p1]=checked[p2]
    cost+=c
    cnt+=1
    t.Unite(p1,p2)
  elif checked[p2]==-1:
    checked[p2]=checked[p1]
    cost+=c
    cnt+=1
    t.Unite(p1,p2)
  elif checked[p1]==checked[p2]:
    continue
  else:
    if t.isSameGroup(p1,p2):
      continue
    else:
      cost+=c
      groupc+=1
      t.Unite(p1,p2)
print(cost)

Solution (Python):
def main():
    import sys 
    input = sys.stdin.readline
    from heapq import heappop,heappush
    from operator import itemgetter
    
    def prim():
        used = [True]*n
        edgelist = []
        for e in edge[0]:
            heappush(edgelist,e)
        used[0] = False
        res = 0
        while len(edgelist) != 0:
            short_edge = heappop(edgelist)
            if not used[short_edge[1]]:
                continue
            v = short_edge[1]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heappush(edgelist,e)
            res += short_edge[0]
        return res

    n = int(input())
    A = [list(map(int,input().split()))+[i] for i in range(n)]
    A.append([-10**12,-10**12,-1])
    A.append([10**12,10**12,-1])
    X = sorted(A)
    Y = sorted(A,key = itemgetter(1))
    edge = [[] for i in range(n)]
    for i in range(1,n+1):
        sx = X[i-1][0]
        sy = Y[i-1][1]
        mx = X[i][0]
        my = Y[i][1]
        lx = X[i+1][0]
        ly = Y[i+1][1]
        nsx = X[i-1][2]
        nsy = Y[i-1][2]
        nmx = X[i][2]
        nmy = Y[i][2]
        nlx = X[i+1][2]
        nly = Y[i+1][2]
        edge[nsx].append((mx-sx,nmx))
        edge[nmx].append((mx-sx,nsx))
        edge[nlx].append((lx-mx,nmx))
        edge[nmx].append((lx-mx,nlx))
        edge[nsy].append((my-sy,nmy))
        edge[nmy].append((my-sy,nsy))
        edge[nly].append((ly-my,nmy))
        edge[nmy].append((ly-my,nly))

    print(prim()) 

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

def solve(n, x, y):
    def dist(i, j):
        return min(abs(x[i]-x[j]), abs(y[i]-y[j]))
    que = []
    for p in map(np.argsort, [x, y]):
        for i in range(n-1):
            u, v = p[i], p[i+1]
            que.append((u, v, dist(u, v)))
    parent = [i for i in range(n)]
    def find(i):
        if parent[i] == i:
            return i
        else:
            j = find(parent[i])
            parent[i] = j
            return j
    ans = 0
    for u, v, d in sorted(que, key=lambda _: _[2]):
        u = find(u)
        v = find(v)
        if u != v:
            ans += d
            if u > v:
                u, v = v, u
            parent[v] = u
    return ans

n = int(input())
x = np.zeros(n, dtype=int)
y = np.zeros(n, dtype=int)
for i in range(n):
    x[i], y[i] = map(int, input().split())
print(solve(n, x, y))

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

from operator import itemgetter
margin = []
XY.sort(key = itemgetter(1))

for j in range(n-1):
    margin.append([XY[j][0],XY[j+1][0],XY[j+1][1]-XY[j][1]])

XY.sort(key = itemgetter(2))
for j in range(n-1):
    margin.append([XY[j][0],XY[j+1][0],XY[j+1][2]-XY[j][2]])

margin.sort(key = itemgetter(2))
def search(UF,loc):
    if UF[loc] == loc:
        return UF[loc]
    else:
        UF[loc] = search(UF,UF[loc])
        return UF[loc]
UF = [k for k in range(n+1)]
count = 1
ans = 0
for p,q,m in margin:
        if count == n:
            break
        UF[p] = search(UF,p)
        UF[q] = search(UF,q)
        if UF[p] != UF[q]:
            ans += m
            UF[max(UF[p],UF[q])] = min(UF[p],UF[q])
            count += 1
print(ans)

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

def MST(n, E):
    def par(m):
        if UF[m] == m:
            return m
        ret = par(UF[m])
        UF[m] = ret
        return ret
    
    UF = [i for i in range(n)]
    E = sorted(E, key=lambda x: x[2])
    ans = 0
    for i, j, d in E:
        if par(i) != par(j):
            ans += d
            UF[par(i)] = par(j)
    return ans

N = int(input())

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

F = []
Y = sorted(X, key = lambda x: x[1])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][1]-Y[i][1])))

Y = sorted(X, key = lambda x: x[2])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][2]-Y[i][2])))

print(MST(N, F))

Solution (Python):
import sys
input = sys.stdin.readline
n=int(input())
Edge=[[] for i in range(n)]
XY=[]
append=XY.append
for i in range(n):
  x,y=map(int,input().split())
  append([i,x,y])
XY.sort(key=lambda x:x[1])
for i in range(1,n):
  n1,x1,y1=XY[i-1][0],XY[i-1][1],XY[i-1][2]
  n2,x2,y2=XY[i][0],XY[i][1],XY[i][2]
  Edge[n1].append([min(abs(x2-x1),abs(y2-y1)),n2])
  Edge[n2].append([min(abs(x2-x1),abs(y2-y1)),n1])
XY.sort(key=lambda x:x[2])
for i in range(1,n):
  n1,x1,y1=XY[i-1][0],XY[i-1][1],XY[i-1][2]
  n2,x2,y2=XY[i][0],XY[i][1],XY[i][2]
  Edge[n1].append([min(abs(x2-x1),abs(y2-y1)),n2])
  Edge[n2].append([min(abs(x2-x1),abs(y2-y1)),n1])
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
print(prim_heap())

Solution (Python):
import sys
import heapq
input = sys.stdin.readline
N = int(input())
XYI = sorted([[int(_) for _ in input().split()] + [_] for _ in range(N)])
visited = [False] * N
H = []
for j in range(N - 1):
    heapq.heappush(H, (XYI[j + 1][0] - XYI[j][0], XYI[j][2], XYI[j + 1][2]))
XYI.sort(key=lambda xs: xs[1])
for j in range(N - 1):
    heapq.heappush(H, (XYI[j + 1][1] - XYI[j][1], XYI[j + 1][2], XYI[j][2]))
ans = 0

UF = list(range(N + 1))
SIZE = [0] + [1] * N  


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    if not is_same(x, y):
        X, Y = find(x), find(y)
        SX, SY = SIZE[X], SIZE[Y]
        if SX > SY:
            m = UF[X] = Y
        else:
            m = UF[Y] = X
        SIZE[m] = SX + SY
        SIZE[X + Y - m] = 0


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


def scan_uf():
    for i in range(len(UF)):
        find(i)


while H:
    d, i1, i2 = heapq.heappop(H)
    if not is_same(i1, i2):
        unite(i1, i2)
        ans += d
print(ans)

Solution (Python):
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

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

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

X = np.array(X)
Y = np.array(Y)
Xargs = X.argsort()
Yargs = Y.argsort()


graph = [[] for _ in range(N)]
for v, u in zip(Xargs[:-1], Xargs[1:]):
    graph[v].append((abs(X[v] - X[u]), u))
    graph[u].append((abs(X[v] - X[u]), v))
for v, u in zip(Yargs[:-1], Yargs[1:]):
    graph[v].append((abs(Y[v] - Y[u]), u))
    graph[u].append((abs(Y[v] - Y[u]), v))

heap = graph[0]
heapq.heapify(heap)
fixed = np.zeros(N, dtype=bool)
fixed[0] = True

cnt = 1
ans = 0
while cnt < N:
    dist, v = heapq.heappop(heap)
    if fixed[v]:
        continue
    fixed[v] = True
    cnt += 1
    ans += dist
    for d, u in graph[v]:
        if fixed[u]:
            continue
        heapq.heappush(heap, (d, u))

print(ans)

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

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

for i in range(N-1):
    G.add(x[i][0],x[i+1][0],abs(x[i+1][1] - x[i][1]))
    G.add(y[i][0],y[i+1][0],abs(y[i+1][1] - y[i][1]))

print(G.Kruskal())

Solution (Python):




from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul,itemgetter
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)


class UNION_FIND(object):
    def __init__(self,n):
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])
            return self.parent[x]
 
    def size(self,x):
        return -self.parent[self.root(x)]
    def union(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]
        self.parent[y]=x
        return True

def KRUSKAL(n, edges, TF_of_maximize):
    edges.sort(key=lambda x: x[2],reverse=TF_of_maximize)
    uf = UNION_FIND(n)
    cost = []
    for (a,b,c) in edges:
        if uf.root(a)!= uf.root(b):
            uf.union(a,b)
            cost.append(c)
    return cost


def main():
    n=int(input())
    inp=[[i]+list(map(int,input().split()))for i in range(n)]
    inpX=sorted(inp,key=lambda x:x[1])
    inpY=sorted(inp,key=lambda x:x[2])
    edges=[]
    for i in range(1,n):
        a,b,c=inpX[i]
        d,e,f=inpX[i-1]
        edges.append((a,d,min(abs(b-e),abs(c-f))))
        a,b,c=inpY[i]
        d,e,f=inpY[i-1]
        edges.append((a,d,min(abs(b-e),abs(c-f))))
    
    print(sum(KRUSKAL(n, edges, 0))) 
    

if __name__ == '__main__':
    main()

Solution (Python):
















import sys

input=sys.stdin.readline  

class UNION_FIND(object):
    def __init__(self,n):
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])
            return self.parent[x]
 
    def size(self,x):
        return -self.parent[self.root(x)]
    def union(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]
        self.parent[y]=x
        return True

def compute_mst_kruskal(max_v, edges, flip):
    edges.sort(key=lambda x: x[2],reverse=flip)
    uf = UNION_FIND(max_v)
    mst = []
    for (a,b,c) in edges:
        if uf.root(a)!= uf.root(b):
            uf.union(a,b)
            mst.append(c)
    return mst


def main():
    n=int(input())
    inp=[[i]+list(map(int,input().split()))for i in range(n)]
    inpX=sorted(inp,key=lambda x:x[1])
    inpY=sorted(inp,key=lambda x:x[2])
    edges=[]
    for i in range(1,n):
        a,b,c=inpX[i]
        d,e,f=inpX[i-1]
        edges.append((a,d,min(abs(b-e),abs(c-f))))
        a,b,c=inpY[i]
        d,e,f=inpY[i-1]
        edges.append((a,d,min(abs(b-e),abs(c-f))))
    
    print(sum(compute_mst_kruskal(n, edges, 0)))
        
    
if __name__ == '__main__':
    main()

Solution (Python):







from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul,itemgetter
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)


class UNION_FIND(object):
    def __init__(self,n):
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])
            return self.parent[x]
 
    def size(self,x):
        return -self.parent[self.root(x)]
    def union(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]
        self.parent[y]=x
        return True

def compute_mst_kruskal(max_v, edges, flip):
    edges.sort(key=lambda x: x[2],reverse=flip)
    uf = UNION_FIND(max_v)
    mst = []
    for (a,b,c) in edges:
        if uf.root(a)!= uf.root(b):
            uf.union(a,b)
            mst.append(c)
    return mst


def main():
    n=int(input())
    inp=[[i]+list(map(int,input().split()))for i in range(n)]
    inpX=sorted(inp,key=lambda x:x[1])
    inpY=sorted(inp,key=lambda x:x[2])
    edges=[]
    for i in range(1,n):
        a,b,c=inpX[i]
        d,e,f=inpX[i-1]
        edges.append((a,d,min(abs(b-e),abs(c-f))))
        a,b,c=inpY[i]
        d,e,f=inpY[i-1]
        edges.append((a,d,min(abs(b-e),abs(c-f))))
    
    print(sum(compute_mst_kruskal(n, edges, 0)))
        
    
if __name__ == '__main__':
    main()