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 -*-
import sys
from heapq import heappush,heappop,heapify

N=int(sys.stdin.readline().strip())
V=[]    #頂点の集合 (x座標、y座標、頂点番号)
for v in range(N):   #v:頂点番号
    x,y=tuple(map(int, sys.stdin.readline().split()))
    V.append((x,y,v+1))

#頂点をy軸でソート
V.sort(key=lambda x:(x[0]) )
E=[]    #辺の集合 (辺の長さ、頂点番号、頂点番号)
for i in range(N-1):
    fro_x,fro=V[i][0],V[i][2]
    to_x,to=V[i+1][0],V[i+1][2]
    E.append( (abs(fro_x-to_x),fro,to))

#頂点をx軸でソート
V.sort(key=lambda x:(x[1]) )
for i in range(N-1):
    fro_y,fro=V[i][1],V[i][2]
    to_y,to=V[i+1][1],V[i+1][2]
    E.append( (abs(fro_y-to_y),fro,to))

#辺の集合を辺の長さで昇順ソート
E.sort(key=lambda x:(x[0]) )

al=[[] for _ in range(N+1)]

for cost,fro,to in E:
    al[fro].append((cost,to))
    al[to].append((cost,fro))


#確定した頂点のリスト
fixed_v=[ 0 for _ in range(N+1) ]
hq=[]   #最短の辺を取得するためのヒープキュー
V=[1]   #次に処理する頂点が常に1つだけ入る、頂点1が常にスタート地点

ans=0
while V:
    cur=V.pop()
    #確定した頂点の更新
    fixed_v[cur]=1
    #頂点curから出て行く辺を全てhqに入れる
    for cost,to in al[cur]:
        heappush(hq,(cost,to))
    while hq:
        #hqから辺を取り出す
        cost,to=heappop(hq)
        #未確定の頂点が見つかれば、次に見る頂点としてVにappendし、whileループはbreak
        if fixed_v[to]==0:
            ans+=cost
            V.append(to)
            break
        #確定済みの頂点の場合は、#未確定の頂点が見つかるまでheapqからpopする

print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N=int(sys.stdin.readline().strip())
V=[]    #頂点の集合 (x座標、y座標、頂点番号)
for v in range(N):   #v:頂点番号
    x,y=tuple(map(int, sys.stdin.readline().split()))
    V.append((x,y,v+1))

#頂点をy軸でソート
V.sort(key=lambda x:(x[0]) )
E=[]    #辺の集合 (辺の長さ、頂点番号、頂点番号)
for i in range(N-1):
    fro_x,fro=V[i][0],V[i][2]
    to_x,to=V[i+1][0],V[i+1][2]
    E.append( (abs(fro_x-to_x),fro,to))

#頂点をx軸でソート
V.sort(key=lambda x:(x[1]) )
for i in range(N-1):
    fro_y,fro=V[i][1],V[i][2]
    to_y,to=V[i+1][1],V[i+1][2]
    E.append( (abs(fro_y-to_y),fro,to))

#辺の集合を辺の長さで昇順ソート
E.sort(key=lambda x:(x[0]) )


par=[ i for i in range(N+1) ]
size=[ 1 for i in range(N+1) ]

#Union Find
def root(x):
    while par[x]!=x:
        x=par[x]
    return x

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

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y: return
    if size[y]<size[x]: x,y=y,x  #yの要素数を大きくする
    size[y]+=size[x]
    par[x]=y #yが親ノード

def getsize(x):
	return size[root(x)]

ans=0
for cost,v1,v2 in E:
    if same(v1,v2) is False:
        ans+=cost
        unite(v1,v2)

print ans

Submission status: Accepted

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

import sys
input = sys.stdin.readline

from heapq import heapify, heappop, heappush

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()
dx = [];dy =[]
for i in range(N-1):
  tx = X[i+1][0]-X[i][0]
  dx.append((tx,(X[i+1][1],X[i][1])))
  ty = Y[i+1][0]-Y[i][0]
  dy.append((ty,(Y[i+1][1],Y[i][1])))
