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:
# -*- coding: utf-8 -*-


class UnionFind(object):
    '''Represents a data structure that tracks a set of elements partitioned
       into a number of disjoint (non-overlapping) subsets.
    Landau notation: O(α(n)), where α(n) is the inverse Ackermann function.
    See:
    https://www.youtube.com/watch?v=zV3Ul2pA2Fw
    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
    https://atcoder.jp/contests/abc120/submissions/4444942
    '''

    def __init__(self, number_count: int):
        '''
        Args:
            number_count: The size of elements (greater than 2).
        '''
        self.parent_numbers = [-1 for _ in range(number_count)]

    def find_root(self, number: int) -> int:
        '''Follows the chain of parent pointers from number up the tree until
           it reaches a root element, whose parent is itself.
        Args:
            number: The trees id (0-index).
        Returns:
            The index of a root element.
        '''
        if self.parent_numbers[number] < 0:
            return number

        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])
        return self.parent_numbers[number]

    def get_group_size(self, number: int) -> int:
        '''
        Args:
            number: The trees id (0-index).
        Returns:
            The size of group.
        '''
        return -self.parent_numbers[self.find_root(number)]

    def is_same_group(self, number_x: int, number_y: int) -> bool:
        '''Represents the roots of tree number_x and number_y are in the same
           group.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        return self.find_root(number_x) == self.find_root(number_y)

    def merge_if_needs(self, number_x: int, number_y: int) -> bool:
        '''Uses find_root to determine the roots of the tree number_x and
           number_y belong to. If the roots are distinct, the trees are combined
           by attaching the roots of one to the root of the other.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        x = self.find_root(number_x)
        y = self.find_root(number_y)

        if x == y:
            return False

        if self.get_group_size(x) >= self.get_group_size(y):
            self.parent_numbers[x] += self.parent_numbers[y]
            self.parent_numbers[y] = x
        else:
            self.parent_numbers[y] += self.parent_numbers[x]
            self.parent_numbers[x] = y
        return True


def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    x = [None for _ in range(n)]
    y = [None for _ in range(n)]

    for i in range(n):
        xi, yi = map(int, input().split())
        xi -= 1
        yi -= 1

        x[i] = (xi, i)
        y[i] = (yi, i)

    # 最小全域木: 無向グラフで、任意の頂点のペアが行き来できる&そのときのコストを最小にしたい
    # x, y座標を別々に考える
    new_x = sorted(x)
    new_y = sorted(y)
    road = list()

    # x, y座標ともに最も近い点のペアを選択する(それ以外の点のペアを選んでもコストは増えるだけ)
    # 計算量がO(N^2)からO(N)に落とせる
    for _from, _to in zip(new_x, new_x[1:]):
        cost = abs(_from[0] - _to[0])
        road.append((_from[1], _to[1], cost))

    for _from, _to in zip(new_y, new_y[1:]):
        cost = abs(_from[0] - _to[0])
        road.append((_from[1], _to[1], cost))

    # コストが最小のものから選ぶ
    new_road = sorted(road, key=lambda x: x[2])
    uf = UnionFind(n)
    ans = 0

    # 同じグループに存在するかをチェックして、コストを加算
    for nr in new_road:
        if uf.merge_if_needs(nr[0], nr[1]):
            ans += nr[2]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


