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



Sample input:
3
1 5
3 9
7 8


Sample output:
3

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    def find(self, x):
        stack = []
        parent = self.parent
        while parent[x] != x:
            stack.append(x)
            x = parent[x]
        for y in stack:
            parent[y] = x
        return x

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        
        if self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        elif self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif xr != yr:
            self.parent[yr] = xr
            self.rank[xr] += 1

from itertools import chain

N = int(input())
points = tuple(tuple(map(int,input().split())) for _ in range(N))
ds = DisjointSet(N)

x_i = sorted((x,i) for i,(x,y) in enumerate(points))
y_i = sorted((y,i) for i,(x,y) in enumerate(points))

xr = [x_i[0]]
yr = [y_i[0]]

for (x0,i0),(x1,i1) in zip(x_i,x_i[1:]):
    if x0 == x1:
        ds.union(i0,i1)
    else:
        xr.append((x1,i1))

for (y0,i0),(y1,i1) in zip(y_i,y_i[1:]):
    if y0 == y1:
        ds.union(i0,i1)
    else:
        yr.append((y1,i1))

deltas = sorted(
        chain(
            ((x1-x0,i0,i1) for (x0,i0), (x1,i1) in zip(xr,xr[1:])),
            ((y1-y0,i0,i1) for (y0,i0), (y1,i1) in zip(yr,yr[1:])),
        )
    )


def it():
    for d,i0,i1 in deltas:
        i0,i1 = ds.find(i0), ds.find(i1)
        if i0 != i1:
            ds.union(i0,i1)
            yield d
print(sum(it()))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
from operator import itemgetter
from copy import deepcopy
from collections import deque
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]

    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def same(x, y):
        return find(x) == find(y)
    def size(x):
        return -par[find(x)]
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]
    def roots():
        return [i for i, x in enumerate(par) if x < 0]

    # input
    n = int(input())
    m = map(int, read().split())
    # inputされたノード座標のリストをｘ座標とｙ座標それぞれでソート。
    mm = zip(m, m)
    cnt = 0
    nodes = []
    nodes_a = nodes.append
    for a, b in mm:
        # nodes_a(x座標、y座標、ノード名) ※ノード名は0origin。union-findを使うため。
        nodes_a((a, b, cnt))
        cnt += 1
    nodes.sort(key=itemgetter(0))
    nodes_y = deepcopy(nodes)
    nodes_y.sort(key=itemgetter(1))
    # ノード座標リストからｘ軸とｙ軸それぞれで「隣接するノードをむすぶ辺」のリストをedgesに格納。
    edges = []
    for i1 in range(n - 1):
        # 辺のコスト、端のノード２つ
        edges.append((nodes[i1+1][0] - nodes[i1][0], nodes[i1][2], nodes[i1+1][2]))
        edges.append((nodes_y[i1+1][1] - nodes_y[i1][1], nodes_y[i1][2], nodes_y[i1+1][2]))
    # 「コストが小さい順」でソート
    edges.sort(key=itemgetter(0))
    # union-findをつかってクラスカル法をする。
    par = [-1] * n  # union-find用のデータ初期化
    edges = deque(edges)  # edgesを左から１つずつpopするのでdequeに変換。
    r = 0  # rに「森に加えた辺のコスト」を加算していく
    while edges:
        e = edges.popleft()
        if not same(e[1], e[2]):
            r += e[0]
            unite(e[1], e[2])
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc065/tasks/arc076_b

import sys
input = sys.stdin.readline

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

    def find(self, x):                                          # 根を見つける関数を定義（同時にxを直接根にくっつける操作も行う）
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])        # 右辺で再帰的に根を探索。根に到達すると一つ目のif判定に引っかかるので、
                                                                # 最終的にself.parents[根]が返ってくる。
                                                                # これを左辺に代入することで、根が親になるように変更する。（根までの距離が長いとO(N)になってしまうので）
            return self.parents[x]

    def union(self, x, y):  # 二つの木をくっつける（子を多く持つ方を根とした親子関係）。これは破壊的操作を行う。
        x = self.find(x)  # xをxの根に置き換える
        y = self.find(y)  # yをyの根に置き換える

        if x == y:  # 根が同じなら置き換える必要なし
            return False

        if self.parents[x] > self.parents[y]:  # 子がたくさんある方を x とする
            x, y = y, x

        self.parents[x] += self.parents[y]  # xの子の数を更新
        self.parents[y] = x  # yの親を更新
        return True         # 同じ木にいるかの判定も同時に行うために、返り値を設定

#####( main )#########################################################################################################################

N = int(input())


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

