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:
import array
import collections


Edge = collections.namedtuple("Edge", "start end weight")


class UnionFind(object):

    def __init__(self, number_of_nodes):  # 初期化
        self.par = array.array("L", range(number_of_nodes))
        self.rank = array.array("L", (0 for i in range(number_of_nodes)))

    def root(self, node):  # 根を求める
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r  # 経路圧縮
            return r

    def in_the_same_set(self, node1, node2):  # 同じ集合に属するか
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):  # 属する集合を併合
        x = self.root(node1)
        y = self.root(node2)
        if x == y:
            pass
        elif 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


# Kruskal法により最小全域木を求める
def compute_mst_kruskal(max_v, edges):
    edges.sort(key=lambda edge: edge.weight)
    uf = UnionFind(max_v)
    mst = []
    for edge in edges:
        if not uf.in_the_same_set(edge.start, edge.end):
            uf.unite(edge.start, edge.end)
            mst.append(edge)
    return mst



N = int(input())
xy = [list(map(int, input().split())) + [i] for i in range(N)]
sort_x = sorted(xy,key = lambda x:x[0])
sort_y = sorted(xy,key = lambda x:x[1])
#print(sort_x,sort_y)

max_v, max_e = N,2*N
entire = []
for i in range(1,N):
    entire.append([sort_x[i][2], sort_x[i-1][2],sort_x[i][0] - sort_x[i-1][0]])
    entire.append([sort_y[i][2], sort_y[i-1][2],sort_y[i][1] - sort_y[i-1][1]])
#print(entire)
edges = [Edge(*k) for k in entire]
#print(edges)
# max_v, max_e = map(int, input().split())
#edges = [Edge(*map(int, input().split())) for _ in range(max_e)]
mst = compute_mst_kruskal(max_v, edges)
print(sum(edge.weight for edge in mst))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C

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

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