class UnionFind(object):
    '''Represents a data structure that tracks a set of elements partitioned
       into a number of disjoint (non-overlapping) subsets.
    Landau notation: O(α(n)), where α(n) is the inverse Ackermann function.
    See:
    https://www.youtube.com/watch?v=zV3Ul2pA2Fw
    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
    https://atcoder.jp/contests/abc120/submissions/4444942
    '''

    def __init__(self, number_count: int):
        '''
        Args:
            number_count: The size of elements (greater than 2).
        '''
        self.parent_numbers = [-1 for _ in range(number_count)]

    def find_root(self, number: int) -> int:
        '''Follows the chain of parent pointers from number up the tree until
           it reaches a root element, whose parent is itself.
        Args:
            number: The trees id (0-index).
        Returns:
            The index of a root element.
        '''
        if self.parent_numbers[number] < 0:
            return number

        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])
        return self.parent_numbers[number]

    def get_group_size(self, number: int) -> int:
        '''
        Args:
            number: The trees id (0-index).
        Returns:
            The size of group.
        '''
        return -self.parent_numbers[self.find_root(number)]

    def is_same_group(self, number_x: int, number_y: int) -> bool:
        '''Represents the roots of tree number_x and number_y are in the same
           group.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        return self.find_root(number_x) == self.find_root(number_y)

    def merge_if_needs(self, number_x: int, number_y: int) -> bool:
        '''Uses find_root to determine the roots of the tree number_x and
           number_y belong to. If the roots are distinct, the trees are combined
           by attaching the roots of one to the root of the other.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        x = self.find_root(number_x)
        y = self.find_root(number_y)

        if x == y:
            return False

        if self.get_group_size(x) >= self.get_group_size(y):
            self.parent_numbers[x] += self.parent_numbers[y]
            self.parent_numbers[y] = x
        else:
            self.parent_numbers[y] += self.parent_numbers[x]
            self.parent_numbers[x] = y
        return True


def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    x = [None for _ in range(n)]
    y = [None for _ in range(n)]

    for i in range(n):
        xi, yi = map(int, input().split())
        xi -= 1
        yi -= 1

        x[i] = (xi, i)
        y[i] = (yi, i)

    new_x = sorted(x)
    new_y = sorted(y)
    road = list()

    for _from, _to in zip(new_x, new_x[1:]):
        cost = abs(_from[0] - _to[0])
        road.append((_from[1], _to[1], cost))

    for _from, _to in zip(new_y, new_y[1:]):
        cost = abs(_from[0] - _to[0])
        road.append((_from[1], _to[1], cost))

    new_road = sorted(road, key=lambda x: x[2])
    uf = UnionFind(n)
    ans = 0

    for nr in new_road:
        if uf.merge_if_needs(nr[0], nr[1]):
            ans += nr[2]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve_abc065d():
    from collections import namedtuple
    from operator import attrgetter
    from itertools import tee
    import sys

    input = sys.stdin.readline

    City = namedtuple('City', 'x y idx')
    Edge = namedtuple('Edge', 'cost a b')
    N = int(input())

    cities = []
    for city_idx in range(N):
        x, y = map(int, input().split())
        c_ = City(x, y, city_idx)
        cities.append(c_)
    cities_x_asc = sorted(cities, key=attrgetter('x'))
    cities_y_asc = sorted(cities, key=attrgetter('y'))

    edges = []

    it_x = iter(cities_x_asc)
    gx1, gx2 = tee(it_x, 2)
    next(gx2)
    for c1, c2 in zip(gx1, gx2):
        d_ = c2.x - c1.x
        e_ = Edge(d_, c1.idx, c2.idx)
        edges.append(e_)
    # x方向にN-1本の辺を張る

    it_y = iter(cities_y_asc)
    gy1, gy2 = tee(it_y, 2)
    next(gy2)
    for c1, c2 in zip(gy1, gy2):
        d_ = c2.y - c1.y
        e_ = Edge(d_, c1.idx, c2.idx)
        edges.append(e_)
    # y方向にN-1本の辺を張る

    edges.sort(key=attrgetter('cost'))

    # <Kruskal’s Algorithm>
    # https://tjkendev.github.io/procon-library/python/graph/min_st_kruskal.html
    # E = [(cost, v, w), ...]
    #   G上の全ての辺(v, w)とそのcostを含むlist

    # Union-Findを使うことで頂点間の連結判定を行う
    *p, = range(N)

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

    def unite(x, y):
        px = root(x)
        py = root(y)
        if px == py:
            return 0
        if px < py:
            p[py] = px
        else:
            p[px] = py
        return 1

    mi = 0
    for e_ in edges:
        if unite(e_.a, e_.b):
            mi += e_.cost

    # miが最小全域木の解

    print(mi)
    return