datax = sorted(data, key=lambda x:x[1])
datay = sorted(data, key=lambda x:x[2])

cost = []
for i in range(N-1):
    p, q = datax[i:i+2]
    pi, px, py = p
    qi, qx, qy = q
    cost.append((pi, qi, min(abs(px-qx), abs(py-qy))))
    cost.append((qi, pi, min(abs(px-qx), abs(py-qy))))
    p, q = datay[i:i+2]
    pi, px, py = p
    qi, qx, qy = q
    cost.append((pi, qi, min(abs(px-qx), abs(py-qy))))
    cost.append((qi, pi, min(abs(px-qx), abs(py-qy))))

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

tree = UnionFind(N)
res = 0
for p, q, dist in cost:
    # p -= 1
    # q -= 1                                                        # デクリメントが必要ならば、コメントアウトを消す
    if tree.union(p, q):
        res += dist                                                 # 小さい順に足されていく（プリム法と異なる）

print(res)

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        
        if self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        elif self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif xr != yr:
            self.parent[yr] = xr
            self.rank[xr] += 1

from itertools import chain

N = int(input())
points = tuple(tuple(map(int,input().split())) for _ in range(N))
ds = DisjointSet(N)

x_i = sorted((x,i) for i,(x,y) in enumerate(points))
y_i = sorted((y,i) for i,(x,y) in enumerate(points))

xr = [x_i[0]]
yr = [y_i[0]]

for (x0,i0),(x1,i1) in zip(x_i,x_i[1:]):
    if x0 == x1:
        ds.union(i0,i1)
    else:
        xr.append((x1,i1))

for (y0,i0),(y1,i1) in zip(y_i,y_i[1:]):
    if y0 == y1:
        ds.union(i0,i1)
    else:
        yr.append((y1,i1))

deltas = sorted(
        chain(
            ((x1-x0,i0,i1) for (x0,i0), (x1,i1) in zip(xr,xr[1:])),
            ((y1-y0,i0,i1) for (y0,i0), (y1,i1) in zip(yr,yr[1:])),
        )
    )


def it():
    for d,i0,i1 in deltas:
        if ds.find(i0) != ds.find(i1):
            ds.union(i0,i1)
            yield d
print(sum(it()))

Submission status: Accepted

Solution code:
n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
x,y=zip(*xy)
x=list(zip(range(n),x))
y=list(zip(range(n),y))
x.sort(key=lambda a:a[1])
y.sort(key=lambda a:a[1])
d=[]
for i in range(n-1):
  d.append([x[i+1][1]-x[i][1],x[i+1][0],x[i][0]])
  d.append([y[i+1][1]-y[i][1],y[i+1][0],y[i][0]])
d.sort(key=lambda a:a[0],reverse=True)
# Union FInd
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())

ans=0
uf=UnionFind(n)
while d:
  dist,i,j=d.pop()
  if uf.same(i,j):
    continue
  uf.union(i,j)
  ans+=dist
print(ans)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix
from operator import itemgetter

n = int(input()) 
ixy = [[i] + [int(x) for x in input().split()] for i in range(n)]

edge = set()

for key in [itemgetter(1),itemgetter(2)]:
    ixy.sort(key = key)
    for i in range(n-1):
        i1, i2 = ixy[i][0], ixy[i+1][0]
        x1, x2 = ixy[i][1], ixy[i+1][1]
        y1, y2 = ixy[i][2], ixy[i+1][2]
        d = min(abs(x2-x1), abs(y2-y1))
        edge.add((i1,i2,d))
    
row,col,value = zip(*edge)
csr_ = csr_matrix((value, (row,col)), shape=(n, n))
mst = minimum_spanning_tree(csr_, overwrite=True).astype(int)
print(mst.sum())

Submission status: Accepted

Solution code:
from operator import itemgetter
from scipy.sparse import csr_matrix
import numpy as np

N = int(input())

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

edge = set()
for key in [itemgetter(1),itemgetter(2)]:
  XY.sort(key = key)
  for i in range(N-1):
    i1,x1,y1 = XY[i]
    i2,x2,y2 = XY[i+1]
    d = min(abs(x1-x2),abs(y1-y2))
    edge.add((i1,i2,d))
    
# csr形式に直す
row,col,value = zip(*edge)
value = np.array(value,dtype=int)
graph = csr_matrix((value,(row,col)),shape=(N,N))

