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 sys
from collections import defaultdict
from heapq import heappop, heappush
from operator import itemgetter

readline = sys.stdin.readline

N = int(readline())
town = [None] * N
for i in range(N):
    x, y = map(int, readline().split())
    town[i] = (i, x, y)

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]

    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

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


def Kruskal(edges):
    edge = []
    total = 0

    uf = UnionFind(N)
    Q = sorted(edges, reverse=True)

    while len(edge) < N - 1 and Q:
        cost, e = Q.pop()
        if uf.find(e[0]) != uf.find(e[1]):
            total += cost
            edge.append(edge)
            uf.union(*e)
    return total


edges = []
for xy in [1, 2]:
    town = sorted(town, key=itemgetter(xy))
    for i in range(N - 1):
        t1, t2 = town[i], town[i + 1]
        d = t2[xy] - t1[xy]
        edges.append((d, (t1[0], t2[0])))
print(Kruskal(edges))

Submission status: Accepted

Solution code:
import heapq

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
ixy = [(i, x, y) for i, (x, y) in enumerate(xy)]

# Get edges with cost along both x, y
edges = [[] for i in range(n)]
for x_or_y in [1, 2]:
    xy_sorted = sorted(ixy, key = lambda a: a[x_or_y])
    for i in range(n-1):
        i1 = xy_sorted[i][0]
        i2 = xy_sorted[i+1][0]
        cost = xy_sorted[i+1][x_or_y] - xy_sorted[i][x_or_y]
        edges[i1].append((i2, cost))
        edges[i2].append((i1, cost))

# Calculate minimum Spanning tree (Prim algorithm)
distinct = [False]*n
ans = 0
pque = []
heapq.heappush(pque, (0, 0))
while len(pque) > 0:
    # print(pque)
    cost, v = heapq.heappop(pque)
    if distinct[v]: continue
    
    ans += cost
    distinct[v] = True

    for v_next, cost_next in edges[v]:
        if not distinct[v_next]:
            heapq.heappush(pque, (cost_next, v_next))

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
from heapq import heappush,heappop
N = int(input())
table=[]
for i in range(N):
    a,b = map(int,input().split())
    table.append([a,b,i])
A = sorted(table,key=itemgetter(0))
B = sorted(table,key=itemgetter(1))

graph=[]
for k in range(N):#距離、点
    graph.append((min(abs(A[k][0]-A[k-1][0]),abs( A[k][1]-A[k-1][1])),A[k][2],A[k-1][2]))
for k in range(N):
    graph.append((min(abs(B[k][0]-B[k-1][0]),abs( B[k][1]-B[k-1][1])),B[k][2],B[k-1][2]))

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

    def find(self,x):#親を探す 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,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return 
        if self.rank[px]<self.rank[py]:
            self.par[px]=py
        else:
            self.par[py]=px
        if self.rank[px]==self.rank[py]:
            self.rank[px] +=1
    
    def connect(self,x,y):#親が同じかみる
        return self.find(x)==self.find(y)
#クラスカル法
kei = Unionfindtree(N)
graph.sort()
dist =0
for d,i,j in graph:
    if not kei.connect(i,j):
        kei.union(i,j)
        dist +=d
print(dist)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Prim(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = list(set(V))

    used = set([])
    q = []
    heapq.heappush(q, (0, V[0]))

    ret = 0
    while q:
        c, v = heapq.heappop(q)

        if v in used:
            continue
        used.add(v)
        ret += c
        for u in g[v]:
            heapq.heappush(q, (g[v][u], u))
    return ret


@mt
def slv(N, XY):
    g = defaultdict(dict)
    V = [(i, x, y) for i, (x, y) in enumerate(XY)]
    V.sort(key=lambda x: x[1])
    for i in range(1, N):
        v = V[i][0]
        u = V[i-1][0]
        d = min(abs(XY[v][0] - XY[u][0]), abs(XY[v][1] - XY[u][1]))
        g[v][u] = d
        g[u][v] = d

    V.sort(key=lambda x: x[2])
    for i in range(1, N):
        v = V[i][0]
        u = V[i-1][0]
        d = min(abs(XY[v][0] - XY[u][0]), abs(XY[v][1] - XY[u][1]))
        g[v][u] = d
        g[u][v] = d

    return Prim(g)


def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]

    print(slv(N, XY))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

class UnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x:int, y:int) -> bool:
        if self.isSame(x,y):
            #print("x and y has already united")
            return False
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
                
        return True
                
    
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)
    
    
def kruskal(edges: list, node_num: int) -> int:
    edges.sort(key=lambda x:x[0])
    
    uf = UnionFind(node_num)
    rem = node_num-1
    ans = 0
    
    for cost, prev, nex in edges:
        if uf.find(prev) != uf.find(nex):
            uf.unite(prev, nex)
            ans += cost
            rem -= 1
            
        if rem == 0:
            break
        
    return ans


N = int(input().rstrip())

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


edges = []
for xy in [1,2]:
    town.sort(key=lambda x: x[xy])
    
    for i in range(N-1):
        edges.append(tuple([town[i+1][xy] - town[i][xy],town[i+1][0], town[i][0]]))
        
        
ans = kruskal(edges, N)
print(ans)

Submission status: Accepted

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

N = int(input().rstrip())

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


#1. x,y順にソートしてx→x+1, y→y+1の辺を追加する
edges = []
for xy in [1,2]:
    town.sort(key=lambda x: x[xy])
    
    for i in range(N-1):
        edges.append(tuple([town[i+1][xy] - town[i][xy],town[i+1][0], town[i][0]]))
        
#2. edgesをコスト順にソート
edges.sort(key=lambda x: x[0])

#3. N-1本の辺で全点がつながるまでuniteする
par = [i for i in range(N)]
rank = [0 for i in range(N)]

def find(x:int) -> int:
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
def unite(x:int, y:int) -> bool:
    # 同じ木に属しているならスルーする
    if find(x) == find(y):
        return False
    
    rootx = find(x)
    rooty = find(y)
    
    if rank[rootx] < rank[rooty]:
        par[rootx] = rooty
        
    else:
        par[rooty] = rootx
        if rank[rootx] == rank[rooty]:
            rank[rootx] += 1

    return True    
    
rem = N
ans = 0

for cost,nex,prev in edges:
    if find(nex) != find(prev):
        unite(nex,prev)
        ans += cost
        rem -= 1
        
    if rem == 1:
        break
    
print(ans)

Submission status: Accepted

Solution code:
#a = int(input())
#b,c = map(int,input().split())
#s = input()
#list_s = list(input())
#list_int = list(map(int,input().split()))

#list = [0 for i in range(n)]
#dp = [[0 for i in range(A)] for j in range(B)]

#list_int 並べて出力 print (' '.join(map(str,ans_li)))
#list_str 並べて出力 print (' '.join(list))

# 2進数 format(10, 'b') # '1010'

# aa=[int(input()) for i in range(n)]

#for i,name in enumerate(list)

''' 二次元配列を一列ずつ
for i in ans:
	print(*i)
'''
''' heapq
queue = []
heapq.heapify(queue) #heapqの作成
heapq.heappush(queue,num) #numのpush(値の追加)
pop = heapq.heappop(queue) #numのpop(最小値の出力)
pop = heapq.heappushpop(queue,num) #push -> pop

'''

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def Find(x):	#xの根を返す
	global table

	if table[x] == x:
		return x
	else:
		table[x] = Find(table[x])	#親の更新(根を直接親にして参照距離を短く)
		return table[x]

def Union(x,y):	#xとyを繋げる
	x = Find(x)
	y = Find(y)

	if x == y:
		return

	if rank[x] > rank[y]:
		table[y] = x
	else:
		table[x] = y
		if rank[x] == rank[y]:
			rank[y] += 1