if __name__ == '__main__':
    solve_abc065d()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納　par[x] == x の時そのノードは根
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0)
        self.rank = [0] * (n+1)
        # 各々の集合の要素数（根が代表して値を持っておく）
        self.count = [1] * (n+1)

    # 検索
    def find(self, x):
        # 根ならその番号を返す
        root = x
        queue = [x]
        data = []
        while queue:
            now = queue.pop()
            if self.par[now] == now:
                root = now
            else:
                # 根でないなら親の要素で再検索
                data.append(now)
                queue.append(self.par[now])
        # 検索する過程で親を更新
        for y in data:
            self.par[y] = root
        return root

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        t = (x == y)
        if UnionFind.same_check(self, x, y):
            return t
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.count[y] += self.count[x]
            self.count[x] = 0
        else:
            self.par[y] = x
            self.count[x] += self.count[y]
            self.count[y] = 0
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        return t

    # 同じ集合に属しているか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    # 属している集合の要素数
    def size(self, x):
        q = UnionFind.find(self, x)
        return self.count[q]


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

edge = []
vertex.sort()
for i in range(1, n):
    edge.append((vertex[i][0] - vertex[i - 1][0], vertex[i][2], vertex[i - 1][2]))

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

edge.sort()
u = UnionFind(n)
ans = 0
for d, i, j in edge:
    if u.union(i, j):
        continue
    ans += d

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, n):
    self.parents = list(range(n))
    self.ranks = [0] * n

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

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

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

n = int(input())
X = [None] * n
Y = [None] * n
for i in range(n):
  x, y = map(int, input().split())
  X[i] = (x, i)
  Y[i] = (y, i)
X.sort(key=lambda x: x[0])
Y.sort(key=lambda y: y[0])
Z = [None] * (2 * n - 2)
for i in range(n - 1):
  Z[2 * i] = (X[i + 1][0] - X[i][0], X[i][1], X[i + 1][1])
  Z[2 * i + 1] = (Y[i + 1][0] - Y[i][0], Y[i][1], Y[i + 1][1])
Z.sort(key=lambda z: z[0])

u = UnionFind(n)
total = 0
count = 0
for z in Z:
  d, a, b = z
  if not u.same(a, b):
    u.unite(a, b)
    total += d
    count += 1
    if count == n - 1:
      break
print(total)

Submission status: Accepted

Solution code:
import heapq

def prim():
    used = [1] * n
    used[0] = 0
    lis = []
    res = 0
    
    for a,b in edge[0]:
        heapq.heappush(lis,a*(10**6)+b)
        
    while lis:
        minedge = heapq.heappop(lis)
        
        if used[minedge%(10**6)] == 0:
            continue

        v = minedge%(10**6)
        used[v] = 0

        for q in edge[v]:
            if used[q[1]] == 1:
                heapq.heappush(lis , q[0]*(10**6) + q[1] )
        res += (minedge // (10**6))
    return res

n = int(input())
edge = [[] for _ in range(n)]
xsort = [[0]*2 for _ in range(n)]
ysort = [[0]*2 for _ in range(n)]

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

for i in range(n-1):
    edge[xsort[i][1]].append([xsort[i+1][0] - xsort[i][0] , xsort[i+1][1]])
    edge[xsort[i+1][1]].append([xsort[i+1][0] - xsort[i][0] , xsort[i][1]])
    edge[ysort[i][1]].append([ysort[i+1][0] - ysort[i][0] , ysort[i+1][1]])
    edge[ysort[i+1][1]].append([ysort[i+1][0] - ysort[i][0] , ysort[i][1]])
    
print(prim())

Submission status: Accepted

Solution code:
import sys 
input = sys.stdin.readline
n = int(input())
data = []
class UnionFind:
    def __init__(self, n):
        #親ノードの番号を格納
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)
    def find(self, x):
        #根ならその番号を返す
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self, x, y):
        #同じかどうかの確認
        return self.find(x) == self.find(y)
    def union(self, x, y):
        #統合する
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = 0
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
        else:
            self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
            self.size[y] = 0
    def getsize(self, x):
        p = self.find(x)
        return self.size[p]
x = []
y = []
for i in range(n):
    a,b = map(int, input().split())
    x.append([a,i+1])
    y.append([b,i+1])
x.sort(key = lambda x: x[0])
y.sort(key = lambda x: x[0])
edge = []
for i in range(n-1):
    edge.append([x[i+1][0] - x[i][0],x[i+1][1],x[i][1]])
    edge.append([y[i+1][0] - y[i][0],y[i+1][1],y[i][1]])
