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 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
data = []
edges = []
for i in range(N):
  x,y = IL()
  data.append([i,x,y])
  
data = sorted(data,key = lambda x:x[1])
for i in range(N-1):
  f = data[i][0]
  t = data[i+1][0]
  c = data[i+1][1]-data[i][1]
  edges.append([f,t,c])
  
data = sorted(data,key = lambda x:x[2])
for i in range(N-1):
  f = data[i][0]
  t = data[i+1][0]
  c = data[i+1][2]-data[i][2]
  edges.append([f,t,c])

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

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())
      
U = UnionFind(N)
ans = 0
for f,t,c in edges:
  if not U.same(f,t):
    U.union(f,t)
    ans += c
    
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline
import math
from heapq import heappush, heappop, heapify

def solve(n, nodes):
  xsort_nodes = sorted(nodes, key=lambda n: n[1])
  ysort_nodes = sorted(nodes, key=lambda n: n[2])
  edges = [[] for _ in range(n)]
  for i in range(n-1):
    prev_node = xsort_nodes[i]
    post_node = xsort_nodes[i+1]
    edges[prev_node[0]].append((abs(prev_node[1]-post_node[1]), post_node[0]))
  for i in range(n-1):
    prev_node = ysort_nodes[i]
    post_node = ysort_nodes[i+1]
    edges[prev_node[0]].append((abs(prev_node[2]-post_node[2]), post_node[0]))
  for i in range(1, n):
    prev_node = xsort_nodes[i-1]
    post_node = xsort_nodes[i]
    edges[post_node[0]].append((abs(prev_node[1]-post_node[1]), prev_node[0]))
  for i in range(1, n):
    prev_node = ysort_nodes[i-1]
    post_node = ysort_nodes[i]
    edges[post_node[0]].append((abs(prev_node[2]-post_node[2]), prev_node[0]))
  tree = [0]*n
  tree[0] = 1
  distance = 0
  current_edges = [*edges[0]]
  heapify(current_edges)
  while(len(current_edges)):
    d, x = heappop(current_edges)
    if tree[x]:
      continue
    distance += d
    tree[x] = 1
    for edge in edges[x]:
      heappush(current_edges, edge)
  return distance  

def main():
  n = int(input())
  nodes = []
  for i in range(n):
    x, y = map(int, input().split(' '))
    nodes.append((i, x, y))
  ans = solve(n, nodes)
  print(ans)
  

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import heapq

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

x=sorted([(i,pts[i][0]) for i in range(n)],key=lambda x:x[1])
y=sorted([(i,pts[i][1]) for i in range(n)],key=lambda x:x[1])

invx=[0]*n
invy=[0]*n

for i in range(n):
    invx[x[i][0]]=i
    invy[y[i][0]]=i

q=[(0,0)]

visit=[0]*n
ans=0

while q:
    cnt,i=heapq.heappop(q)

    if visit[i]==1:
        continue

    visit[i]=1
    ans+=cnt

    xi=invx[i]
    yi=invy[i]

    for delta in [-1,1]:
        nx=xi+delta
        ny=yi+delta
        if 0<=nx<n and visit[x[nx][0]]==0:
            heapq.heappush(q,(abs(x[nx][1]-x[xi][1]),x[nx][0]))
        if 0<=ny<n and visit[y[ny][0]]==0:
            heapq.heappush(q,(abs(y[ny][1]-y[yi][1]),y[ny][0]))

print(ans)

Submission status: Accepted

Solution code:
import heapq

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

x=sorted([(i,pts[i][0]) for i in range(n)],key=lambda x:x[1])
y=sorted([(i,pts[i][1]) for i in range(n)],key=lambda x:x[1])

invx=[0]*n
invy=[0]*n

for i in range(n):
    cx,_=x[i]
    invx[cx]=i
    cy,_=y[i]
    invy[cy]=i

xi=invx[0]
yi=invy[0]

q=[(0,0)]


visit=[0]*n
ans=0