def unite(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
n = I()
v = LIR(n)
l = [None for i in range(2*n-2)]
for i in range(n):
    v[i].append(i)
par = [i for i in range(n)]
rank = [0 for i in range(n)]
v.sort(key = lambda x:x[0])
for i in range(n-1):
    l[i] = [v[i][2],v[i+1][2],v[i+1][0]-v[i][0]]
v.sort(key = lambda x:x[1])
for i in range(n-1):
    l[i+n-1] = [v[i][2],v[i+1][2],v[i+1][1]-v[i][1]]
l.sort(key = lambda x:x[2])
k = 0
ans = 0
for i in range(2*n-2):
    x,y,c = l[i]
    if not same(x,y):
        k += 1
        ans += c
        unite(x,y)
    if k == n-1:break
print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C

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

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

def unite(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
n = I()
v = LIR(n)
l = defaultdict(int)
for i in range(n):
    v[i].append(i)
par = [i for i in range(n)]
rank = [0 for i in range(n)]
v.sort(key = lambda x:x[0])
for i in range(n-1):
    l[i] = [v[i][2],v[i+1][2],v[i+1][0]-v[i][0]]
v.sort(key = lambda x:x[1])
for i in range(n-1):
    l[i+n-1] = [v[i][2],v[i+1][2],v[i+1][1]-v[i][1]]
l = list(l.values())
l.sort(key = lambda x:x[2])
k = 0
ans = 0
for i in range(2*n-2):
    x,y,c = l[i]
    if not same(x,y):
        k += 1
        ans += c
        unite(x,y)
    if k == n-1:break
print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C

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

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

def unite(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
n = I()
v = LIR(n)
l = []
for i in range(n):
    v[i].append(i)
par = [i for i in range(n)]
rank = [0 for i in range(n)]
v.sort(key = lambda x:x[0])
for i in range(n-1):
    l.append([v[i][2],v[i+1][2],v[i+1][0]-v[i][0]])
v.sort(key = lambda x:x[1])
for i in range(n-1):
    l.append([v[i][2],v[i+1][2],v[i+1][1]-v[i][1]])
l.sort(key = lambda x:x[2])
k = 0
ans = 0
for i in range(len(l)):
    x,y,c = l[i]
    if not same(x,y):
        k += 1
        ans += c
        unite(x,y)
    if k == n-1:break
print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        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 same_check(self, x, y):
        return self.find(x) == self.find(y)

N = int(input())
# minimum spanning tree
res = 0
pos = []
for i in range(N):
    p = tuple(int(x) for x in input().split())
    p = (p[0], p[1], i)
    pos.append(p)
x_order = sorted(pos)
y_order = sorted(pos, key=lambda x: x[1])

uf = UnionFind(N)
x_i = y_i = 0
num_edge = 0

edge = []
for i in range(len(x_order) - 1):
    v1 = x_order[i+1]
    v2 = x_order[i]
    edge.append((v1[0] - v2[0], v1[2], v2[2]))
    v1 = y_order[i+1]
    v2 = y_order[i]
    edge.append((v1[1] - v2[1], v1[2], v2[2]))

edge.sort()
i = 0
while num_edge < N-1:
    e = edge[i]
    i += 1
    if uf.same_check(e[1], e[2]):
        continue
    else:
        res += e[0]
        uf.union(e[1], e[2])
        num_edge += 1

print(res)

Submission status: Accepted

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

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

roads = []
for i in range(n - 1):
    i1, x1, y1 = ixy[i]
    i2, x2, y2 = ixy[i + 1]
    roads.append((x2 - x1, i1, i2))

ixy.sort(key=lambda x: x[2])
for i in range(n - 1):
    i1, x1, y1 = ixy[i]
    i2, x2, y2 = ixy[i + 1]
    roads.append((y2 - y1, i1, i2))

p = [i for i in range(n)]


def f_p(x):
    if x == p[x]:
        return x
    p[x] = f_p(p[x])
    return p[x]


roads.sort()
total_c = 0
for c, i1, i2 in roads:
    p1 = f_p(i1)
    p2 = f_p(i2)
    if p1 != p2:
        p[p1] = p2
        total_c += c

print(total_c)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]

    def find(self, x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x

    def union(self, s1, s2):
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]


n = int(input())

x = dict()
y = dict()

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

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

r = []

for i in range(n - 1):
    r.append([x[i][0], x[i + 1][0], x[i + 1][1] - x[i][1]])
    r.append([y[i][0], y[i + 1][0], y[i + 1][1] - y[i][1]])

r = sorted(r, key=lambda t:t[2])

uft = UnionFind(n)

ans = 0
for a, b, c in r:
    ra = uft.find(a)
    rb = uft.find(b)
    if ra != rb:
        ans += c
        uft.union(ra, rb)

print(ans)

Submission status: Accepted

Solution code:
class UnionFind(object):
  def __init__(self,n):
    self.parent={i:i for i in range(1,n+1)}
    self.size={i:1 for i in range(1,n+1)}
  def find(self,a):
    if self.parent[a]!=a:
      self.parent[a]=self.find(self.parent[a])
    return self.parent[a]
  def unite(self,a,b):
    a=self.find(a)
    b=self.find(b)
    if a==b:return
    if self.size[a]>self.size[b]:
      self.size[a]+=self.size[b]
      self.parent[b]=a
    else:
      self.size[b]+=self.size[a]
      self.parent[a]=b
  def isunited(self,a,b):
    return self.find(a)==self.find(b)

N=int(input())
l=[[i+1]+list(map(int,input().split())) for i in range(N)]
o=[]

l.sort(key=lambda x:x[1])
for i in range(N-1):
    o.append((l[i][0],l[i+1][0],l[i+1][1]-l[i][1]))

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

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

ans=0
uft=UnionFind(N)
for town1,town2,cost in o:
    if not uft.isunited(town1,town2):
        uft.unite(town1,town2)
        ans+=cost

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
n = int(input())
x =[]
y =[]
info = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  x.append([i,info[i][0]])
  y.append([i,info[i][1]])

x = sorted(x,key=itemgetter(1))
y = sorted(y,key=itemgetter(1))
tree = []
#for i in range(n):
#  if i==0:
#    tree[x[i][0]].append([x[i+1][0],abs(x[i][1]-x[i+1][1])])
#    tree[y[i][0]].append([y[i+1][0],abs(y[i][1]-y[i+1][1])])
#  elif i==n-1:
#    tree[x[i][0]].append([x[i-1][0],abs(x[i][1]-x[i-1][1])])
#    tree[y[i][0]].append([y[i-1][0],abs(y[i][1]-y[i-1][1])])
#  else:
#    tree[x[i][0]].append([x[i+1][0],abs(x[i][1]-x[i+1][1])])
#    tree[x[i][0]].append([x[i-1][0],abs(x[i][1]-x[i-1][1])])
#    tree[y[i][0]].append([y[i+1][0],abs(y[i][1]-y[i+1][1])])
#    tree[y[i][0]].append([y[i-1][0],abs(y[i][1]-y[i-1][1])])
    
for i in range(n-1):
    tree.append([x[i][0],x[i+1][0],abs(x[i][1]-x[i+1][1])])
    tree.append([y[i][0],y[i+1][0],abs(y[i][1]-y[i+1][1])])

#UnionFindクラス
class UnionFind(object):

  def __init__(self, n=1):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ in range(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]
  
  # xとyの根を結合させる
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x != y:
      if self.rank[x] < self.rank[y]:
        x, y = y, x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
      self.par[y] = x
  
  # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
  def is_same(self, x, y):
    return self.find(x) == self.find(y)

uf = UnionFind(len(tree))
tree = sorted(tree,key=itemgetter(2))
ans = 0

for i in tree:
  x,y,kyori = i
  if not uf.is_same(x,y):
    uf.union(y,x)
    ans += kyori
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
n = int(input())
x =[]
y =[]
info = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  x.append([i,info[i][0]])
  y.append([i,info[i][1]])

x = sorted(x,key=itemgetter(1))
y = sorted(y,key=itemgetter(1))
tree = []

for i in range(n-1):
    tree.append([x[i][0],x[i+1][0],x[i+1][1]-x[i][1]])
    tree.append([y[i][0],y[i+1][0],y[i+1][1]-y[i][1]])

#UnionFindクラス
class UnionFind(object):

  def __init__(self, n=1):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ in range(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]
  
  # xとyの根を結合させる
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x != y:
      if self.rank[x] < self.rank[y]:
        x, y = y, x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
      self.par[y] = x
  
  # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
  def is_same(self, x, y):
    return self.find(x) == self.find(y)

uf = UnionFind(len(tree))
tree = sorted(tree,key=itemgetter(2))
ans = 0

for i in tree:
  x,y,kyori = i
  if not uf.is_same(x,y):
    uf.union(y,x)
    ans += kyori
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
n = int(input())
x =[]
y =[]
info = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  x.append([i,info[i][0]])
  y.append([i,info[i][1]])

x = sorted(x,key=itemgetter(1))
y = sorted(y,key=itemgetter(1))
tree = []
#for i in range(n):
#  if i==0:
#    tree[x[i][0]].append([x[i+1][0],abs(x[i][1]-x[i+1][1])])
#    tree[y[i][0]].append([y[i+1][0],abs(y[i][1]-y[i+1][1])])
#  elif i==n-1:
#    tree[x[i][0]].append([x[i-1][0],abs(x[i][1]-x[i-1][1])])
#    tree[y[i][0]].append([y[i-1][0],abs(y[i][1]-y[i-1][1])])
#  else:
#    tree[x[i][0]].append([x[i+1][0],abs(x[i][1]-x[i+1][1])])
#    tree[x[i][0]].append([x[i-1][0],abs(x[i][1]-x[i-1][1])])
#    tree[y[i][0]].append([y[i+1][0],abs(y[i][1]-y[i+1][1])])
#    tree[y[i][0]].append([y[i-1][0],abs(y[i][1]-y[i-1][1])])
    
for i in range(n-1):
    tree.append([x[i][0],x[i+1][0],abs(x[i][1]-x[i+1][1])])
    tree.append([y[i][0],y[i+1][0],abs(y[i][1]-y[i+1][1])])

#UnionFindクラス
class UnionFind(object):

  def __init__(self, n=1):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ in range(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]
  
  # xとyの根を結合させる
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x != y:
      if self.rank[x] < self.rank[y]:
        x, y = y, x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
      self.par[y] = x
  
  # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
  def is_same(self, x, y):
    return self.find(x) == self.find(y)

uf = UnionFind(len(tree))
tree = sorted(tree,key=itemgetter(2))
ans = 0

for i in tree:
  x,y,kyori = i
  if not uf.is_same(x,y):
    uf.union(y,x)
    ans += kyori
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from heapq import heappush, heappop, heapify
n=int(input())
G=[[]for i in range(n)]
d=[]
for i in range(n):
    a,b=map(int,input().split())
    d.append((a,b,i))
d=sorted(d,key=lambda x:x[0])
for i in range(n-1):
    G[d[i][2]].append((d[i+1][0]-d[i][0],d[i+1][2]))
    G[d[i+1][2]].append((d[i+1][0]-d[i][0],d[i][2]))
d=sorted(d,key=lambda x:x[1])
for i in range(n-1):
    G[d[i][2]].append((d[i+1][1]-d[i][1],d[i+1][2]))
    G[d[i+1][2]].append((d[i+1][1]-d[i][1],d[i][2]))
used = [0 for i in range(n)]
que = [(c, w) for c, w in G[0]]
used[0] = 1
heapify(que)

ans = 0
while que:
    cv, v = heappop(que)
    if used[v]:
        continue
    used[v] = 1
    ans += cv
    for c, w in G[v]:
        if used[w]:
            continue
        heappush(que, (c, w))
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
points=[[i]+list(map(int,input().split())) for i in range(n)]
 
edges=[]
points.sort(key=lambda x: x[1])
for i in range(n-1):
    n1,x1,y1=points[i]
    n2,x2,y2=points[i+1]
    edges.append([n1,n2,x2-x1])
points.sort(key=lambda y: y[2])
for i in range(n-1):
    n1,x1,y1=points[i]
    n2,x2,y2=points[i+1]
    edges.append([n1,n2,y2-y1])

class UnionFind:
    def __init__(self,n):
        self.par=[i for i in range(n+1)]
        self.rank=[0]*(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 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
        else:
            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)

uf=UnionFind(n)
edges.sort(key=lambda c: c[2], reverse=True)
ans=0
i=0


while i!=n-1:
    x,y,cost=edges.pop()
    if not uf.same_check(x,y):
        ans+=cost
        uf.union(x,y)
        i+=1
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
import heapq
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(key=itemgetter(0))
Y.sort(key=itemgetter(0))

import sys
sys.setrecursionlimit(10**6)


class UnionFind(object):

    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        else:
            return False
u = UnionFind(N)
q = []
for i in range(N-1):
    q.append((X[i+1][0]-X[i][0], X[i+1][1], X[i][1]))
    q.append((Y[i+1][0]-Y[i][0], Y[i+1][1], Y[i][1]))
q.sort(key=itemgetter(0))
ans = 0
for elem in q:
    cost, a, b = elem
    if u.union(a, b):
        ans += cost
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
import heapq
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(key=itemgetter(0))
Y.sort(key=itemgetter(0))
G = [[] for _ in range(N)]
for i in range(N-1):
    G[X[i][1]].append((X[i+1][0]-X[i][0], X[i+1][1]))
    G[X[i+1][1]].append((X[i+1][0]-X[i][0], X[i][1]))
    G[Y[i][1]].append((Y[i+1][0]-Y[i][0], Y[i+1][1]))
    G[Y[i+1][1]].append((Y[i+1][0]-Y[i][0], Y[i][1]))

q = []
heapq.heapify(q)
for elem in G[0]:
    heapq.heappush(q, elem)
used = [False] * N
used[0] = True
ans = 0
while q:
    res = heapq.heappop(q)
    cost, nq = res
    if not used[nq]:
        used[nq] = True
        ans += cost
        for elem in G[nq]:
            heapq.heappush(q, elem)
print(ans)

Submission status: Accepted

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

    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):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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


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

x_order = sorted(ixy, key=lambda x: x[1])
y_order = sorted(ixy, key=lambda x: x[2])

edge = []

for i in range(1, N):
    pre_i1, pre_x1, pre_y1 = x_order[i - 1]
    i1, x1, y1 = x_order[i]
    edge.append((x1 - pre_x1, pre_i1, i1))
    pre_i2, pre_x2, pre_y2 = y_order[i - 1]
    i2, x2, y2 = y_order[i]
    edge.append((y2 - pre_y2, pre_i2, i2))

edge = sorted(edge, key=lambda x: x[0])
union_find = UnionFind(N)
ans = 0
for e in edge:
    cost, pre_i, i = e
    if union_find.check_same(pre_i, i):
        continue
    else:
        union_find.union(pre_i, i)
        ans += cost
print(ans)

Submission status: Accepted

Solution code:
import itertools

def find(table, x):
    stack = [x]
    while table[stack[-1]] != stack[-1]:
        stack.append(table[stack[-1]])
    
    for i in stack:
        table[i] = stack[-1]
    return table[x]


def union(table, x1, x2):
    p1 = find(table, x1)
    p2 = find(table, x2)
    table[p2] = p1

n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]