#edge[i][0] = cost, [1] -> [2]でつながっている辺
edge.sort(key = lambda x: x[0])
UF = UnionFind(n)
ans = 0
for i in range(len(edge)):
    cost,a,b = edge[i]
    if UF.same_check(a,b):
        continue
    else:
        ans += cost
        UF.union(a,b)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
import heapq
class Prim():
    """
    ・無向辺
    ・負のコストがあっても大丈夫？
    ・計算量はO(E log|V|)　
    ・heapを使う
    """
    
    class Edge():
        #重み付き有向辺（あとで往復させる）
        
        def __init__(self, _to, _cost):
            self.to =_to
            self.cost = _cost
    
    def __init__(self, V):
        #引数Vは頂点数
        self.G = [[] for _ in range(V)] #隣接リストG[u][i]が，頂点uのi番目の辺
        self. _E = 0 #辺の数
        self._V = V #頂点数
    
    #proparty - 辺の数
    def E(self):
        return self._E
    
    #proparty - 頂点数
    def V(self):
        return self._V
    
    def add(self, _from, _to, _cost):
        #2頂点と辺のコストを追加
        self.G[_from].append(self.Edge(_to,_cost))
        self._E +=1
        
    def add2(self, _from, _to, _cost):
        #2頂点と辺のコスト（無向）を追加
        self.G[_from].append(self.Edge(_to, _cost))
        self.G[_to].append(self.Edge(_from, _cost))
        self._E +=1
        
    def CostSum(self):
        #print(self.G[0][0].cost)
        
        used = [0]*self.V()
        que = [] #priority queue
        heapq.heappush(que,(0,0)) #始点の距離と頂点番号=0をヒープに追加
        ans =0 #辺の長さの和
        
        while len(que)!=0:
            #print("que:",format(que))
            #キューに格納されてある中で一番コストが小さい頂点を取り出す
            cost,v = heapq.heappop(que)
            
            #すでにX内にあれば(使用ずみならば)処理しない
            if used[v] ==1:
                continue
            used[v] = 1
            ans += cost
            
            #現在の全域木Xから，Xの外にある頂点e.toとの距離を見てqueに入れていく
            for i in range(len(self.G[v])):
                e = self.G[v][i] #vのi個目の隣接辺
                #print("e:",format(e.to))
                if used[e.to]==0:
                    heapq.heappush(que,(e.cost,e.to))
                    
        return ans   



def main():
    mod=10**9+7
    N=I()
    xyi=[[0,0,0] for _ in range(N)]
    for i in range(N):
        xyi[i][0],xyi[i][1]=MI()
        xyi[i][2]=i
    xyi.sort()
    prim = Prim(N)
    for i in range(N-1):
        prim.add2(xyi[i][2],xyi[i+1][2],abs(xyi[i][0]-xyi[i+1][0]))
        
    xyi.sort(key=lambda x: x[1])
    for i in range(N-1):
        prim.add2(xyi[i][2],xyi[i+1][2],abs(xyi[i][1]-xyi[i+1][1]))

        
    ans = prim.CostSum()
    
    print(ans)
    

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
import decimal
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()
    x = []
    y = []
    for _ in range(N):
        xx,yy = MAP()
        x.append(xx)
        y.append(yy)
    x = [(x[i],i) for i in range(N)]
    y = [(y[i],i) for i in range(N)]
    x.sort(key=lambda x:x[0])
    y.sort(key=lambda x:x[0])
    edges = []
    for i in range(N-1):
        edges.append((x[i][1],x[i+1][1],x[i+1][0]-x[i][0]))
        edges.append((y[i][1],y[i+1][1],y[i+1][0]-y[i][0]))
    edges.sort(key=lambda x:x[2])
    uf = UnionFind(N)
    answer = 0
    for i in range(len(edges)):
        s,t,w = edges[i]
        if not uf.same(s,t):
            uf.union(s,t)
            answer += w
    print(answer)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