while q:
    cnt,i=heapq.heappop(q)

    if visit[i]==1:
        continue

    visit[i]=1
    ans+=cnt

    xi=invx[i]
    yi=invy[i]

    if xi>0 and visit[x[xi-1][0]]==0:
        heapq.heappush(q,(x[xi][1]-x[xi-1][1],x[xi-1][0]))
    if xi<n-1 and visit[x[xi+1][0]]==0:
        heapq.heappush(q,(x[xi+1][1]-x[xi][1],x[xi+1][0]))

    if yi>0 and visit[y[yi-1][0]]==0:
        heapq.heappush(q,(y[yi][1]-y[yi-1][1],y[yi-1][0]))
    if yi<n-1 and visit[y[yi+1][0]]==0:
        heapq.heappush(q,(y[yi+1][1]-y[yi][1],y[yi+1][0]))
    
print(ans)

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

N = int(input())
uf = UnionFind(N)
XY = [list(map(int,input().split()))+[i] for i in range(N)]

X = sorted(XY, key=lambda i:i[0])
Y = sorted(XY, key=lambda i:i[1])

side = [[] for _ in range(len(X)+len(Y)-2)]
j = 0
for i in range(N-1):
  side[j] += [X[i+1][0]-X[i][0],X[i][2],X[i+1][2]]
  side[j+1] += [Y[i+1][1]-Y[i][1],Y[i][2],Y[i+1][2]]
  j += 2

ans = 0
side.sort()

for i,j,k in side:
  if uf.same(j,k):
    continue
  uf.union(j,k)
  ans += i

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
town=[]
for i in range(n):
  x,y=map(int,input().split())
  town.append([x,y,i])

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

Y=sorted(town,key=lambda x:x[1])
es=[]
for i in range(1,n):
  es.append((min(abs(X[i][0]-X[i-1][0]),abs(X[i][1]-X[i-1][1])),X[i][2],X[i-1][2]))
  #es.append((min(abs(X[i][0]-X[i-1][0]),abs(X[i][1]-X[i-1][1])),X[i-1][2],X[i][2]))
  es.append((min(abs(Y[i][0]-Y[i-1][0]),abs(Y[i][1]-Y[i-1][1])),Y[i][2],Y[i-1][2]))
  #es.append((min(abs(Y[i][0]-Y[i-1][0]),abs(Y[i][1]-Y[i-1][1])),Y[i-1][2],Y[i][2]))
es.sort(key=lambda x:x[0])


#Union-Find木
#par[i]:iの親　deep[i]:iの深さ　size[i]:iの大きさ
par=[i for i in range(n)]
deep=[1]*n
size=[1]*n

#親を見つける
def find(x):
  if par[x]==x:
    return x
  else:
    return find(par[x])

#二つのグループを統合する
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if deep[x]<deep[y]:
    par[x]=y
    size[y]+=size[x]
  else:
    par[y]=x
    size[x]+=size[y]
    if deep[x]==deep[y]:
      deep[x]+=1

#xとyが同じグループに属するかどうか
def same(x,y):
  return find(x)==find(y)

#xが属するグループの要素数を返す
def group_count(x):
  return size[find(x)]
  
#クラスカル法
#esは重みで小さい順にsort済み
#es[i]:[重み、始点、終点]
def kruskal(n,es):
  ans=0
  for to in es:
    if not same(to[1],to[2]):
      ans+=to[0]
      unite(to[1],to[2])
  return ans

      
  
print(kruskal(n,es))

Submission status: Accepted

Solution code:
n=int(input())
town=[]
for i in range(n):
  x,y=map(int,input().split())
  town.append([x,y,i])

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

Y=sorted(town,key=lambda x:x[1])
es=[]
for i in range(1,n):
  es.append((min(abs(X[i][0]-X[i-1][0]),abs(X[i][1]-X[i-1][1])),X[i][2],X[i-1][2]))
  es.append((min(abs(X[i][0]-X[i-1][0]),abs(X[i][1]-X[i-1][1])),X[i-1][2],X[i][2]))
  es.append((min(abs(Y[i][0]-Y[i-1][0]),abs(Y[i][1]-Y[i-1][1])),Y[i][2],Y[i-1][2]))
  es.append((min(abs(Y[i][0]-Y[i-1][0]),abs(Y[i][1]-Y[i-1][1])),Y[i-1][2],Y[i][2]))
