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:
class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * N #parent[i] は(i+1)番目の要素が含まれる要素数の(-1)倍
    #要素が負-->その数を親とするグループに属する要素の数×(-1)
    #要素が正-->親のindex

    #Aがどのグループに属しているかを調べる
    def root(self, A):
        if self.parent[A-1] < 0: #負の数-->その数は親
            return A
        self.parent[A-1] = self.root(self.parent[A-1]) #負では無い時、親の場所が入っているから、親が属しているグループを、自分自身に入れる(一度確認したところは直接親を見れるようにする)
        return self.parent[A-1] #親の位置を返す

    #Aが含まれているグループに属している数を返す
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    #AとBをくっ付ける
    def connect(self, A, B):
        A = self.root(A) #Aを含むグループの親を返す
        B = self.root(B) #Bを含むグループの親を返す
        if A == B: #親が同じならなにもしない
            return False
        
        #大きい方(A)に小さい方(B)をつなぎたい
        if self.size(A) < self.size(B): #大小関係が逆の時は入れ替える
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] #大きい方に小さい方を加える　（負の数＋負の数 = 新しいグループに含まれる数×(-1)）
        self.parent[B-1] = A #加えられた親の値を、加えた先の親の位置に書き変える
        return True
    
    def same(self, A, B):
        if self.root(A) == self.root(B):
            return True
        else:
            return False

N = int(input())

lst = []
l_append = lst.append
for i in range(N):
    x, y = map(int, input().split())
    l_append([x, y, i])
# print (lst)
edge = []
e_append = edge.append
lst.sort(key = lambda x: x[0])
for i in range(1, N):
    e_append([lst[i-1][2], lst[i][2], min(abs(lst[i-1][0]-lst[i][0]), abs(lst[i-1][1]-lst[i][1]))])
# print (edge)
lst.sort(key = lambda x: x[1])
for i in range(1, N):
    e_append([lst[i-1][2], lst[i][2], min(abs(lst[i-1][0]-lst[i][0]), abs(lst[i-1][1]-lst[i][1]))])
# print (edge)
edge.sort(key = lambda x: x[2])

uni = UnionFind(N)
ans = 0
for i in edge:
    if not uni.same(i[0], i[1]): #違うグループのとき
        uni.connect(i[0], i[1])
        ans += i[2]
print (ans)

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * N #parent[i] は(i+1)番目の要素が含まれる要素数の(-1)倍
    #要素が負-->その数を親とするグループに属する要素の数×(-1)
    #要素が正-->親のindex

    #Aがどのグループに属しているかを調べる
    def root(self, A):
        if self.parent[A-1] < 0: #負の数-->その数は親
            return A
        self.parent[A-1] = self.root(self.parent[A-1]) #負では無い時、親の場所が入っているから、親が属しているグループを、自分自身に入れる(一度確認したところは直接親を見れるようにする)
        return self.parent[A-1] #親の位置を返す

    #Aが含まれているグループに属している数を返す
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    #AとBをくっ付ける
    def connect(self, A, B):
        A = self.root(A) #Aを含むグループの親を返す
        B = self.root(B) #Bを含むグループの親を返す
        if A == B: #親が同じならなにもしない
            return False
        
        #大きい方(A)に小さい方(B)をつなぎたい
        if self.size(A) < self.size(B): #大小関係が逆の時は入れ替える
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] #大きい方に小さい方を加える　（負の数＋負の数 = 新しいグループに含まれる数×(-1)）
        self.parent[B-1] = A #加えられた親の値を、加えた先の親の位置に書き変える
        return True
    
    def same(self, A, B):
        if self.root(A) == self.root(B):
            return True
        else:
            return False

N = int(input())

lst = []
for i in range(N):
    x, y = map(int, input().split())
    lst.append([x, y, i])
# print (lst)
edge = []
lst.sort(key = lambda x: x[0])
for i in range(1, N):
    edge.append([lst[i-1][2], lst[i][2], min(abs(lst[i-1][0]-lst[i][0]), abs(lst[i-1][1]-lst[i][1]))])
# print (edge)
lst.sort(key = lambda x: x[1])
for i in range(1, N):
    edge.append([lst[i-1][2], lst[i][2], min(abs(lst[i-1][0]-lst[i][0]), abs(lst[i-1][1]-lst[i][1]))])
# print (edge)
edge.sort(key = lambda x: x[2])

uni = UnionFind(N)
ans = 0
for i in edge:
    if not uni.same(i[0], i[1]): #違うグループのとき
        uni.connect(i[0], i[1])
        ans += i[2]