import decimal
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()
    x = []
    y = []
    for _ in range(N):
        xx,yy = MAP()
        x.append(xx)
        y.append(yy)
    x = [(x[i],i) for i in range(N)]
    y = [(y[i],i) for i in range(N)]
    x.sort()
    y.sort()
    edges = []
    for i in range(N-1):
        edges.append((x[i][1],x[i+1][1],x[i+1][0]-x[i][0]))
        edges.append((y[i][1],y[i+1][1],y[i+1][0]-y[i][0]))
    edges.sort(key=lambda x:x[2])
    uf = UnionFind(N)
    answer = 0
    for i in range(len(edges)):
        s,t,w = edges[i]
        if not uf.same(s,t):
            uf.union(s,t)
            answer += w
    print(answer)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop, heapify
from pprint import pprint

N = int(sys.stdin.readline().strip())

points = []
for i in range(N):
    x, y = map(int, sys.stdin.readline().strip().split())
    points.append((i, x, y))

x_sorted = sorted(points, key=lambda x:x[1])
y_sorted = sorted(points, key=lambda x:x[2])
# pprint(x_sorted)

edges = [[] for _ in range(N)]
for i, (p1, x1, y1) in enumerate(x_sorted[:-1]):
    p2, x2, y2 = x_sorted[i+1]
    edges[p1].append((p2, x2 - x1))
    edges[p2].append((p1, x2 - x1))

for i, (p1, x1, y1) in enumerate(y_sorted[:-1]):
    p2, x2, y2 = y_sorted[i+1]
    edges[p1].append((p2, y2 - y1))
    edges[p2].append((p1, y2 - y1))

# prim法
used = set()
q = []
for i in range(N):
    if len(edges[i]):
        for t, w in edges[i]:
            q.append((w, t))
        used.add(i)
        break
heapify(q)

ans = 0
while q:
    w, s = heappop(q)
    if s in used:
        continue
    used.add(s)
    ans += w
    for t, w in edges[s]:
        if t in used:
            continue
        heappush(q, (w, t))

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush, heapify
import sys
input = lambda: sys.stdin.readline().rstrip()

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

    if x == y:
        return
    if parents[x] > parents[y]:
        x, y = y, x
    parents[x] += parents[y]
    parents[y] = x

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

N = int(input())

verticies_x = []
verticies_y = []

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

edge = []

for i in range(N-1):
    tmp_x = verticies_x[i+1][0] - verticies_x[i][0]
    tmp_y = verticies_y[i+1][0] - verticies_y[i][0]
    edge.append((tmp_x, verticies_x[i][1], verticies_x[i+1][1]))
    edge.append((tmp_y, verticies_y[i][1], verticies_y[i+1][1]))

ans = 0
edge.sort()
parents = [-1] * N
for cost, s, g in edge:
    if same(s,g):
        continue
    else:
        union(s,g)
        ans += cost
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

def find_parent(x):
    y=parent[x]
    if y<0:
        return x
    parent[x]=find_parent(y)
    return parent[x]

def connect(a,b):
    c=find_parent(a)
    d=find_parent(b)
    if c==d:
        return
    if parent[c]<parent[d]:
        parent[c]+=parent[d]
        parent[d]=c
    else:
        parent[d]+=parent[c]
        parent[c]=d
    return

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()
edge=[]
for i in range(1,N):
    edge.append([X[i][0]-X[i-1][0],X[i-1][1],X[i][1]])
    edge.append([Y[i][0]-Y[i-1][0],Y[i-1][1],Y[i][1]])
edge.sort()
parent=[-1]*N

ans=0
for l,a,b in edge:
    if find_parent(a)==find_parent(b):
        continue
    else:
        ans+=l
        connect(a,b)

print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

def find_parent(x):
    y=parent[x]
    if y<0:
        return x
    parent[x]=find_parent(y)
    return parent[x]

def connect(a,b):
    c=find_parent(a)
    d=find_parent(b)
    if c==d:
        return
    if parent[c]<parent[d]:
        parent[c]+=parent[d]
        parent[d]=c
    else:
        parent[d]+=parent[c]
        parent[c]=d
    return

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()
edge=[]
for i in range(1,N):
    edge.append([X[i][0]-X[i-1][0],X[i-1][1],X[i][1]])
    edge.append([Y[i][0]-Y[i-1][0],Y[i-1][1],Y[i][1]])
edge.sort()
parent=[-1]*N

ans=0
for l,a,b in edge:
    if find_parent(a)==find_parent(b):
        continue
    else:
        ans+=l
        connect(a,b)

print(ans)