def Check(x,y):
	if Find(x) == Find(y):
		return True
	else:
		return False



N = int(input())


#Union-Find
table = [i for i in range(N)]	#木の親 table[x] == x なら根
rank  = [1 for i in range(N)]	#木の長さ

# 優先度付きキューの作成
q = []
heapq.heapify(q)


xys = [list(map(int,input().split()))+[i] for i in range(N)]
xys.sort()
for i in range(N-1):
	xa,ya,a = xys[i]
	xb,yb,b = xys[i+1]
	heapq.heappush(q,[xb-xa,a,b])

xys.sort(key=lambda x:x[1])
for i in range(N-1):
	xa,ya,a = xys[i]
	xb,yb,b = xys[i+1]
	heapq.heappush(q,[yb-ya,a,b])

#総コスト
weight = 0


while q:
	w,a,b = heapq.heappop(q)

	if not Check(a,b):
		weight += w
		Union(a,b)

print(weight)

Submission status: Accepted

Solution code:
#クラスカル法を使った最小全域木の問題。2次元平面上という点に工夫の必要がある。
#全頂点と全頂点を結ぶパスを張ることが許されれば解決するがN<=10**5なので、TLE。
#簡単のために1次元上の頂点の場合を考える。
#この場合は頂点位置をソートして隣り合う頂点にパスを張れば充分と分かる。
#なぜならV0,V2=(V0,V1)+(V1,V2)なので改めて(V0,V2)を張る必要がない。
#さてここで、条件より2頂点間のパスは最終的にはx軸かy軸の1次平面上の距離となることを思い出す。
#つまり全頂点をx軸上の位置でソートしたもの、y軸上でソートしたものの2種類でそれぞれN-1個のパスがあれば充分と分かる。
#では、2*(N-1)個のパスに含まれる(N-1)個の「最短ではない」パスをどう扱えば良いか？
#少し考えれば、これは無視してそのままクラスカル法にかけても結果は変わらないと分かる。
#以上、パス構築O(N log N),クラスカル法O(2N log N)でおそらく間に合うはず。

from collections import defaultdict

#UnionFind
class UnionFind(object):
  def __init__(self,n):
    self.table=[-1]*n
 
  def find(self,x):
    parent=self.table[x]
    if parent<0:
      return x
    else:
      root=self.find(parent)
      self.table[x]=root
      return root
 
  def union(self,a,b):
    root1=self.find(a)
    root2=self.find(b)
    if root1 != root2:
      if self.table[root1] != self.table[root2]:
        if self.table[root1] < self.table[root2]:
          self.table[root2]=root1
        else:
          self.table[root1]=root2
      else:
        self.table[root1]+=(-1)
        self.table[root2]=root1

#入力読込
N=int(input())
Vx=[]
Vy=[]
for i in range(N):
  x,y=map(int,input().split())
  Vx.append([i,x])
  Vy.append([i,y])

E=[]
#x軸をベースにパスを作る準備
Vx=sorted(Vx, key=lambda x:x[1])
#y軸をベースにパスを作る準備
Vy=sorted(Vy, key=lambda x:x[1])

#パスを作る
for i in range(N-1):
  a,b=Vx[i]
  c,d=Vx[i+1]
  e,f=Vy[i]
  g,h=Vy[i+1]
  E.append((d-b,a,c))
  E.append((h-f,e,g))
  
#クラスカル法
E=sorted(E,key = lambda x:x[0])
UF=UnionFind(N)
ans=0
for a,b,c in E:
  if UF.find(b)!=UF.find(c):
    ans+=a
    UF.union(b,c)

print(ans)

Submission status: Accepted

Solution code:
import operator
import numpy as np
n = int(input())
xy = np.array([list(map(int, input().split())) for _ in range(n)])