# 最小全域木
from scipy.sparse.csgraph import minimum_spanning_tree
tree = minimum_spanning_tree(graph, overwrite = True).astype(int)
answer = tree.sum()
print(answer)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
n=int(input())
points=[list(map(int,input().split()))+[i] for i in range(n)]
points.sort(key = lambda x:x[1])
edge=[]
for i in range(n-1):
    edge.append((points[i][2],points[i+1][2],points[i+1][1]-points[i][1]))
points.sort()
for i in range(n-1):
    edge.append((points[i][2],points[i+1][2],points[i+1][0]-points[i][0]))
class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for i in range(N)]
    
    def merge(self, a, b):
        if self.issame(a,b):
            return
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
        self.size[pb] += self.size[pa]
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r
    
    def issame(self, x, y):
        return self.root(x) == self.root(y)
    
    def getsize(self, x):
        return self.size[self.root(x)]
edge.sort(key=lambda x:x[2])
uf=UnionFind(n)
ans=0
for ed in edge:
    if uf.issame(ed[0],ed[1]):continue
    ans+=ed[2]
    uf.merge(ed[0],ed[1])
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify

class Graph():  #non-directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.edge = edge
        self.indexed = indexed
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.graph[e[1] - indexed].append((e[0] - indexed, e[2]))

    def prim(self):
        used = [False for _ in range(self.n)]
        used[0] = True
        heap = [(cost, adj) for adj, cost in self.graph[0]]
        heapify(heap)
        res = 0
        while heap:
            cost, node = heappop(heap)
            if used[node]:
                continue
            used[node] = True
            res += cost
            for adj, adjcost in self.graph[node]:
                if used[adj]:
                    continue
                heappush(heap, (adjcost, adj))
        return res

import sys
input = sys.stdin.readline

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

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

sort_by_x = sorted(T, key=lambda x: x[0])
sort_by_y = sorted(T, key=lambda x: x[1])

E = []

for i in range(N - 1):
    x1, y1, id1 = sort_by_x[i]
    x2, y2 ,id2 = sort_by_x[i + 1]
    E.append((id1, id2, min(abs(x1 - x2), abs(y1 - y2))))
    x1, y1, id1 = sort_by_y[i]
    x2, y2 ,id2 = sort_by_y[i + 1]
    E.append((id1, id2, min(abs(x1 - x2), abs(y1 - y2))))

g = Graph(N, E, 0)

print(g.prim())

Submission status: Accepted

Solution code:
class Graph():  #non-directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.edge = edge
        self.indexed = indexed
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.graph[e[1] - indexed].append((e[0] - indexed, e[2]))

    def kruskal(self):  #UnionFind
        #edgemap = {self.edge[i]: i for i in range(len(self.edge))}
        sortedge = sorted(self.edge, key=lambda x: x[2])
        #sortedge = reversed(sortedge) コストの最大化
        uf = UnionFind(self.n)
        res = 0
        restored = []
        for e in sortedge:
            if uf.find(e[0] - self.indexed) != uf.find(e[1] - self.indexed):
                res += e[2]
                #restored.append(edgemap[e])
                uf.unite(e[0] - self.indexed, e[1] - self.indexed)
        return res#, restored

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

    def find(self, x):
        root = x
        while self.parents[root] != root:
            root = self.parents[root]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root

    def unite(self, x, y):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot: return
        xrank = self.rank[xroot]
        yrank = self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
            self.size[yroot] += self.size[xroot]
        elif xrank == yrank:
            self.parents[yroot] = xroot
            self.rank[yroot] += 1
            self.size[xroot] += self.size[yroot]
        else:
            self.parents[yroot] = xroot
            self.size[xroot] += self.size[yroot]

import sys
input = sys.stdin.readline

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

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

sort_by_x = sorted(T, key=lambda x: x[0])
sort_by_y = sorted(T, key=lambda x: x[1])

E = []

for i in range(N - 1):
    x1, y1, id1 = sort_by_x[i]
    x2, y2 ,id2 = sort_by_x[i + 1]
    E.append((id1, id2, min(abs(x1 - x2), abs(y1 - y2))))
    x1, y1, id1 = sort_by_y[i]
    x2, y2 ,id2 = sort_by_y[i + 1]
    E.append((id1, id2, min(abs(x1 - x2), abs(y1 - y2))))

g = Graph(N, E)

print(g.kruskal())

Submission status: Accepted