edges = []
cities = list(range(n))
for j in (0, 1):
    cities.sort(key=lambda city: points[city][j])
    for i in range(n - 1):
        city1, city2 = cities[i], cities[i + 1]
        (x1, y1), (x2, y2) = points[city1], points[city2]
        cost = min(abs(x1 - x2), abs(y1 - y2))
        edges.append((cost, city1, city2))
edges.sort() # key=lambda cost, city1, city2: cost

table = list(range(n))
answer = 0
for cost, city1, city2 in edges:
    parent1, parent2 = find(table, city1), find(table, city2)
    if parent1 != parent2:
        answer += cost
        union(table, city1, city2)

print(answer)

Submission status: Accepted

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

"""
・最小全域木、Union-Find
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from operator import itemgetter

# Union-Find木
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (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 union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

N = int(input())
X = [[0] * 2 for i in range(N)]
Y = [[0] * 2 for i in range(N)]
for i in range(N):
    x, y = map(int, input().split())
    X[i][0] = x
    X[i][1] = i
    Y[i][0] = y
    Y[i][1] = i
# 元indexを保持して座標位置順にソート
X.sort(key=itemgetter(0))
Y.sort(key=itemgetter(0))

edges = []
for i in range(1, N):
    # 座標上で隣り合う頂点同士で辺集合を作る
    edges.append((X[i-1][1], X[i][1], X[i][0] - X[i-1][0]))
    edges.append((Y[i-1][1], Y[i][1], Y[i][0] - Y[i-1][0]))
# コスト順にソート
edges.sort(key=itemgetter(2))

uf = UnionFind(N)
ans = 0
grp = N
# Union-Findで閉路を作らない確認をして最小全域木を作る
for x, y, w in edges:
    if not uf.same(x, y):
        uf.union(x, y)
        ans += w
        grp -= 1
    # グループが1つになれば、それ以上やる必要ない
    if grp == 1:
        break
print(ans)

Submission status: Accepted

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

"""
・最小全域木、Union-Find
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from operator import itemgetter

