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:
from heapq import *
#->: 型注釈
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    
    #要素xが属するグループの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    #xのグループとyのグループを併合
    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))
    # print(x1, x2)
    # print("=--")

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))
    # print(y1, y2)

ans = 0
# print(H)
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)

Submission status: Accepted

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

# import fractions

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)
# lcm = lambda x, y: (x * y) // fractions.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 = [], []

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

    # クラスカル法で、重みの小さい順に辺を繋げて木とする
    # UnionFind木を用いて既に繋がっているか否かを判定し
    # 最小全域木をつくる
    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()

Submission status: Accepted

Solution code:
import sys
#import time
import copy
#from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
#import heapq
#import time

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)

    # ノードxのrootノードを見つける
    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
    # xとyが同じグループに属するか判断
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # ノードxが属する木のサイズを返す
    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)

Submission status: Accepted

Solution code:
import sys
#import time
import copy
#from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
#import heapq
#import time

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)

    # ノードxのrootノードを見つける
    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
    # xとyが同じグループに属するか判断
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # ノードxが属する木のサイズを返す
    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)

Submission status: Accepted

Solution code:
import sys
#import time
import copy
#from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
#import heapq
#import time

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)

    # ノードxのrootノードを見つける
    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
    # xとyが同じグループに属するか判断
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # ノードxが属する木のサイズを返す
    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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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)

    #print(nodes_sorted_by_x)
    #print(nodes_sorted_by_y)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

#最小全域木　クラスカル法
# 重み付き無向グラフで、それらの全ての頂点を結び連結するような木の最小のコストを求める
# 辺の重みの小さい順にみて、連結成分が閉路にならない辺を追加していく
# つなぐ頂点が同じ連結成分にないことをUnion Find Tree でみる

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

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
                root.member_num_ = root.member_num_ + unite_root.member_num_
            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                unite_root.member_num_ = root.member_num_ + unite_root.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])
G = [set() for _ in range(N+1)]
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])))
    G[X[i][1]].add(X[i+1][1])
    G[Y[i][1]].add(Y[i+1][1])
    G[X[i+1][1]].add(X[i][1])
    G[Y[i+1][1]].add(Y[i][1])
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)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.readline
N = int(input())
p = [tuple(map(int, input().split())) for _ in range(N)]
e = dd(list)
p = [(i, p[i][0], p[i][1]) for i in range(N)]
p.sort(key = lambda x: x[1])
for i in range(N - 1):
  x = p[i][0]
  y = p[i + 1][0]
  e[x].append((y, abs(p[i][1] - p[i + 1][1])))
  e[y].append((x, abs(p[i][1] - p[i + 1][1])))
p.sort(key = lambda x: x[2])
for i in range(N - 1):
  x = p[i][0]
  y = p[i + 1][0]
  e[x].append((y, abs(p[i][2] - p[i + 1][2])))
  e[y].append((x, abs(p[i][2] - p[i + 1][2])))
class prim:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def MSTcost(self):
    h = []
    visited = [0] * (self.n + 1)
    ks = list(self.e.keys())
    b = pow(10, 10)
    for edge in self.e[ks[0]]:
      heapq.heappush(h, edge[1] * b + edge[0])
    res = 0
    visited[ks[0]] = 1
    while len(h):
      p = heapq.heappop(h)
      p0 = p // b
      p1 = p % b
      if visited[p1]: continue
      visited[p1] = 1
      for q in self.e[p1]:
        if visited[q[0]]:
          continue
        heapq.heappush(h, q[1] * b + q[0])
      res += p0
    return res
pri = prim(N, e)
print(pri.MSTcost())

Submission status: Accepted

Solution code:
import heapq
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])

def kruskal(n, edge):
    ans = 0
    uf = UnionFind(n)
    while True:
        d, v, u = heapq.heappop(edge)
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            n -= 1
            ans += d
        if n < 2: return ans
    return ans

n = int(input())
x, y = [None]*n, [None]*n

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

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