sa1 = np.argsort(xy[:,0])
sa2 = np.argsort(xy[:,1])

s1 = xy[sa1,0]
s2 = xy[sa2,1]
c1 = s1[1:] - s1[:-1]
c2 = s2[1:] - s2[:-1]

c = [(c, (sa1[i], sa1[i+1])) for i, c in enumerate(c1)] + [(c, (sa2[i], sa2[i+1])) for i, c in enumerate(c2)]
c = sorted(c, key=operator.itemgetter(0))

total_cost = 0
sg = {}
for cost, verts in c:
    vf1 = sg.get(verts[0])
    vf2 = sg.get(verts[1])
    if vf1 and vf2:
        if vf1 is vf2: continue
        if len(vf1) < len(vf2): vf1, vf2 = vf2, vf1
        total_cost += cost
        vf1.update(vf2)
        for v in vf2: sg[v] = vf1
    else:
        total_cost += cost
        if vf1:
            vf1.add(verts[1])
            sg[verts[1]] = vf1
        elif vf2:
            vf2.add(verts[0])
            sg[verts[0]] = vf2
        else:
            sg[verts[0]] = sg[verts[1]] = set(verts)
print(total_cost)

Submission status: Accepted

Solution code:
from operator import itemgetter
from heapq import heappush,heappop
import sys
N = int(input())
table=[]
for i in range(N):
    a,b = map(int,input().split())
    table.append([a,b,i])
A = sorted(table,key=itemgetter(0))
B = sorted(table,key=itemgetter(1))

graph=[[] for i in range(N)]
for k in range(N-1):#距離、点
    graph[A[k][2]].append((abs(A[k][0]-A[k-1][0]),A[k-1][2]))
    graph[A[k][2]].append((abs(A[k][0]-A[k+1][0]),A[k+1][2]))
graph[A[N-1][2]].append((abs(A[N-1][0]-A[N-2][0]),A[N-2][2]))
for k in range(N-1):
    graph[B[k][2]].append((abs(B[k][1]-B[k-1][1]),B[k-1][2]))
    graph[B[k][2]].append((abs(B[k][1]-B[k+1][1]),B[k+1][2]))
graph[B[N-1][2]].append((abs(B[N-1][1]-B[N-2][1]),B[N-2][2]))
#プリム法
kei = []
visit=[False]*N
heappush(kei,[0,0])#距離,点
dist = 0
point =0
while kei:
    d,i = heappop(kei)
    if point ==N:
        print(dist)
        sys.exit()
    if visit[i]==True:
        continue
    visit[i]=True
    dist += d
    point+=1
    for e,j in graph[i]:
        if not visit[j]:
            heappush(kei,[e,j])

Submission status: Accepted

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

def Find(x):	#xの根を返す
	global table

	if table[x] == x:
		return x
	else:
		table[x] = Find(table[x])	#親の更新(根を直接親にして参照距離を短く)
		return table[x]

def Union(x,y):	#xとyを繋げる
	x = Find(x)	
	y = Find(y)
	
	if x == y:
		return
	
	if rank[x] > rank[y]:
		table[y] = x
	else:
		table[x] = y
		if rank[x] == rank[y]:
			rank[y] += 1

def Check(x,y):
	if Find(x) == Find(y):
		return True
	else:
		return False


		
#N:頂点数 E:辺数 
N = int(input())

#Union-Find
table = [i for i in range(N)]	#木の親 table[x] == x なら根	
rank  = [1 for i in range(N)]	#木の長さ

# 優先度付きキューの作成
q = []
heapq.heapify(q)


rout = []

for i in range(N):
	x,y = list(map(int,input().split()))
	rout.append([i,x,y])
	
# y順ソートルート
rout.sort(key=lambda x:x[2])
for i in range(N-1):	
	n1,x1,y1 = rout[i]
	n2,x2,y2 = rout[i+1]
	w = y2 - y1
	heapq.heappush(q,[w,n1,n2])