es.sort(key=lambda x:x[0])


#Union-Find木
#par[i]:iの親　deep[i]:iの深さ　size[i]:iの大きさ
par=[i for i in range(n)]
deep=[1]*n
size=[1]*n

#親を見つける
def find(x):
  if par[x]==x:
    return x
  else:
    return find(par[x])

#二つのグループを統合する
def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if deep[x]<deep[y]:
    par[x]=y
    size[y]+=size[x]
  else:
    par[y]=x
    size[x]+=size[y]
    if deep[x]==deep[y]:
      deep[x]+=1

#xとyが同じグループに属するかどうか
def same(x,y):
  return find(x)==find(y)

#xが属するグループの要素数を返す
def group_count(x):
  return size[find(x)]
  
#クラスカル法
#esは重みで小さい順にsort済み
#es[i]:[重み、始点、終点]
def kruskal(n,es):
  ans=0
  for to in es:
    if not same(to[1],to[2]):
      ans+=to[0]
      unite(to[1],to[2])
  return ans

      
  
print(kruskal(n,es))

Submission status: Accepted

Solution code:
from collections import defaultdict
import heapq

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

    def getParent(self):
        return [self.find(i) for i in range(N)]

    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 unite(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if (root_x == root_y):
            return
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x

        elif self.rank[root_y] > self.rank[root_x]:
            self.parent[root_x] = root_y

        else:
            self.parent[root_x] = root_y
            self.rank[root_y] += 1

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

    def memsInGroup(self, x):
        """
        O(N)かかります
        """
        root = self.find(x)
        return [i for i in range(N) if root == self.find(i)]

    def sizeOfGroup(self, x):
        return len(self.memsInGroup(x))

class Edge:

    def __init__(self, u, v, cost):
        self.u = u
        self.v = v
        self.cost = cost

N = int(input())
vertex = {}
for i in range(N):
    x, y = map(int, input().split())
    vertex[i] = (x, y)

sortX = sorted(vertex.items(), key=lambda x:x[1][0])
sortY = sorted(vertex.items(), key=lambda x:x[1][1])

edges = []

for i in range(N-1):
    v1 = sortX[i]
    v2 = sortX[i+1]
    edges.append(Edge(v1[0]-1, v2[0]-1, abs(v1[1][0] - v2[1][0])))

for i in range(N-1):
    v1 = sortY[i]
    v2 = sortY[i+1]
    edges.append( Edge(v1[0]-1, v2[0]-1, abs(v1[1][1] - v2[1][1]) ) )

edges.sort(key = lambda x: x.cost)
uf = UnionFind(N)

res = 0
for e in edges:
    if not uf.isSame(e.u, e.v):
        uf.unite(e.u, e.v)
        res += e.cost

print(res)

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())
XYi = []
for i in range(N):
    tmp = list(map(int,input().split()))
    XYi.append(tmp+[i])

edges = []
E = 0

XYi.sort(key=lambda x:x[0])
for i in range(N-1):
    A,B,ind1 = XYi[i]
    C,D,ind2 = XYi[i+1]
    edges.append((min(abs(A-C),abs(B-D)), ind1, ind2))
    E+=1

XYi.sort(key=lambda x:x[1])
for i in range(N-1):
    A,B,ind1 = XYi[i]
    C,D,ind2 = XYi[i+1]
    edges.append((min(abs(A-C),abs(B-D)), ind1, ind2))
    E+=1

edges.sort()
def kruskal(n, edges):#edges: wでソート済み
    U = UnionFind(n)
    res = 0
    for e in edges:
        w, s, t = e
        if not U.same(s, t):
            res+=w
            U.union(s, t)
    return res