edge = []
for i in range(n-1):
    heapq.heappush(edge, (x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    heapq.heappush(edge, (y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))

del x, y
print(kruskal(n, edge))

Submission status: Accepted

Solution code:
N=int(input())
import sys
input=sys.stdin.readline
X=[(-10**10,0)]
Y=[(-10**10,0)]

for i in range(N):
    x,y=map(int,input().split())
    X.append((x,i+1))
    Y.append((y,i+1))
X.append((10**10,N+1))
Y.append((10**10,N+1))
X.sort()
Y.sort()

#print(X,Y)

L=[[]for i in range(N+1)]
for i in range(1,N+1):
    L[X[i][1]].append((X[i][0]-X[i-1][0],X[i-1][1]))
    L[X[i][1]].append((X[i+1][0]-X[i][0],X[i+1][1]))
for i in range(1,N+1):
    L[Y[i][1]].append((Y[i][0]-Y[i-1][0],Y[i-1][1]))
    L[Y[i][1]].append((Y[i+1][0]-Y[i][0],Y[i+1][1]))
#print(L)
C=[1 for i in range(N+2)]
C[0]=0
C[-1]=0
C[1]=0
import heapq
ans=0
Q=L[1]
heapq.heapify(Q)
for i in range(10**6):
    #print(ans,Q)
    #print(C)
    if len(Q)==0:
        break
    q=heapq.heappop(Q)
    if C[q[1]]==0:
        continue
    else:
        C[q[1]]=0
        ans+=q[0]
        for j in range(4):
            if C[L[q[1]][j][1]]==1:
                heapq.heappush(Q,L[q[1]][j])
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
city=[0]*N
for i in range(N):
    x,y=map(int,input().split())
    city[i]=(i,x,y)
city.sort(key=lambda x:x[1])
data=[(city[i][0],city[i+1][0],city[i+1][1]-city[i][1]) for i in range(N-1)]
city.sort(key=lambda x:x[2])
data+=[(city[i][0],city[i+1][0],city[i+1][2]-city[i][2]) for i in range(N-1)]
data.sort(key=lambda x:x[2])
f = list(range(N))
costs = [1] * N
def find(x):
    if f[x] != x:
        f[x] = find(f[x])
    return f[x]
res = 0
for i, j, k in data:
    fi, fj = find(i), find(j)
    if fi == fj:
        continue
    else:
        if costs[fi] <= costs[fj]:
            f[fi] = fj
            costs[fj] += costs[fi]
            res += k
        else:
            f[fj] = fi
            costs[fi] += costs[fj]
            res += k
print(res)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [-1 for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            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 not x==y: # 根が同じでない場合のみ併合する
            if self.rank[x] < self.rank[y]:
                self.par[y] += self.par[x] # 要素数を併合
                self.par[x] = y # 根を付け替えている
            else:
                self.par[x] += self.par[y]
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
        
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y) 

def main():
    import sys
    input = sys.stdin.readline
    
    N = int(input())
    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 a:a[0])
    Y = sorted(Y,key=lambda a:a[0])
    DX = []
    DY = []
    for i in range(N-1):
        x1,i1 = X[i]
        x2,i2 = X[i+1]
        DX.append([abs(x1-x2),i1,i2])
        y1,i1 = Y[i]
        y2,i2 = Y[i+1]
        DY.append([abs(y1-y2),i1,i2])
    
    DX = sorted(DX,key=lambda a:a[0])
    DY = sorted(DY,key=lambda a:a[0])
    #print(DX)
    #print(DY)
        
    ans = 0
    A = UnionFind(N)
    i,j = 0,0
    c = 0
    while c < N-1:
        if i<=N-2 and j<=N-2:
            if DX[i][0] < DY[j][0]:
                cost,m1,m2 = DX[i]
                if not A.same_check(m1,m2):
                    #print(m1,m2)
                    A.union(m1,m2)
                    c += 1
                    ans += cost
                i += 1
            else:
                cost,m1,m2 = DY[j]
                if not A.same_check(m1,m2):
                    #print(m1,m2)
                    A.union(m1,m2)
                    c += 1
                    ans += cost
                j += 1
        elif i==N-1:
            cost,m1,m2 = DY[j]
            if not A.same_check(m1,m2):
                #print(m1,m2)
                A.union(m1,m2)
                c += 1
                ans += cost
            j += 1
        else:
            cost,m1,m2 = DX[i]
            if not A.same_check(m1,m2):
                #print(m1,m2)
                A.union(m1,m2)
                c += 1
                ans += cost
            i += 1
    print(ans)
        
    
    
main()

Submission status: Accepted

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

def same_tree(node_a, node_b):
    if node_a.root() == node_b.root():
        return True

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        node = self
        while not node.is_root:
            node = node.parent
        return node

def main():
    N = int(input())
    
    nodes = [Node() for i in range(N)]

    # 各町の座標をタプル(i, x, y)に入れて配列に格納
    xs = []
    ys = []
    for i in range(N):
        x, y = map(int, input().split())
        xs.append((x, i))
        ys.append((y, i))
    xs = sorted(xs)
    ys = sorted(ys)

    # 使う可能性のある辺のみを取り出す
    edges = []
    for i in range(1, N):
        edges.append((xs[i][0] - xs[i-1][0], xs[i-1][1], xs[i][1]))
        edges.append((ys[i][0] - ys[i-1][0], ys[i-1][1], ys[i][1]))
    edges = sorted(edges)

    # クラスカル法
    ans = 0
    for (cost, a, b) in edges:
        if not same_tree(nodes[a], nodes[b]):
            unite(nodes[a], nodes[b])
            ans += cost
    print(ans)

if __name__ == "__main__":
    main()