# x順ソートルート
rout.sort(key=lambda x:x[1])
for i in range(N-1):	
	n1,x1,y1 = rout[i]
	n2,x2,y2 = rout[i+1]
	w = x2 - x1
	heapq.heappush(q,[w,n1,n2])

	

#総コスト	
weight = 0


while q:
	w,a,b = heapq.heappop(q)
	
	if not Check(a,b):
		weight += w
		Union(a,b)
		
print(weight)

Submission status: Accepted

Solution code:
N = int(input())
xy = [[int(_) for _ in input().split()] for i in range(N)]

xsort_n = sorted(range(N), key=lambda n:xy[n][0])
ysort_n = sorted(range(N), key=lambda n:xy[n][1])

from collections import defaultdict

neighbors = defaultdict(list)

for i in range(N - 1):
    x1 = xsort_n[i]
    x2 = xsort_n[i+1]
    xd = xy[x2][0] - xy[x1][0]
    y1 = ysort_n[i]
    y2 = ysort_n[i+1]
    yd = xy[y2][1] - xy[y1][1]
    neighbors[x1].append((x2, xd))
    neighbors[x2].append((x1, xd))
    neighbors[y1].append((y2, yd))
    neighbors[y2].append((y1, yd))

from heapq import *

isused = [0] * N

h = []

heappush(h, (0, 0))

result = 0

while h:
    d, n = heappop(h)
    if isused[n]:
        continue
    result += d
    isused[n] = 1
    for ni, nd in neighbors[n]:
        if not isused[ni]:
            heappush(h, (nd, ni))
    
print(result)

Submission status: Accepted

Solution code:
N = int(input())
xy = [[int(_) for _ in input().split()] for i in range(N)]

xsort_n = sorted(range(N), key=lambda n:xy[n][0])
ysort_n = sorted(range(N), key=lambda n:xy[n][1])

from collections import defaultdict

neighbors = defaultdict(list)

for i in range(N - 1):
    x1 = xsort_n[i]
    x2 = xsort_n[i+1]
    y1 = ysort_n[i]
    y2 = ysort_n[i+1]
    neighbors[x1].append(x2)
    neighbors[x2].append(x1)
    neighbors[y1].append(y2)
    neighbors[y2].append(y1)

from heapq import *

isused = [0] * N

h = []

heappush(h, (0, 0))

result = 0

while h:
    d, n = heappop(h)
    if isused[n]:
        continue
    result += d
    isused[n] = 1
    for i in neighbors[n]:
        if not isused[i]:
            d1 = min(abs(xy[n][0] - xy[i][0]), abs(xy[n][1] - xy[i][1]))
            heappush(h, (d1, i))
    
print(result)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

N = int(input())
T = [[i] + list(map(int, input().split())) for i in range(N)]
E = [[] for i in range(N)]
E = []
T.sort(key=lambda x: x[1])
for i in range(N-1):
    s, l = T[i:i+2]
    E.append([s[0], l[0], l[1]-s[1]])
T.sort(key=lambda x: x[2])
for i in range(N-1):
    s, l = T[i:i+2]
    E.append([s[0], l[0], l[2]-s[2]])
E.sort(key=lambda x: x[2])

Par = list(range(N))
def root(x):
    if Par[x] == x:
        return x
    else:
        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 x != y:
        Par[x] = y

ans = 0
for e in E:
    if not same(e[0], e[1]):
        ans += e[2]
        unite(e[0], e[1])

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
par,rank = [i for i in range(n+1)],[0 for i in range(n+1)]
def root(x):
	if par[x]!=x: par[x] = root(par[x])
	return par[x]
def unite(x,y):
	x2,y2 = root(x),root(y)
	if x2!=y2:
		if rank[x2]<rank[y2]: par[x2] = y2
		else: par[y2] = x2
		if rank[x2]==rank[y2]: rank[x2]+=1