print(kruskal(N, edges))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    x, y = [], []
    for i in range(n):
        xi, yi = map(int, input().split())
        x.append((xi, i))
        y.append((yi, i))

    x.sort()
    y.sort()

    # x[x_ind[i]][1] = i
    x_ind = [0] * n
    y_ind = [0] * n
    for i in range(n):
        x_ind[x[i][1]] = i
        y_ind[y[i][1]] = i

    from heapq import heapify, heappush, heappop

    ans = 0
    seen = [True] * n
    heap = [(0, 0)]
    heapify(heap)
    while len(heap) > 0:
        cost, city = heappop(heap)

        if seen[city]:
            ans += cost
            seen[city] = False

            xi = x_ind[city]
            if xi > 0 and seen[x[xi-1][1]]:
                heappush(heap, (x[xi][0] - x[xi-1][0], x[xi-1][1]))
            if xi < n-1 and seen[x[xi+1][1]]:
                heappush(heap, (x[xi+1][0] - x[xi][0], x[xi+1][1]))
            yi = y_ind[city]
            if yi > 0 and seen[y[yi-1][1]]:
                heappush(heap, (y[yi][0] - y[yi-1][0], y[yi-1][1]))
            if yi < n-1 and seen[y[yi+1][1]]:
                heappush(heap, (y[yi+1][0] - y[yi][0], y[yi+1][1]))
    
    print(ans)

main()

Submission status: Accepted

Solution code:
N=int(input())
A=[]
for i in range(N):
  x,y=map(int,input().split())
  A.append((x,y,i))
A=sorted(A)
B=sorted(A,reverse=False, key=lambda x: x[1]) 
#print(A,B)
E=[[]for i in range(N)]
for i in range(N-1):
  x1,x2=A[i][2],A[i+1][2]
  y1,y2=B[i][2],B[i+1][2]
  E[x1].append((x2,A[i+1][0]-A[i][0]))
  E[x2].append((x1,A[i+1][0]-A[i][0]))
  E[y1].append((y2,B[i+1][1]-B[i][1]))
  E[y2].append((y1,B[i+1][1]-B[i][1]))
G=E
# G[v] = [w, ...]
#     グラフG上で頂点vが隣接する辺集合

from heapq import heappush, heappop, heapify
used = [0]*N
que = [(c, w) for w, c 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 w,c in G[v]:
        if used[w]:
            continue
        heappush(que,(c,w))
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=[]
for i in range(N):
  x,y=map(int,input().split())
  A.append((x,y,i))
A=sorted(A)
B=sorted(A,reverse=False, key=lambda x: x[1]) 
#print(A,B)
E=[]
for i in range(N-1):
  E.append(((A[i+1][0]-A[i][0]),A[i][2],A[i+1][2]))
  E.append(((B[i+1][1]-B[i][1]),B[i][2],B[i+1][2]))
edge=E

def kruskal():
    cost=0
    edge.sort()
    for c,u,v in edge:
        if same(u,v):
            continue
        union(u,v)
        cost+=c
    return cost

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    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)
par=[-1]*N
print(kruskal())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
XYI = [tuple(map(int,input().split() + [i])) for i in range(N)]
sx = sorted(XYI, key=lambda x:x[0])
sy = sorted(XYI, key=lambda x:x[1])

es = []
for (x0,_,i0),(x1,_,i1) in zip(sx,sx[1:]):
    es.append((x1-x0, i0, i1))
for (_,y0,i0),(_,y1,i1) in zip(sy,sy[1:]):
    es.append((y1-y0, i0, i1))
es.sort(key=lambda x:x[0])

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]
uf = UnionFind(N)

ans = 0
for d,a,b in es:
    if uf.is_same(a,b): continue
    uf.unite(a,b)
    ans += d
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
X = []
Y = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((x, y, i))
    Y.append((y, x, i))