Solution code:
class Graph():  #non-directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.edge = edge
        self.indexed = indexed
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.graph[e[1] - indexed].append((e[0] - indexed, e[2]))

    def kruskal(self):  #UnionFind
        edgemap = {self.edge[i]: i for i in range(len(self.edge))}
        sortedge = sorted(self.edge, key=lambda x: x[2])
        #sortedge = reversed(sortedge) コストの最大化
        uf = UnionFind(self.n)
        res = 0
        restored = []
        for e in sortedge:
            if uf.find(e[0] - self.indexed) != uf.find(e[1] - self.indexed):
                res += e[2]
                restored.append(edgemap[e])
                uf.unite(e[0] - self.indexed, e[1] - self.indexed)
        return res, restored

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

    def find(self, x):
        root = x
        while self.parents[root] != root:
            root = self.parents[root]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root

    def unite(self, x, y):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot: return
        xrank = self.rank[xroot]
        yrank = self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
            self.size[yroot] += self.size[xroot]
        elif xrank == yrank:
            self.parents[yroot] = xroot
            self.rank[yroot] += 1
            self.size[xroot] += self.size[yroot]
        else:
            self.parents[yroot] = xroot
            self.size[xroot] += self.size[yroot]

import sys
input = sys.stdin.readline

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

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

sort_by_x = sorted(T, key=lambda x: x[0])
sort_by_y = sorted(T, key=lambda x: x[1])

E = []

for i in range(N - 1):
    x1, y1, id1 = sort_by_x[i]
    x2, y2 ,id2 = sort_by_x[i + 1]
    E.append((id1, id2, min(abs(x1 - x2), abs(y1 - y2))))
    x1, y1, id1 = sort_by_y[i]
    x2, y2 ,id2 = sort_by_y[i + 1]
    E.append((id1, id2, min(abs(x1 - x2), abs(y1 - y2))))

g = Graph(N, E)

print(g.kruskal()[0])

Submission status: Accepted

Solution code:
import sys
import collections
sys.setrecursionlimit(10 ** 8)

def input(): return sys.stdin.readline().strip()
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

class UnionFind:
    def __init__(self, size):
        self.par = [i for i in range(size)]
        self.rank = [0] * size

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

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

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

def main():
    N = Z()
    Cs = [ZZ()+[i] for i in range(N)]
    X = sorted(Cs)
    Y = sorted(Cs, key=lambda x:x[1])
    es = []
    for i in range(N-1):
        c = X[i+1][0] - X[i][0]
        u, v = X[i][2], X[i+1][2]
        es.append([c, u, v])
    for i in range(N-1):
        c = Y[i+1][1] - Y[i][1]
        u, v = Y[i][2], Y[i+1][2]
        es.append([c, u, v])
    es.sort()
    uf = UnionFind(N)
    output = 0
    for i in range(len(es)):
        c, u, v = es[i]
        if not uf.same(u, v):
            uf.unite(u, v)
            output += c
    print(output)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


class UnionFind:
    # Reference: https://note.nkmk.me/python-union-find/
    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 main():
    N, *XY = map(int, read().split())
    X = list(zip(XY[::2], range(N)))
    Y = list(zip(XY[1::2], range(N)))

    X.sort()
    Y.sort()

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

    edge.sort()

    uf = UnionFind(N)
    ans = 0
    for d, s, t in edge:
        if not uf.same(s, t):
            uf.union(s, t)
            ans += d

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq


class UnionFind:
    from collections import deque

    def __init__(self, v):
        self.v = v
        self._tree = list(range(v + 1))

    def _root(self, a):
        queue = self.deque()
        while self._tree[a] != a:
            queue.append(a)
            a = self._tree[a]
        while queue:
            index = queue.popleft()
            self._tree[index] = a
        return a

    def union(self, a, b):
        root_a = self._root(a)
        root_b = self._root(b)
        self._tree[root_b] = root_a

    def find(self, a, b):
        return self._root(a) == self._root(b)


N = int(input())
V = []
for i in range(N):
    s, t = map(int, input().split(' '))
    V.append((i, s, t))

E = []
vx = sorted(V, key=lambda v: v[1])
for v1, v2 in zip(vx, vx[1:]):
    i, x1, y1 = v1
    j, x2, y2 = v2
    heapq.heappush(E, (abs(x1 - x2), i, j))

vy = sorted(V, key=lambda v: v[2])
for v1, v2 in zip(vy, vy[1:]):
    i, x1, y1 = v1
    j, x2, y2 = v2
    heapq.heappush(E, (abs(y1 - y2), i, j))

uf = UnionFind(N)
cost = 0
while E:
    c, i, j = heapq.heappop(E)
    if not uf.find(i, j):
        uf.union(i, j)
        cost += c