def same(x,y):
	return root(x)==root(y)
a,b = [],[]
for i in range(n):
	x,y = (int(_) for _ in input().split())
	a.append([x,i])
	b.append([y,i])
a,b,h,ans = sorted(a),sorted(b),[],0
from heapq import heappush,heappop
for i in range(n-1):
	heappush(h,(a[i+1][0]-a[i][0],a[i+1][1],a[i][1]))
	heappush(h,(b[i+1][0]-b[i][0],b[i+1][1],b[i][1]))
while h:
	i,j,k = heappop(h)
	if root(j)!=root(k):
		unite(j,k)
		ans += i
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
n = int(input())
x = []
y = []
for i in range(n):
    s = list(map(int, input().split()))
    x.append([s[0], i])
    y.append([s[1], i])

x.sort()
y.sort()

xdiff = []
ydiff = []
for i in range(1, n):
    xdiff.append([x[i][0] - x[i - 1][0], x[i - 1][1], x[i][1]])
    ydiff.append([y[i][0] - y[i - 1][0], y[i - 1][1], y[i][1]])

xdiff.sort()
ydiff.sort()

parent = [-1] * n

def getParent(index):
    if parent[index] == -1:
        return index
    else:
        parent[index] = getParent(parent[index])
        return parent[index]

count = 0
ans = 0
xIndex = 0
yIndex = 0
while count != n - 1:
    if xIndex != n - 1:
        xTemp = xdiff[xIndex]
    if yIndex != n - 1:
        yTemp = ydiff[yIndex]

    if yIndex == n - 1 or (xIndex != n - 1 and xTemp[0] < yTemp[0]):
        xIndex += 1
        temp = xTemp
    else:
        yIndex += 1
        temp = yTemp

    parent1 = getParent(temp[1])
    parent2 = getParent(temp[2])
    if parent1 == parent2:
        continue
    else:
        count += 1
        ans += temp[0]
        parent[parent1] = parent2

print(ans)

Submission status: Accepted

Solution code:
import sys
import collections
import itertools

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 are_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def grouper(self):
        import itertools
        import operator
        par = operator.itemgetter(1)
        for _, group in itertools.groupby(
                sorted(enumerate(self.par), key=par), par):
            yield [i for i, par in group]

def sliding_window(n, seq):
    import collections
    import itertools
    return zip(*(collections.deque(itertools.islice(it, i), 0) or it
               for i, it in enumerate(itertools.tee(seq, n))))

Edge = collections.namedtuple('Edge', ['s', 't', 'cost'])

N = int(sys.stdin.readline())
xys = [[i] + list(map(int, line.split())) for i, line in enumerate(sys.stdin)]
edges = []
for (i1, x1, _), (i2, x2, _) in sliding_window(2, sorted(xys, key=lambda t: t[1])):
    edges.append(Edge(i1, i2, abs(x1 - x2)))
for (i1, _, y1), (i2, _, y2) in sliding_window(2, sorted(xys, key=lambda t: t[2])):
    edges.append(Edge(i1, i2, abs(y1 - y2)))
edges = sorted(edges, key=lambda e: e.cost)
uf = UnionFind(N)
min_cost = 0
for edge in edges:
    if not uf.are_same(edge.s, edge.t):
        uf.union(edge.s, edge.t)
        min_cost += edge.cost
print(min_cost)

Submission status: Accepted

Solution code:
n = int(input())
z = []
for i in range(n):
    X, Y = map(int, input().split())
    z.append([X, Y, i])

x = sorted(z, key=lambda x: x[0])
y = sorted(z, key=lambda x: x[1])

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

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

# Union-Find  ---------------
parent = [i for i in range(n)]
rank = [0 for i in range(n)]

def find(x):
    if parent[x] == x:
        return x
    else:
        parent[x] = find(parent[x])
        return parent[x]