# Union-Find木
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (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 union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

N = int(input())
X = [[0] * 2 for i in range(N)]
Y = [[0] * 2 for i in range(N)]
for i in range(N):
    x, y = map(int, input().split())
    X[i][0] = x
    X[i][1] = i
    Y[i][0] = y
    Y[i][1] = i
# 元indexを保持して座標位置順にソート
X.sort()
Y.sort()

edges = []
for i in range(1, N):
    # 座標上で隣り合う頂点同士で辺集合を作る
    edges.append((X[i-1][1], X[i][1], X[i][0] - X[i-1][0]))
    edges.append((Y[i-1][1], Y[i][1], Y[i][0] - Y[i-1][0]))
# コスト順にソート
edges.sort(key=itemgetter(2))

uf = UnionFind(N)
ans = 0
grp = N
# Union-Findで閉路を作らない確認をして最小全域木を作る
for x, y, w in edges:
    if not uf.same(x, y):
        uf.union(x, y)
        ans += w
        grp -= 1
    # グループが1つになれば、それ以上やる必要ない
    if grp == 1:
        break
print(ans)

Submission status: Accepted

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

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from operator import itemgetter

# Union-Find木
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (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 union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

N = int(input())
X = [[0] * 2 for i in range(N)]
Y = [[0] * 2 for i in range(N)]
for i in range(N):
    x, y = map(int, input().split())
    X[i][0] = x
    X[i][1] = i
    Y[i][0] = y
    Y[i][1] = i
# 元indexを保持して座標位置順にソート
X.sort()
Y.sort()

edges = []
for i in range(1, N):
    # 座標上で隣り合う頂点同士で辺集合を作る
    edges.append((X[i-1][1], X[i][1], X[i][0] - X[i-1][0]))
    edges.append((Y[i-1][1], Y[i][1], Y[i][0] - Y[i-1][0]))
# コスト順にソート
edges.sort(key=itemgetter(2))

uf = UnionFind(N)
ans = 0
# Union-Findで閉路を作らない確認をして最小全域木を作る
for x, y, w in edges:
    if not uf.same(x, y):
        uf.union(x, y)
        ans += w
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

# x, y座標の値でソートして、隣接する街の間の道を、隣接リストadjに追加する
adj = [[] for i in range(N)]
for xy in [1, 2]:
    towns.sort(key=lambda t: t[xy])
    for i in range(N - 1):
        t1 = towns[i][0]
        t2 = towns[i + 1][0]
        cost = min(abs(towns[i + 1][1] - towns[i][1]), abs(towns[i + 1][2] - towns[i][2]))#towns[i + 1][xy] - towns[i][xy]
        adj[t1].append((t2, cost))
        adj[t2].append((t1, cost))

# 最小全域木を求める（プリム法）
import heapq
pq = []
heapq.heappush(pq, (0, 0))

done = set()
ans = 0
while pq:
    cost, v_now = heapq.heappop(pq)

    if v_now in done:
        continue

    ans += cost
    done.add(v_now)

    if len(done) == N:
        break

    for v, c in adj[v_now]:
        if v not in done:
            heapq.heappush(pq, (c, v))

print(ans)