heapify(dx);heapify(dy)
#print(dx,dy)
visited = set([])
ans = 0
uf = UnionFind(N)
while uf.get_size(0) < N:
  if not dy or dx[0] <= dy[0]:
    cost, loc = heappop(dx)
  else:
    cost, loc = heappop(dy)
  if uf.is_same(loc[0],loc[1]): #すでに接続済みのところはスキップ
    continue
  ans += cost
  #print(cost)
  uf.union(loc[0],loc[1])
print(ans)

Submission status: Accepted

Solution code:
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):
    '''
    xの根を求める
    '''
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def union(x, y):
    '''
    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):
    '''
    xとyが同じ集合に属するかを判定する
    '''
    return find(x) == find(y)


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

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

par = [-1] * n
print(kruskal())

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()


def main():
    """
    （考察を述べてなかったので再提出）
    道を全部張った後に最小全域木を求めれば良いー＞プリム
    ただしそのまま実装すると辺の数が|E|=N^2になり、かつ
    プリムの計算量はO(|E|log|E|)なのでTLEする。

    そこで必要になりそうな辺のみに間引くことを考える。
    可能性のある辺はx座標またはy座標が隣り合うものなので、
    そのような辺のみを格納する。
    """
    N = int(input())
    city_x = defaultdict(list)
    city_y = defaultdict(list)
    indexes_x = set()
    indexes_y = set()
    for v in range(N):
        x, y = map(int, input().split())
        city_x[x].append(v)
        city_y[y].append(v)
        indexes_x.add(x)
        indexes_y.add(y)
    indexes_x = list(indexes_x)
    indexes_y = list(indexes_y)
    indexes_x.sort()
    indexes_y.sort()

    # 必要な道のみに間引く
    repn = [[] for _ in range(N)]
    pre_x = -1
    for x in indexes_x:
        pre_v = city_x[x][0]
        for i, v in enumerate(city_x[x]):
            if i == 0: continue
            repn[v].append((0, pre_v))
            repn[pre_v].append((0, v))
            pre_v = v
        if pre_x != -1:
            repn[city_x[pre_x][0]].append((x - pre_x, pre_v))
            repn[pre_v].append((x - pre_x, city_x[pre_x][0]))
        pre_x = x
    pre_y = -1
    for y in indexes_y:
        pre_v = city_y[y][0]
        for i, v in enumerate(city_y[y]):
            if i == 0: continue
            repn[v].append((0, pre_v))
            repn[pre_v].append((0, v))
            pre_v = v
        if pre_y != -1:
            repn[city_y[pre_y][0]].append((y - pre_y, pre_v))
            repn[pre_v].append((y - pre_y, city_y[pre_y][0]))
        pre_y = y
    # for i in range(N): print(repn[i])

    # プリム
    unvisited = set([i for i in range(1, N)])
    ans = 0
    q = []
    for cost, v in repn[0]: heappush(q, (cost, v))
    while q:
        cost, v = heappop(q)
        if v not in unvisited: continue
        ans += cost
        unvisited.remove(v)
        if not unvisited: break
        for next_cost, u in repn[v]:
            if u not in unvisited: continue
            heappush(q, (next_cost, u))
    print(ans)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()


def main():
    """
    道を全部張った後に最小全域木を求めれば良いー＞プリム
    """
    N = int(input())
    city_x = defaultdict(list)
    city_y = defaultdict(list)
    indexes_x = set()
    indexes_y = set()
    for v in range(N):
        x, y = map(int, input().split())
        city_x[x].append(v)
        city_y[y].append(v)
        indexes_x.add(x)
        indexes_y.add(y)
    indexes_x = list(indexes_x)
    indexes_y = list(indexes_y)
    indexes_x.sort()
    indexes_y.sort()

    # 必要な道のみに間引く
    repn = [[] for _ in range(N)]
    pre_x = -1
    for x in indexes_x:
        pre_v = city_x[x][0]
        for i, v in enumerate(city_x[x]):
            if i == 0: continue
            repn[v].append((0, pre_v))
            repn[pre_v].append((0, v))
            pre_v = v
        if pre_x != -1:
            repn[city_x[pre_x][0]].append((x - pre_x, pre_v))
            repn[pre_v].append((x - pre_x, city_x[pre_x][0]))
        pre_x = x
    pre_y = -1
    for y in indexes_y:
        pre_v = city_y[y][0]
        for i, v in enumerate(city_y[y]):
            if i == 0: continue
            repn[v].append((0, pre_v))
            repn[pre_v].append((0, v))
            pre_v = v
        if pre_y != -1:
            repn[city_y[pre_y][0]].append((y - pre_y, pre_v))
            repn[pre_v].append((y - pre_y, city_y[pre_y][0]))
        pre_y = y
    # for i in range(N): print(repn[i])

    # プリム
    unvisited = set([i for i in range(1, N)])
    ans = 0
    q = []
    for cost, v in repn[0]: heappush(q, (cost, v))
    while q:
        cost, v = heappop(q)
        if v not in unvisited: continue
        ans += cost
        unvisited.remove(v)
        if not unvisited: break
        for next_cost, u in repn[v]:
            if u not in unvisited: continue
            heappush(q, (next_cost, u))
    print(ans)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from operator import itemgetter

class UnionFind:  # 0-index
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n  # 親の番号 要素が根の場合は-(そのグループの要素数)を格納

    def find(self, x):  # 要素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が属するグループと要素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):  # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self, x, y):  # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def members(self, x):  # 要素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 {root: self.members(root) for root in self.roots()}

# ---------------------- #

def kruskal(n, edges):  # edges := [(u, v, weight), ...] weightでソート済み O(E)
    uf = UnionFind(n)
    ret = 0
    for u, v, w in edges:
        if not uf.same(u, v):
            ret += w
            uf.union(u, v)
    return ret

# ---------------------- #

n = int(input())
XY = []
for i in range(n):
    x, y = (int(x) for x in input().split())
    XY.append((i, x, y))

edges = []
XY.sort(key=itemgetter(1))
for (u, x1, _), (v, x2, _) in zip(XY, XY[1:]):
    edges.append((u, v, abs(x2 - x1)))

XY.sort(key=itemgetter(2))
for (u, _, y1), (v, _, y2) in zip(XY, XY[1:]):
    edges.append((u, v, abs(y2 - y1)))

edges.sort(key=itemgetter(2))
ans = kruskal(n, edges)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from heapq import heappop, heappush,heapify

icase=0
if icase==0:
    n=int(input())
    xy=[[0]*2 for i in range(n)]
    x=[0]*n
    y=[0]*n
    for i in range(n):
#        xy[i]=list(map(int,input().split()))
        x[i],y[i]=map(int,input().split())
elif icase==1:    
    n=3
#    xy=[[1, 5], [3, 9], [7, 8]]
    x=[1, 3, 7]
    y=[5, 9, 8]
elif icase==2:    
    n=6
#    xy=[[8, 3], [4, 9], [12, 19], [18, 1], [13, 5], [7, 6]]
    x=[8, 4, 12,18,13,7]
    y=[3, 9, 19, 1, 5, 6]

xi=[[0]*2 for i in range(n)]
yi=[[0]*2 for i in range(n)]
for i in range(n):
    xi[i]=[x[i],i]
    yi[i]=[y[i],i]
    
xi.sort()
x=xi
y=yi.sort()
y=yi

pair_lst = [i for i in range(n)]
que=[]
for i in range(n-1):
    wi=x[i+1][0]-x[i][0]
    heappush(que,(wi,x[i][1],x[i+1][1]))
    wi=y[i+1][0]-y[i][0]
    heappush(que,(wi,y[i][1],y[i+1][1]))

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

icnt=0
length_sum = 0
while que:
    w, s, t = heappop(que)
#    print(w,s,t)
    root_s = find(s)
    root_t = find(t)
    if root_s != root_t:
        pair_lst[root_s] = root_t
        length_sum += w
        icnt+=1
#        print(icnt)

print(length_sum)

Submission status: Accepted

Solution code:
from copy import deepcopy as copy
from operator import itemgetter

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [-1]*(n+1)#それぞれの要素がどの要素の子であるか

    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]#それぞれの要素の根を再帰的に求める

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        
        self.par[x] += self.par[y]
        self.par[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)#x,yが同じ集合に属するかどうか
    
    def size(self, x):
        return -self.par[self.find(x)]
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if root == self.find(i)]        

def main():
    n = int(input())
    bridge = [None]*n
    for i in range(n):
        bridge[i] = [int(x) for x in input().split()]+[i]

    judge = []

    bridge.sort()
    for i in range(n-1):
        judge.append((bridge[i+1][0]-bridge[i][0], bridge[i][2], bridge[i+1][2]))

    bridge.sort(key=itemgetter(1))
    for i in range(n-1):
        judge.append((bridge[i+1][1]-bridge[i][1], bridge[i][2], bridge[i+1][2]))
    
    judge.sort()
    union = UnionFind(n)
    count = 0
    cost = 0
    for k in range(2*n):
        c, i, j = judge[k]
        if union.same(i, j):
            continue
        union.union(i, j)
        cost += c
        count += 1
        if count == n-1:
            break
    
    print(cost)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFindTree():

    def __init__(self, n):
        #木全体の要素数
        self.n  = n
        #root[x]<0ならそのノードが根でありその値が木の要素数
        self.root = [-1] * (n+1)
        #ランク
        self.rank = [1] * (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.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

    def count_node(self,x):
        return -1 * self.root[self.find_root(x)]
from heapq import heapify, heappop

n = int(input())

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

sort_x = sorted(loc, key=lambda x:x[1])
sort_y = sorted(loc, key=lambda x:x[2])

diff = []

for i in range(n-1):
    diff.append((sort_x[i+1][1]-sort_x[i][1],sort_x[i][0],sort_x[i+1][0]))
    diff.append((sort_y[i+1][2]-sort_y[i][2],sort_y[i][0],sort_y[i+1][0]))

#最小のものから順番に並べる
heapify(diff)

uft = UnionFindTree(n)

ans = 0
while diff:
    w, s, t = heappop(diff)
    if not uft.is_same(s,t):
        uft.unite(s,t)
        ans += w

print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush
N, *A = map(int, open(0).read().split())
*A, = zip(*[iter(A)]*2)
A = [(x, y, i) for i, (x, y) in enumerate(A)]
A.sort()
G = []
x0, y0, i0 = A[0]
for x, y, i in A[1:]:
    c = min(abs(x-x0), abs(y-y0))
    heappush(G, (c, i0, i))
    x0, y0, i0 = x, y, i
A.sort(key=lambda x: x[1])
x0, y0, i0 = A[0]
for x, y, i in A[1:]:
    c = min(abs(x-x0), abs(y-y0))
    heappush(G, (c, i0, i))
    x0, y0, i0 = x, y, i


class UnionFind:
    def __init__(self, n=0):
        self.d = [-1]*n
        self.u = n

    def root(self, x):
        if self.d[x] < 0:
            return x
        self.d[x] = self.root(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if x > y:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        self.u -= 1
        return True

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

    def size(self, x):
        return -self.d[self.root(x)]

    def num_union(self):
        return self.u


ans = 0
u = UnionFind(N)
while u.num_union() > 1:
    c, a, b = heappop(G)
    if u.same(a, b):
        continue
    u.unite(a, b)
    ans += c

print(ans)

Submission status: Accepted

Solution code:
import sys
import pprint
sys.path.append('C:\\ARIHON')

# from Kraskal import compute_mst_kruskal
# import UnionFind
import array
import collections
from operator import itemgetter

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
 
Edge = collections.namedtuple("Edge", "start end weight")

def main():
    n = int(input())
    l = []
    for i in range(n):
        x,y = map(int,input().split())
        l.append((x,y,i))
    
    edges = []

    lxsort = sorted(l,key=itemgetter(0))
    for i in range(n-1):
        edges.append(Edge(lxsort[i][2],lxsort[i+1][2],lxsort[i+1][0]-lxsort[i][0]))
    
    lysort = sorted(l,key=itemgetter(1))
    for i in range(n-1):
        edges.append(Edge(lysort[i][2],lysort[i+1][2],lysort[i+1][1]-lysort[i][1]))
    
    mst = compute_mst_kruskal(n,edges)

    print(sum(edge.weight for edge in mst))
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)


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())
xy = [list(map(int, input().split()))+[i] for i in range(n)]
G = []

xy.sort()
for j in range(1, n):
    sx, sy, si = xy[j-1]
    tx, ty, ti = xy[j]
    G.append((min(abs(sx-tx), abs(sy-ty)), si, ti))

xy.sort(key=lambda x: x[1])
for j in range(1, n):
    sx, sy, si = xy[j-1]
    tx, ty, ti = xy[j]
    G.append((min(abs(sx-tx), abs(sy-ty)), si, ti))

uf = UnionFind(n)
ans = 0
G.sort()
for c, x, y in G:
    if uf.same(x, y):
        continue
    uf.union(x, y)
    ans += c
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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)


def main():
    N = int(readline())
    X = []
    Y = []

    for i in range(N):
        x, y = map(int, readline().split())
        X.append([x, i])
        Y.append([y, i])

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

    uf = UnionFind(N)
    ans = 0
    for s, t, w in L:
        if not uf.same(s, t):
            uf.union(s, t)
            ans += w
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc065/tasks/arc076_b

from heapq import heappush, heappop

class UnionFind(object):
    def __init__(self, n):
        self.n = n
        self.par = [-1] * n
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return False
        else:
            if self.par[x] > self.par[y]:
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x
            return True

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

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

    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.par) if x < 0]

    def group_count(self):
        return len(self.roots())

N = int(input())
X, Y = [], []
Loc = []
for n in range(N):
    xi, yi = map(int, input().split())
    X.append((xi, n))
    Y.append((yi, n))
    Loc.append((n, xi, yi))

# LocX = sorted(Loc, key=lambda x: x[1])
# LocY = sorted(Loc, key=lambda x: x[2])

# edges = set({})
# for i in range(1, N - 1):
#     es = [(LocX[i-1][0], LocX[i][0]), \
#           (LocX[i+1][0], LocX[i][0]), \
#           (LocY[i-1][0], LocY[i][0]), \
#           (LocY[i+1][0], LocY[i][0])]
#     for ii, jj in es:
#         if ii < jj:
#             edges.add((ii, jj))

# print(N)
# print(edges)
# pedges = [(min(abs(X[i] - X[j]), abs(Y[i] - Y[j])), i, j) for (i, j) in edges] 
# pedges.sort()
# print(pedges)

# uf = UnionFind(N)
# total = 0
# for (cost, i, j) in pedges:
#     if uf.unite(i, j):
#         total += cost
# print(total)


# Xでソートして隣接，Yでソートして隣接を辺とみなす
edges = []
X.sort()
Y.sort()
for i in range(N - 1):
    wxi = abs(X[i][0] - X[i + 1][0])
    wyi = abs(Y[i][0] - Y[i + 1][0])
    heappush(edges, (wxi, X[i][1], X[i + 1][1]))
    heappush(edges, (wyi, Y[i][1], Y[i + 1][1]))

# Kruskal
uf = UnionFind(N)
cost = 0
while len(edges) > 0:
    (w, u, v) = heappop(edges)
    if uf.unite(u, v):
        cost += w
print(cost)