def judge(a, b):
    a_parent = find(a)
    b_parent = find(b)
    if a_parent == b_parent:
        return True
    else:
        return False

def merge(a, b):
    a_parent = find(a)
    b_parent = find(b)
    if a_parent == b_parent:
        return
    else:
        if rank[a_parent] > rank[b_parent]:
            parent[b_parent] = a_parent
        elif rank[a_parent] < rank[b_parent]:
            parent[a_parent] = b_parent
        else:
            parent[a_parent] = b_parent
            rank[b_parent] += 1
#----------------------------

from collections import deque
q = deque(new_list)

cost = 0
while len(q)>0:
    c = q.popleft()
    if not judge(c[1], c[2]):
        merge(c[1], c[2])
        cost += c[0]

print(cost)

Submission status: Accepted

Solution code:
n = int(input())
p = [list(map(int,input().split())) for _ in range(n)]

X = sorted([(i, xy[0]) for i, xy in enumerate(p)], key=lambda x: x[1])
Y = sorted([(i, xy[1]) for i, xy in enumerate(p)], key=lambda x: x[1])
dX = sorted([[X[i][0], X[i+1][0], X[i+1][1]-X[i][1]] for i in range(n-1)], key=lambda x: x[2])
dY = sorted([[Y[i][0], Y[i+1][0], Y[i+1][1]-Y[i][1]] for i in range(n-1)], key=lambda x: x[2])

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

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

parent = [i for i in range(n+1)]
depth = [1 for i in range(n+1)]

ans = 0
i, j = 0, 0
while i < n-1 and j < n-1:
    if dX[i][2] < dY[j][2]:
        a, b, d = dX[i]
        i += 1
    else:
        a, b, d = dY[j]
        j += 1
    ra, rb = map(root, [a,b])
    if ra != rb:
        if depth[ra] < depth[rb]:
            a, b = b, a
            ra, rb = rb, ra
        parent[rb] = ra
        depth[ra] = max(depth[ra], depth[rb]+1)
        ans += d
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
P = [[i, list(map(int, input().split()))] for i in range(N)]

X = sorted([[i, xy[0]] for i, xy in P], key=lambda x: x[1])
Y = sorted([[i, xy[1]] for i, xy in P], key=lambda y: y[1])

Xe = [[X[i][0], X[i+1][0], abs(X[i][1]-X[i+1][1])] for i in range(N-1)]
Ye = [[Y[i][0], Y[i+1][0], abs(Y[i][1]-Y[i+1][1])] for i in range(N-1)]
E = sorted(Xe + Ye, key=lambda e: e[2])


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

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def 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)
edge_cnt = 0
MST_cost = 0
i = 0

while edge_cnt < N-1:
    a, b, cost = E[i]
    if not uf.same_check(a, b):
        MST_cost += cost
        uf.union(a, b)
        edge_cnt += 1
    i += 1

print(MST_cost)

Submission status: Accepted