X.sort()
Y.sort()
Edges = list([] for _ in range(N))
for k in range(N-1):
    xk, yk, ik = X[k]
    xk_, yk_, ik_ = X[k+1]
    Edges[ik].append((ik_, min(abs(xk-xk_), abs(yk-yk_))))
    Edges[ik_].append((ik, min(abs(xk-xk_), abs(yk-yk_))))
    yk, xk, ik = Y[k]
    yk_, xk_, ik_ = Y[k+1]
    Edges[ik].append((ik_, min(abs(xk-xk_), abs(yk-yk_))))
    Edges[ik_].append((ik, min(abs(xk-xk_), abs(yk-yk_))))
    
import heapq
def prim(Edges, V):
    mst = []
    included = [False]*V
    heap = []
    included[0] = True
    for v, d in Edges[0]:
        heapq.heappush(heap, (d, 0, v)) #(dist, pre_v, cur_v)
    while heap:
        d, pre_v, cur_v = heapq.heappop(heap)
        if included[cur_v]:
            continue
        included[cur_v] = True
        mst.append((pre_v, cur_v, d))
        for next_v, dist in Edges[cur_v]:
            if not included[next_v]:
                heapq.heappush(heap, (dist, cur_v, next_v))
    return mst

mst = prim(Edges, N)
ans = 0
for v1, v2, d in mst:
    ans += d
    
print(ans)

Submission status: Accepted

Solution code:
# ABC 065 D Built?
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    def find_root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]
        
    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
                
    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]


N=int(input())
towns=[]
for i in range(N):
    x,y=map(int,input().split())
    towns.append((x,y,i))
    
path=[]
A=sorted(towns,key=lambda x:x[0])
for i in range(N-1):
    path.append((A[i][2],A[i+1][2],min(abs(A[i][0]-A[i+1][0]),abs(A[i][1]-A[i+1][1]))))
A=sorted(towns,key=lambda x:x[1])
for i in range(N-1):
    path.append((A[i][2],A[i+1][2],min(abs(A[i][0]-A[i+1][0]),abs(A[i][1]-A[i+1][1]))))

path.sort(key=lambda x:x[2], reverse=True)
uf=UnionFind(N)
res=0
path_num=0
while 1:
    i,j,c=path.pop()
    if not uf.is_same_group(i,j):
        uf.unite(i,j)
        path_num+=1
        res+=c
    if path_num==N-1:
        break
print(res)

Submission status: Accepted

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

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

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.parent[x] = y

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

N = int(input())
X = []
Y = []
for i in range(N):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    X.append((x, y, i))
    Y.append((y, x, i))
X.sort()
Y.sort()
G = []
for i in range(1, N):
    d = abs(X[i][0]-X[i-1][0])
    a, b = X[i][2], X[i-1][2]
    G.append((d, a, b))
    d = abs(Y[i][0]-Y[i-1][0])
    a, b = Y[i][2], Y[i-1][2]
    G.append((d, a, b))
G.sort()
un = UnionFind(N)
ans = 0
for d, a, b in G:
    if not un.same(a, b):
        un.unite(a, b)
        ans += d
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0]*size
    def find(self, x):
        if self.parent[x] == x:
            return x
        # path compression
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        # union by rank
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same(self, x, y):
        return self.find(x) == self.find(y)

if __name__ == "__main__":
    N = int(input())
    vs = []
    for i in range(N):
        x,y = map(int,input().split())
        vs.append((x,y,i))
    vs.sort()
    edges = []
    for k in range(1, N):
        x,y,i = vs[k]
        a,b,j = vs[k-1]
        edges.append((i, j, min(abs(x-a),abs(y-b))))
    vs.sort(key=lambda x:x[1])
    for k in range(1, N):
        x,y,i = vs[k]
        a,b,j = vs[k-1]
        edges.append((i, j, min(abs(x-a),abs(y-b))))
    uf = UnionFind(N)
    edges.sort(key=lambda x:x[2])
    ans = 0
    for i,j,w in edges:
        if not uf.same(i,j):
            uf.unite(i,j)
            ans += w
    print(ans)

Submission status: Accepted