print(cost)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        self.v=[-1]*n
    
    def find(self,x):
        if self.v[x]<0:
            return x
        else:
            self.v[x]=self.find(self.v[x])
            return self.v[x]
    
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)

        if x==y:
            return False
        else:
            if self.v[x]>self.v[y]:
                x,y=y,x
            self.v[x]+=self.v[y]
            self.v[y]=x
            return True
    
    def same(self,x,y):
        return self.find(x)==self.find(y)
    
    def size(self,x):
        return -self.v[self.find(x)]

import sys

N=int(sys.stdin.readline())
ps=[]
xs=set()
ys=set()
for i in range(N):
    x,y=map(int,input().split())
    ps.append((x,y))
    xs.add(x)
    ys.add(y)

xs=tuple(sorted(xs))
ys=tuple(sorted(ys))

dx={e:i for i,e in enumerate(xs)}
dy={e:i for i,e in enumerate(ys)}
uf=(UnionFind(N*2))
for x,y in ps:
    uf.unite(dx[x],dy[y]+N)

def make_edges(xs,start):
    xes=[]
    for i, (x0,x1) in enumerate(zip(xs,xs[1:]),start=start):
        xes.append((abs(x1-x0), i, i+1))
    return xes

xes=make_edges(xs,start=0)
yes=make_edges(ys,start=N)

ret=0
for cost,a,b in sorted(xes+yes,key=lambda x:x[0]):
    if uf.same(a,b):
        continue
    uf.unite(a,b)
    ret+=cost
print(ret)

Submission status: Accepted

Solution code:
import heapq
def prim_heap():
    used = [True] * n #True:不使用
    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

#########################
n = int(input())
zahyo = []
for i in range(n):
    x,y = map(int,input().split())
    zahyo.append((x,y,i))
xza = sorted(zahyo)
yza = sorted(zahyo,key=lambda x: x[1])
edge = [[] for i in range(n)]
#隣接リスト edge[i]:[コスト,行先]
for i in range(n-1):
    c = abs(xza[i][0]-xza[i+1][0])
    edge[xza[i][2]].append((c,xza[i+1][2]))
    edge[xza[i+1][2]].append((c,xza[i][2]))
for i in range(n-1):
    c = abs(yza[i][1]-yza[i+1][1])
    edge[yza[i][2]].append((c,yza[i+1][2]))
    edge[yza[i+1][2]].append((c,yza[i][2]))
print(prim_heap())

Submission status: Accepted

Solution code:
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())
xy = []
uf = UnionFind(N)
d = {}
j = 0
for i in range(N):
    x, y = map(int, input().split())
    if not (x,y) in d:
        d[(x,y)] = j
        xy.append((x,y))
        j += 1
N = len(xy)

xy = sorted(xy, key = lambda x:x[0])

root = []
for i in range(N-1):
    before_x, before_y = xy[i]
    x, y = xy[i+1]
    root.append((d[xy[i]],d[xy[i+1]],x - before_x))

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

for i in range(N-1):
    before_x, before_y = xy[i]
    x, y = xy[i+1]
    root.append((d[xy[i]],d[xy[i+1]],y - before_y))

root = sorted(root, key = lambda x:x[2])

ans = 0
for s,g,c in root:
    if uf.same(s,g):
        continue
    else:
        uf.union(s,g)
        ans += c

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
path = []

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n
    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)

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

x_li = sorted(path)
y_li = sorted(path,key=lambda x:(x[1]))

edge = []

for i in range(1,n):
    edge.append((x_li[i][2],x_li[i-1][2],x_li[i][0]-x_li[i-1][0]))
    edge.append((y_li[i][2],y_li[i-1][2],y_li[i][1]-y_li[i-1][1]))

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

uf = UnionFind(n)
cost = 0

for i,j,k in edge:
    if not uf.same(i,j):
        uf.union(i,j)
        cost += k

print(cost)

Submission status: Accepted

Solution code:
# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]
n = int(input())
#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

p = [] #点p
edge = []
for i in range(n):
    x,y = map(int,input().split())
    p.append([x,y,i])
p.sort(key=lambda x:x[0])
for i in range(n-1):
    x_0,_,j=p[i]
    x_1,_,k=p[i+1]
    edge.append([x_1-x_0,j,k]) # 重みx_1 - x_0の点jと点kを繋ぐ辺
p.sort(key=lambda x:x[1])
for i in range(n-1):
    _,y_0,j=p[i]
    _,y_1,k=p[i+1]
    edge.append([y_1-y_0,j,k])

edge.sort() #クラスカル法を使うので重みでソート
ans = 0
for i in range(len(edge)):
    cost,u,v = edge[i]
    if not same(u,v):
        unite(u,v)
        ans+=cost
print(ans)