Solution code:
def d_Built(N, P):
    xs = []
    ys = []
    E = []  # 辺の情報を格納
    for i, (x, y) in enumerate(P):
        xs.append((x, i))
        ys.append((y, i))
    xs.sort()
    ys.sort()

    # 頂点をつなぐ辺の候補を得る
    x_edge = []
    y_edge = []
    for i in range(N - 1):
        # x座標、y座標でソートしたもので隣り合った2点を結ぶ
        x_edge.append((xs[i][1], xs[i + 1][1], xs[i + 1][0] - xs[i][0]))
        y_edge.append((ys[i][1], ys[i + 1][1], ys[i + 1][0] - ys[i][0]))
    x_edge.extend(y_edge)  # 頂点a,頂点b,それを結ぶ辺のコスト
    x_edge.sort(key=lambda x: x[2])  # コストの小さいものから並べる(クラスカル法のため)

    class UnionFind:
        def __init__(self, N):
            self.p = list(range(N))  # 初期状態ではi番の頂点の根(parent)はi番である
            self.rank = [0] * N  # 初期状態ではどの頂点もランクが0とする(何もつながってない)
            self.size = [1] * N  # 初期状態ではどの頂点も連結成分の大きさは1

        def find(self, x):
            # 頂点xが属する連結成分の代表(根の番号)を求める
            if self.p[x] != x:
                # 頂点xの根は他の頂点だった
                self.p[x] = self.find(self.p[x])  # 経路圧縮
            return self.p[x]

        def is_same(self, x, y):
            # 頂点x,yは同じ連結成分に属するか？
            return self.find(x) == self.find(y)

        def union(self, x, y):
            # x,yを同じ連結成分に属させる
            u = self.find(x)
            v = self.find(y)
            if u == v:
                # 同じ連結成分に既に属していた
                return
            if self.rank[u] < self.rank[v]:
                self.p[u] = v  # ランクの大きな方につなげる
                self.size[v] += self.size[u]  # つながっている要素数だけ足す
                self.size[u] = 0  # ランクが小さかった連結成分は「解散」
            else:
                # 上と同様にやる
                self.p[v] = u
                self.size[u] += self.size[v]
                self.size[v] = 0
                if self.rank[u] == self.rank[v]:
                    # 根の分だけ1個「ずれる」
                    self.rank[u] += 1

        def get_size(self, x):
            # 頂点xが属する連結成分の大きさ
            return self.size[self.find(x)]

        def show(self):
            return self.p

    uf = UnionFind(N)
    # クラスカル法を使う
    i = 0
    while len(E) != N - 1:
        x1, x2, cost = x_edge[i]
        if uf.find(x1) != uf.find(x2):
            # x1,x2が同じ木に属していた場合、注目している辺を追加するとループを作ってしまう
            uf.union(x1, x2)
            E.append(cost)
        i += 1
    return sum(E)
  
N = int(input())
P = [[int(i) for i in input().split()] for j in range(N)]
print(d_Built(N, P))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
N = int(input())
x, y = [0] * N, [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())

inds = range(N)
d = [[] for i in range(N)]
xxy = sorted(zip(x, y, inds))
for i in range(N-1):
    cur = xxy[i][2]
    nex = xxy[i+1][2]
    d[cur].append(((xxy[i+1][0] - xxy[i][0]), nex))
    d[nex].append(((xxy[i+1][0] - xxy[i][0]), cur))

yxy = sorted(zip(y, x, inds))
for i in range(N-1):
    cur = yxy[i][2]
    nex = yxy[i+1][2]
    d[cur].append(((yxy[i+1][0] - yxy[i][0]), nex))
    d[nex].append(((yxy[i+1][0] - yxy[i][0]), cur))

ans = 0
used = [False] * N
used[0] = True
q = []
for i in d[0]:
    heappush(q, i)
while len(q) > 0:
    v, x = heappop(q)
    if used[x]:
        continue
    used[x] = True
    ans += v
    for y in d[x]:
        if not used[y[1]]:
            heappush(q, y)

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
  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
    return False

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

ixy.sort(key=lambda x:x[1])
for j in range(N-1):
  costs += [(ixy[j][0], ixy[j+1][0], ixy[j+1][1]-ixy[j][1])]
  costs += [(ixy[j+1][0], ixy[j][0], ixy[j+1][1]-ixy[j][1])]
ixy.sort(key=lambda y:y[2])
for j in range(N-1):
  costs += [(ixy[j][0], ixy[j+1][0], ixy[j+1][2]-ixy[j][2])]
  costs += [(ixy[j+1][0], ixy[j][0], ixy[j+1][2]-ixy[j][2])]

costs.sort(key=lambda cost:cost[2])
ans = 0
roots = UnionFind(N)
for cost in costs:
  u, v, c = cost
  if roots.find(u)!=roots.find(v):
    roots.union(u, v)
    ans += c
    
print(ans)