Solution code:
class Union():
    def __init__(self, n):
        self.para = [-1] * n
    
    def find(self, n):
        if self.para[n] < 0:
            return n
        
        else:
            self.para[n] = self.find(self.para[n])
            return self.para[n]
    
    def union(self, n, m):
        n = self.find(n)
        m = self.find(m)
        if n == m:
            return False
        else:
            if self.para[n] > self.para[m]:
                n, m = m, n
            
            self.para[n] += self.para[m]
            self.para[m] = n
    
    def same(self, n, m):
        return self.find(n) == self.find(m)

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()
ALL = []
for i in range(len(X)-1):
    ALL.append((X[i+1][0]-X[i][0], X[i][1], X[i+1][1]))
    ALL.append((Y[i+1][0]-Y[i][0], Y[i][1], Y[i+1][1]))
ALL.sort()
ut = Union(N)
cnt = 0
for a in ALL:
    n = a[1]
    m = a[2]
    if not ut.same(n,m):
        ut.union(n,m)
        cnt += a[0]
print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
xy=[]
for i in range(n):
  xy.append(list(map(int,input().split()))+[i])
  
x_sort=sorted(xy,key=lambda x:x[0])
y_sort=sorted(xy,key=lambda x:x[1])
edge=[]
for i in range(1,n):
  edge.append([min(abs(x_sort[i][1]-x_sort[i-1][1]),abs(x_sort[i][0]-x_sort[i-1][0])),x_sort[i][2],x_sort[i-1][2]])
  edge.append([min(abs(y_sort[i][1]-y_sort[i-1][1]),abs(y_sort[i][0]-y_sort[i-1][0])),y_sort[i][2],y_sort[i-1][2]])
edge.sort(key=lambda x:x[0])


#Union-Find
par=[i for i in range(n)]
deep=[1 for i in range(n)]
size=[1 for i in range(n)]
def find(x):
  if par[x]==x:
    return x
  else:
    return find(par[x])

def unite(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return
  if deep[x]<deep[y]:
    par[x]=y
    size[y]+=size[x]
  else:
    par[y]=x
    size[x]+=size[y]
    if deep[x]==deep[y]:
      deep[x]+=1

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

#クラスカル法
#n:頂点数　edge:重みでsortした辺のリスト
def kruskal(n,edge):
  res=0
  #w:重さ s:始点　t:終点
  for w,s,t in edge:
    if not same(s,t):
      unite(s,t)
      res+=w
  return res

#連結でコストが最小になるものを求める
#最小全域木

print(kruskal(n,edge))

Submission status: Accepted

Solution code:
#最小全域技問題(UnionFindと貪欲の合わせ技)
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

class UnionFindPathCompression():
    def __init__(self, n):
        self.parents = list(range(n))
        self.rank = [1]*n
        self.size = [1]*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 union(self, x, y):
        px = self.find(x)
        py = self.find(y)

        if px == py:
            return
        else:
            if self.rank[px] < self.rank[py]:
                self.parents[px] = py
                self.size[py] += self.size[px]
            else:
                self.parents[py] = px
                self.size[px] += self.size[py]
                #ランクの更新
                if self.rank[px] == self.rank[py]:
                    self.rank[px] += 1

N = int(input())
town = [[i]+list(map(int,input().split())) for i in range(N)]
root = []
#x軸の小さい順
town = sorted(town, key=lambda x: x[1])
for i in range(1,N):
    px,nx = town[i-1][1], town[i][1]
    root.append([town[i-1][0], town[i][0], nx-px])
#y軸の小さい順
town = sorted(town, key=lambda x: x[2])
for i in range(1,N):
    py,ny = town[i-1][2], town[i][2]
    root.append([town[i-1][0], town[i][0], ny-py])
#コストの少ない順
root = sorted(root, key=lambda x: x[2])
ufpc = UnionFindPathCompression(N)
ans = 0
for pp,np,cost in root:
    if ufpc.find(pp) != ufpc.find(np):
        ufpc.union(pp,np)
        ans += cost
        #print(pp,np,cost,ans)
print(ans)