print (ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
pointx=[]
pointy=[]
for i in range(n):
    x,y=map(int,input().split())
    pointx.append((x,i))
    pointy.append((y,i))
pointx.sort()
pointy.sort()
G=[[] for i in range(n)]
for i in range(n-1):
    dx=abs(pointx[i+1][0]-pointx[i][0])
    G[pointx[i][1]].append((dx,pointx[i+1][1]))
    G[pointx[i+1][1]].append((dx,pointx[i][1]))
    dy=abs(pointy[i+1][0]-pointy[i][0])
    G[pointy[i][1]].append((dy,pointy[i+1][1]))
    G[pointy[i+1][1]].append((dy,pointy[i][1]))
import heapq
q=[]
check=[False]*n
INF=10**10
d=[INF]*n
ans=0
d[0]=0
heapq.heappush(q,(0,0))
while len(q)>0:
    now=heapq.heappop(q)
    if not check[now[1]]:
        ans+=now[0]
        check[now[1]]=True
        for i in G[now[1]]:
            if i[0]<d[i[1]]:
                d[i[1]]=i[0]
                heapq.heappush(q,i)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
towns = [tuple(map(int, input().split())) for _ in range(N)]

xs = []
ys = []

for i, (x,y) in enumerate(towns):
    xs.append((x, i))
    ys.append((y, i))

xs.sort()
ys.sort()

es = []
for (x1, i1), (x2, i2) in zip(xs, xs[1:]):
    es.append((x2-x1, i1, i2)) #i1からi2までのコストがx2-x1、絶対値とってないけど

for (y1, i1), (y2, i2) in zip(ys, ys[1:]):
    es.append((y2-y1, i1, i2)) #i1からi2までのコストがy2-y1、
es.sort()

class UnionFind:
    def __init__(self, N):
        #初めの親ノードはすべて異なる
        self.parent = [i for i in range(N)]
        #木の高さ
        self.rank = [0] * N
        self.count = 0

    #どのUnionに所属するか判定
    def root(self, a):
        #親が根の場合
        if self.parent[a] == a:
            return a
        else:
            #親の親を調べなおす＆見つかった根に接続しなおす
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]

    #同じUnionか判定
    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    #Unionを作る
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return
        #高いほうの下に小さいほうを繋ぐ
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count +=1


ans = 0
uf = UnionFind(N)
for d,a,b in es:
    #すでに繋がれてるならスキップ
    if uf.is_same(a,b):
        continue
    uf.unite(a,b) #esはソート済みのため短い順から重複をせずにN個の町が繋がれることが保証される
    ans += d
print(ans)

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

class UF(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):
    """
    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 のグループを結合
    """
    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):
    """
    x と y が同じグループか否か
    """
    return self.find(x) == self.find(y)

  def get_size(self, x):
    """
    x が属するグループの要素数
    """
    x = self.find(x)
    return self.size[x]

N = I()
x = []
y = []

for i in range(N):
  xtemp,ytemp = II()
  x.append([xtemp, i])
  y.append([ytemp, i])

xsort = sorted(x,lambda a:a[0])
ysort = sorted(y,lambda a:a[0])

graph = []
for i in range(N-1):
  graph.append([min(abs(xsort[i][0]-xsort[i+1][0]),abs(y[xsort[i][1]][0]-y[xsort[i+1][1]][0])), \
                xsort[i][1],xsort[i+1][1]])
  graph.append([min(abs(ysort[i][0]-ysort[i+1][0]),abs(x[ysort[i][1]][0]-x[ysort[i+1][1]][0])), \
                ysort[i][1],ysort[i+1][1]])

ans = 0
uf = UF(N)
graph.sort()
for w in graph:
  if not uf.is_same(w[1],w[2]):
    uf.union(w[1],w[2])
    ans += w[0]

print(ans)

Submission status: Accepted

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


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

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


def main():
    N = int(input())
    x_list = []
    y_list = []
    x_app = x_list.append
    y_app = y_list.append
    for i in range(N):
        x, y = map(int, input().split())
        x_app([x, i])
        y_app([y, i])

    x_list.sort()
    y_list.sort()
    adj = []
    adj_app = adj.append
    for i in range(N-1):
        adj_app([x_list[i + 1][0] - x_list[i][0], x_list[i + 1][1], x_list[i][1]])
        adj_app([y_list[i + 1][0] - y_list[i][0], y_list[i + 1][1], y_list[i][1]])

    adj.sort(key=lambda x: x[0])
    uf = UnionFind(N)
    ans = 0
    for edge in adj:
        if not uf.isSameGroup(edge[1], edge[2]):
            ans += edge[0]
            uf.unite(edge[1], edge[2])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

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

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

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

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


def main():
    N = int(input())
    x_list = []
    y_list = []
    x_app = x_list.append
    y_app = y_list.append
    for i in range(N):
        x, y = (int(x) for x in input().split())
        x_app([x, i])
        y_app([y, i])

    x_list.sort()
    y_list.sort()
    adj = []
    adj_app = adj.append
    for i in range(N-1):
        adj_app((x_list[i + 1][0] - x_list[i][0], x_list[i + 1][1], x_list[i][1]))
        adj_app((y_list[i + 1][0] - y_list[i][0], y_list[i + 1][1], y_list[i][1]))

    adj.sort(key=lambda x: x[0])
    uf = UnionFind(N)
    ans = 0
    for edge in adj:
        if not uf.same(edge[1], edge[2]):
            ans += edge[0]
            uf.unite(edge[1], edge[2])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 6199094

import sys
input = sys.stdin.readline

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

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

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

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

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

def main():
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app((xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app((yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))


    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(N)
    weight = 0

    for edge in edges:
        if not uf.same(edge[0], edge[1]):
            uf.unite(edge[0], edge[1])
            weight+=edge[2]
    print(weight)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 6199094

import array
import sys
input = sys.stdin.readline

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

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

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

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

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

def main():
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app((xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app((yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))


    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(N)
    weight = 0

    for edge in edges:
        if not uf.same(edge[0], edge[1]):
            uf.unite(edge[0], edge[1])
            weight+=edge[2]
    print(weight)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) #親ノード
        self.size = [1]*n #グループの要素数
 
    def root(self, x): #root(x): xの根ノードを返す．
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 
 
    def merge(self, x, y): #merge(x,y): xのいる組とyのいる組をまとめる
        x, y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: x,y=y,x #xの要素数が大きいように
        self.size[x] += self.size[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True
 
    def issame(self, x, y): #same(x,y): xとyが同じ組ならTrue
        return self.root(x) == self.root(y)
        
    def getsize(self,x): #size(x): xのいるグループの要素数を返す
        return self.size[self.root(x)]

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

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


Xyi = sorted(xyi)
xYi = sorted(xyi, key=lambda x: x[1])

from heapq import *

a = []

for j in range(n-1):
    x,y,i = Xyi[j]
    xx,yy,ii = Xyi[j+1]
    heappush(a,(xx-x,ii,i))
    x,y,i = xYi[j]
    xx,yy,ii = xYi[j+1]
    heappush(a,(yy-y,ii,i))

#print(a)

uf = UnionFind(n)
c = 1
ans = 0
while c < n:
    d,ii,i = heappop(a)
#    print(d,ii,i)
    if uf.merge(ii,i):
        c += 1
        ans += d
#        print(c,ans,ii,i)

print(ans)

Submission status: Accepted

Solution code:
def solve(query):
    q_x = sorted(query, key=lambda x: x[1])
    q_y = sorted(query, key=lambda x: x[2])

    g = set()

    for a, b in zip(q_x, q_x[1:]):
        s = a[0]
        t = b[0]
        w = min(abs(b[1]-a[1]), abs(b[2] - a[2]))
        g.add((w, s, t))

    for a, b in zip(q_y, q_y[1:]):
        s = a[0]
        t = b[0]
        w = min(abs(b[1]-a[1]), abs(b[2] - a[2]))
        g.add((w, s, t))

    _g = sorted(list(g))

    ans = 0
    for w, a, b in _g:
        if unite(a, b):
            ans += w
    return ans


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


def unite(x, y):
    rt_x = root(x)
    rt_y = root(y)
    if rt_x == rt_y:
        return False
    if rt_x < rt_y:
        par[rt_y] = rt_x
    else:
        par[rt_x] = rt_y

    return True


if __name__ == '__main__':
    n = int(input())
    query = []
    par = [i for i in range(n+1)]
    for i in range(n):
        a, b = map(int, input().split())
        query.append((i, a, b))

    print(solve(query))

Submission status: Accepted

Solution code:
from collections import defaultdict

import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline

parent_node = []

def get_parent(ind):
    global parent_node
    if ind != parent_node[ind]:
        parent_node[ind] = get_parent(parent_node[ind])
    return parent_node[ind]



def main():
    num = int(input())

    data = defaultdict(tuple)

    for i in range(num):
        x, y = map(int, input().split())
        data[i] = (x, y)

    data_sort = sorted(data.items(), key=lambda x: x[1][0])
    data_x = [ele for ele, ele2 in data_sort]
    data_sort = sorted(data.items(), key=lambda x: x[1][1])
    data_y = [ele for ele, ele2 in data_sort]

    cost_data = [0 for i in range((num - 1) * 2)]
    for i in range(len(data_x) - 1):
        a, b = data_x[i], data_x[i + 1]
        cost = abs(data[a][0] - data[b][0])
        cost_data[i] = a, b, cost
    for i in range(len(data_y) - 1):
        a, b = data_y[i], data_y[i + 1]
        cost = abs(data[a][1] - data[b][1])
        cost_data[i + len(data_x) - 1] = a, b, cost

    cost_data.sort(key=lambda x: x[2])
    global parent_node
    parent_node = [i for i in range(num)]

    ans = 0
    for i in range(len(cost_data)):
        a, b, cost = cost_data[i]
        a_parent = get_parent(a)
        b_parent = get_parent(b)
        if a_parent != b_parent:
            ans += cost
            parent_node[min(a_parent, b_parent)] = max(a_parent, b_parent)

    print(ans)





if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

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

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

def main():
    N = int(input())
    xli = []
    yli = []
    x_app = xli.append
    y_app = yli.append


    for i in range(N):
        x,y = (int(x) for x in input().split())
        x_app([x-1,i])
        y_app([y-1,i])
    xli.sort()
    yli.sort()

    edges = []
    edges_app = edges.append
    for i in range(N-1):
        edges_app((xli[i][1],xli[i+1][1],xli[i+1][0]-xli[i][0]))
        edges_app((yli[i][1],yli[i+1][1],yli[i+1][0]-yli[i][0]))


    edges.sort(key=lambda edge: edge[2])
    uf = UnionFind(N)
    weight = 0

    for edge in edges:
        if not uf.same(edge[0], edge[1]):
            uf.unite(edge[0], edge[1])
            weight+=edge[2]
    print(weight)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.par = list(range(n))
        self.rank = [0] * 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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        elif self.rank[x] < self.rank[y]:
            x, y = y, x
        
        self.par[y] = x
                
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

def kruskal():
    edges.sort(key=lambda x: x[2])
    t = UnionFind(N)
    ret = 0
    
    for u, v, c in edges:
        if not t.is_same(u, v):
            t.unite(u, v)
            ret += c
            
    return ret

edges = []

for k in range(1, 3):
    X.sort(key=lambda x: x[k])
    for i in range(N - 1):
        edges.append((X[i][0], X[i + 1][0], abs(X[i][k] - X[i + 1][k])))

print(kruskal())

Submission status: Accepted

Solution code:
import heapq

def prim(cost):
    V = len(cost)
    res = 0
    mincost = [float('inf')]*V
    used = [False]*V
    hq = []
    mincost[0] = 0
    heapq.heappush(hq,(0,0))
    while hq:
        weight,u = heapq.heappop(hq)
        if used[u]:
            continue
        used[u] = True
        res += weight
        mincost[u] = weight
        for v, v_cost in cost[u]:
            if not used[v]:
                heapq.heappush(hq,(v_cost,v))
    return res

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

xyi.sort()
cost = [[] for _ in range(N)]
for i in range(N-1):
    xj = xyi[i][0]
    j = xyi[i][2]
    xk = xyi[i+1][0]
    k = xyi[i+1][2]
    cost[j].append((k,xk-xj))
    cost[k].append((j,xk-xj))
xyi.sort(key=lambda x:x[1])
for i in range(N-1):
    yj = xyi[i][1]
    j = xyi[i][2]
    yk = xyi[i+1][1]
    k = xyi[i+1][2]
    cost[j].append((k,yk-yj))
    cost[k].append((j,yk-yj))

print(prim(cost))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.size_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.size_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        parent = self.root()
        return parent.group_id_

    def size(self):
        parent = self.root()
        return parent.size_

    def unite(self, unite_node):
        parent = self.root()
        unite_parent = unite_node.root()

        if parent.group_id_ != unite_parent.group_id_:
            if parent.size() > unite_parent.size():
                unite_parent.parent_ = parent
                parent.size_ = parent.size_ + unite_parent.size_
            else:
                parent.parent_ = unite_parent
                unite_parent.size_ = parent.size_ + unite_parent.size_
    def is_group(self,other):#selfとotherが同じグループに属するか
        return self.root()==other.root()

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()
G=[]
for i in range(N-1):
  G.append([X[i+1][0]-X[i][0],X[i][1],X[i+1][1]])
  G.append([Y[i+1][0]-Y[i][0],Y[i][1],Y[i+1][1]])
G.sort()
U=[UnionFindNode(i) for i in range(N)]
ans=0
for i in range(len(G)):
    c,a,b=G[i]
    if U[a].is_group(U[b]):
        continue
    U[a].unite(U[b])
    ans+=c
    if U[0].size()==N:
        print(ans)
        quit()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, x: "List[int]", y: "List[int]"):
    tmp = []
    for i in range(N):
        tmp.append([i, x[i], y[i]])
    tmp.sort(key=lambda x: x[1])
    dis = []
    for i in range(N - 1):
        dis.append([abs(tmp[i + 1][1] - tmp[i][1]), tmp[i][0], tmp[i + 1][0]])

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

    par = list(range(N))
    def find_root(x):
        if par[x] != x:
            par[x] = find_root(par[x])
        return par[x]
    def union(a, b):
        a_root = find_root(a)
        b_root = find_root(b)
        par[a_root] = b_root
        return

    dis.sort(key=lambda x: x[0])
    ret = 0
    for d in dis:
        a = d[1]
        b = d[2]
        if find_root(a) != find_root(b):
            ret += d[0]
            union(a, b)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]" 
    y = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)
 
    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        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
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
 
    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
        
n=int(input())
xlist=[]
ylist=[]
rlist=[]
checked=[-1]*n
for i in range(n):
  x,y=map(int,input().split())
  xlist.append([x,i])
  ylist.append([y,i])
xlist=sorted(xlist,key=lambda x:x[0])
ylist=sorted(ylist,key=lambda x:x[0])
for i in range(1,n):
  cost=xlist[i][0]-xlist[i-1][0]
  rlist.append([cost,xlist[i][1],xlist[i-1][1]])
  cost=ylist[i][0]-ylist[i-1][0]
  rlist.append([cost,ylist[i][1],ylist[i-1][1]])
rlist=sorted(rlist,key=lambda x:x[0])
cnt=0
cost=0
groupn=0
groupc=0
t=UnionFind(n)
for c,p1,p2 in rlist:
  if cnt==n and groupn-groupc==1:
    break
  if checked[p1]==-1 and checked[p2]==-1:
    checked[p1]=groupn
    checked[p2]=groupn
    cost+=c
    cnt+=2
    groupn+=1
    t.Unite(p1,p2)
  elif checked[p1]==-1:
    checked[p1]=checked[p2]
    cost+=c
    cnt+=1
    t.Unite(p1,p2)
  elif checked[p2]==-1:
    checked[p2]=checked[p1]
    cost+=c
    cnt+=1
    t.Unite(p1,p2)
  elif checked[p1]==checked[p2]:
    continue
  else:
    if t.isSameGroup(p1,p2):
      continue
    else:
      cost+=c
      groupc+=1
      t.Unite(p1,p2)
print(cost)

Submission status: Accepted

Solution code:
def main():
    import sys 
    input = sys.stdin.readline
    from heapq import heappop,heappush
    from operator import itemgetter
    
    def prim():
        used = [True]*n
        edgelist = []
        for e in edge[0]:
            heappush(edgelist,e)
        used[0] = False
        res = 0
        while len(edgelist) != 0:
            short_edge = heappop(edgelist)
            if not used[short_edge[1]]:
                continue
            v = short_edge[1]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heappush(edgelist,e)
            res += short_edge[0]
        return res

    n = int(input())
    A = [list(map(int,input().split()))+[i] for i in range(n)]
    A.append([-10**12,-10**12,-1])
    A.append([10**12,10**12,-1])
    X = sorted(A)
    Y = sorted(A,key = itemgetter(1))
    edge = [[] for i in range(n)]
    for i in range(1,n+1):
        sx = X[i-1][0]
        sy = Y[i-1][1]
        mx = X[i][0]
        my = Y[i][1]
        lx = X[i+1][0]
        ly = Y[i+1][1]
        nsx = X[i-1][2]
        nsy = Y[i-1][2]
        nmx = X[i][2]
        nmy = Y[i][2]
        nlx = X[i+1][2]
        nly = Y[i+1][2]
        edge[nsx].append((mx-sx,nmx))
        edge[nmx].append((mx-sx,nsx))
        edge[nlx].append((lx-mx,nmx))
        edge[nmx].append((lx-mx,nlx))
        edge[nsy].append((my-sy,nmy))
        edge[nmy].append((my-sy,nsy))
        edge[nly].append((ly-my,nmy))
        edge[nmy].append((ly-my,nly))

    print(prim()) 

if __name__ == '__main__':
    main()