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
input = sys.stdin.readline

# ユニオンファインド
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())
a= [list(map(int, input().split())) for i in range(n)]
b=[]
a.sort()
# aの各点に通し番号を振る
for i in range(n):
    a[i].append(i)

# 繋ぐ点の候補は上下左右の４つ
# 左右に繋ぐ辺を追加
for i in range(n-1):
    b.append([a[i][2], a[i + 1][2], a[i + 1][0] - a[i][0]])

a.sort(key=lambda x:x[1])
# 上下に繋ぐ辺を追加
for i in range(n-1):
    b.append([a[i][2], a[i + 1][2], a[i + 1][1] - a[i][1]])

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

uf=UnionFind(n)
ans=0
cnt=0
# クラスカル法
for x,y,z in b:
    if not uf.same(x,y):
        uf.union(x,y)
        cnt+=1
        ans+=z
        if cnt==n-1:
            break
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 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())
a= [list(map(int, input().split())) for i in range(n)]
b=[]
a.sort()
# aの各点に通し番号を振る
for i in range(n):
    a[i].append(i)

# 繋ぐ点の候補は上下左右の４つ
# 左右に繋ぐ辺を追加
for i in range(n-1):
    b.append([a[i][2], a[i + 1][2], a[i + 1][0] - a[i][0]])

a.sort(key=lambda x:x[1])
# 上下に繋ぐ辺を追加
for i in range(n-1):
    b.append([a[i][2], a[i + 1][2], a[i + 1][1] - a[i][1]])

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

uf=UnionFind(n)
ans=0
cnt=0
# クラスカル法
for x,y,z in b:
    if not uf.same(x,y):
        uf.union(x,y)
        cnt+=1
        ans+=z
        if cnt==n-1:
            break
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 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())
a= [list(map(int, input().split())) for i in range(n)]
b=[]
a.sort()
# aの各点に通し番号を振る
for i in range(n):
    a[i].append(i)

# 繋ぐ点の候補は上下左右の４つ
# 左右に繋ぐ辺を追加
for i in range(n):
    if i==0:
        b.append([a[i][2],a[i+1][2], a[i+1][0]-a[i][0]])
    elif i==n-1:
        b.append([a[i][2],a[i-1][2], a[i][0]-a[i-1][0]])
    else:
        b.append([a[i][2],a[i-1][2], a[i][0]-a[i-1][0]])
        b.append([a[i][2], a[i + 1][2], a[i + 1][0] - a[i][0]])

a.sort(key=lambda x:x[1])
# 上下に繋ぐ辺を追加
for i in range(n):
    if i==0:
        b.append([a[i][2],a[i+1][2], a[i+1][1]-a[i][1]])
    elif i==n-1:
        b.append([a[i][2],a[i-1][2], a[i][1]-a[i-1][1]])
    else:
        b.append([a[i][2],a[i-1][2], a[i][1]-a[i-1][1]])
        b.append([a[i][2], a[i + 1][2], a[i + 1][1] - a[i][1]])

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

uf=UnionFind(n)
ans=0
cnt=0
# クラスカル法
for x,y,z in b:
    if not uf.same(x,y):
        uf.union(x,y)
        cnt+=1
        ans+=z
        if cnt==n-1:
            break
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 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())
def main():
    n = int(input())
    uf = UnionFind(n)
    xs = [None]*n
    ys = [None]*n
    ps = [None]*n
    for i in range(n):
        x, y = map(int, input().split())
        ps[i] = [x, y]
        xs[i] = [x, i]
        ys[i] = [y, i]
    xs.sort()
    ys.sort()
    dist_xs = [None]*(n-1)
    dist_ys = [None]*(n-1)
    for i in range(n-1):
        dist_xs[i] = [xs[i+1][0] - xs[i][0], xs[i+1][1], xs[i][1]]
        dist_ys[i] = [ys[i+1][0] - ys[i][0], ys[i+1][1], ys[i][1]]
    dist_xs.sort()
    dist_ys.sort()
    x_i, y_i = 0, 0
    ans = 0
    while x_i < len(dist_xs) or y_i < len(dist_ys):
        if x_i < len(dist_xs) and y_i < len(dist_ys):
            if dist_xs[x_i][0] < dist_ys[y_i][0]:
                if not uf.same(dist_xs[x_i][1], dist_xs[x_i][2]):
                    uf.union(dist_xs[x_i][1], dist_xs[x_i][2])
                    ans += dist_xs[x_i][0]
                x_i += 1
            else:
                if not uf.same(dist_ys[y_i][1], dist_ys[y_i][2]):
                    uf.union(dist_ys[y_i][1], dist_ys[y_i][2])
                    ans += dist_ys[y_i][0]
                y_i += 1
        elif x_i < len(dist_xs):
            if not uf.same(dist_xs[x_i][1], dist_xs[x_i][2]):
                uf.union(dist_xs[x_i][1], dist_xs[x_i][2])
                ans += dist_xs[x_i][0]
            x_i += 1
        else:
            if not uf.same(dist_ys[y_i][1], dist_ys[y_i][2]):
                uf.union(dist_ys[y_i][1], dist_ys[y_i][2])
                ans += dist_ys[y_i][0]
            y_i += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

n=int(input())
xy=[0]*n
for i in range(n):
    x,y=map(int,input().split())
    xy[i]=[x,y,i]

def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

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

xy.sort()
edge = [[] for i in range(n)]
#隣接リスト edge[i]:[コスト,行先]
for i in range(n-1):
    x1,x2=xy[i][0],xy[i+1][0]
    n1,n2=xy[i][2],xy[i+1][2]
    edge[n1].append((x2-x1,n2))
    edge[n2].append((x2-x1,n1))

xy.sort(key=lambda x: x[1])
for i in range(n-1):
    x1,x2=xy[i][1],xy[i+1][1]
    n1,n2=xy[i][2],xy[i+1][2]
    edge[n1].append((x2-x1,n2))
    edge[n2].append((x2-x1,n1))

print(prim_heap())

Submission status: Accepted

Solution code:
import sys


class UnionFind():
    def __init__(self, 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


N = int(input())
Px = []
Py = []
for k, s in enumerate(sys.stdin.readlines()):
    x, y = map(int, s.split())
    Px.append((x, k))
    Py.append((y, k))

edge = []

Px.sort()
Py.sort()
for i in range(N - 1):
    x0, k0 = Px[i]
    x1, k1 = Px[i + 1]
    d = abs(x0 - x1)
    edge.append((d, k0, k1))

    y0, k0 = Py[i]
    y1, k1 = Py[i + 1]
    d = abs(y0 - y1)
    edge.append((d, k0, k1))

edge.sort()
uf = UnionFind(N)
cnt = 0
for d, k0, k1 in edge:
    if uf.find(k0) != uf.find(k1):
        uf.union(k0, k1)
        cnt += d

print(cnt)

Submission status: Accepted

Solution code:
import sys


class UnionFind():
    def __init__(self, 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


N = int(input())
Px = []
Py = []
for k, s in enumerate(sys.stdin.readlines()):
    x, y = map(int, s.split())
    Px.append((x, k))
    Py.append((y, k))

edge = []

Px.sort()
Py.sort()
for i in range(N - 1):
    x0, k0 = Px[i]
    x1, k1 = Px[i + 1]
    d = abs(x0 - x1)
    edge.append((d, k0, k1))

    y0, k0 = Py[i]
    y1, k1 = Py[i + 1]
    d = abs(y0 - y1)
    edge.append((d, k0, k1))

edge.sort()
uf = UnionFind(N)
cnt = 0
for d, k0, k1 in edge:
    if uf.find(k0) != uf.find(k1):
        uf.union(k0, k1)
        cnt += d
    
    if uf.parents[uf.find(0)] == -N:
        break

print(cnt)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop


N = int(input())
Px = []
Py = []
for k, s in enumerate(sys.stdin.readlines()):
    x, y = map(int, s.split())
    Px.append((x, k))
    Py.append((y, k))

edge = [[] for _ in range(N)]

Px.sort()
for i in range(N - 1):
    x0, k0 = Px[i]
    x1, k1 = Px[i + 1]
    d = abs(x0 - x1)
    edge[k0].append((k1, d))
    edge[k1].append((k0, d))

Py.sort()
for i in range(N - 1):
    y0, k0 = Py[i]
    y1, k1 = Py[i + 1]
    d = abs(y0 - y1)
    edge[k0].append((k1, d))
    edge[k1].append((k0, d))

q = []
used = set([0])
for np, nd in edge[0]:
    heappush(q, (nd, np))

cnt = 0
while len(used) < N:
    d, p = heappop(q)
    if p in used:
        continue
    else:
        cnt += d
        used.add(p)
        for np, nd in edge[p]:
            heappush(q, (nd, np))

print(cnt)

Submission status: Accepted

Solution code:
def get_root(s):
    if s != root[s]:
        root[s] = get_root(root[s])
        return root[s]
    return s

def unite(s, t):
    root_s = get_root(s)
    root_t = get_root(t)
    if not root_s == root_t:
        if rank[s] == rank[t]:
            root[root_t] = root_s
            rank[root_s] += 1
        elif rank[s] > rank[t]:
            root[root_t] = root_s
        else:
            root[root_s] = root_t

def same(s, t):
    if get_root(s) == get_root(t):
        return True
    else:
        return False

n = int(input())
root = [i for i in range(n)]
rank = [1 for _ in range(n)]
s, t = [], []
for i in range(n):
    x, y = map(int, input().split())
    s.append([x, i])
    t.append([y, i])
s.sort()
t.sort()
u = []
for i in range(n - 1):
    u.append([abs(s[i][0] - s[i + 1][0]), s[i][1], s[i + 1][1]])
    u.append([abs(t[i][0] - t[i + 1][0]), t[i][1], t[i + 1][1]])
u.sort()
c = 0
ans = 0
for v in u:
    if not same(v[1], v[2]):
        unite(v[1], v[2])
        c += 1
        ans += v[0]
    if c == n - 1:
        break
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
INF = 10 ** 9 + 7

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

Xx = sorted((x, i) for i, (x, _) in enumerate(X))
Xy = sorted((y, i) for i, (_, y) in enumerate(X))

graph = [[] for _ in range(N)]
for i in range(N - 1):
    graph[Xx[i][1]].append((Xx[i + 1][1], Xx[i + 1][0] - Xx[i][0]))
    graph[Xx[i + 1][1]].append((Xx[i][1], Xx[i + 1][0] - Xx[i][0]))
    
    graph[Xy[i][1]].append((Xy[i + 1][1], Xy[i + 1][0] - Xy[i][0]))
    graph[Xy[i + 1][1]].append((Xy[i][1], Xy[i + 1][0] - Xy[i][0]))

min_cost = [INF] * N
visited = [False] * N

pq = []
heappush(pq, (0, 0))
ret = 0

while pq:
    cost, u = heappop(pq)
    if visited[u]:
        continue
    visited[u] = True
    min_cost[u] = cost
    ret += cost
    for v, c in graph[u]:
        if min_cost[v] > c:
            heappush(pq, (c, v))
            
print(ret)

Submission status: Accepted

Solution code:
def set(a, b):
  R[a].append(b)
  R[b].append(a)

N = int(input())
xy = [[i] + list(map(int, input().split())) for i in range(N)]
R = [[] for _ in range(N)]
xy.sort(key = lambda x: x[1])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  set(a[0], b[0])
xy.sort(key = lambda x: x[2])
for i in range(1, N):
  a = xy[i]
  b = xy[i - 1]
  set(a[0], b[0])

xy.sort()
import heapq
q = [[0, 0]]
L = [True] * N
pop = heapq.heappop
push = heapq.heappush
ans = 0

for _ in range(N):
  k, t = pop(q)
  while not L[t]:
    k, t = pop(q)
  L[t] = False
  ans += k
  for i in R[t]:
    if L[i]:
      x = abs(xy[t][1] - xy[i][1])
      x = min(x, abs(xy[t][2] - xy[i][2]))
      push(q, [x, i])
print(ans)
# online help seeked

Submission status: Accepted

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

import sys
input=sys.stdin.buffer.readline
n=int(input())

x_list=[]
y_list=[]

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

for i in range(1,n):
    edges.append((x_list[i][0]-x_list[i-1][0],x_list[i][1],x_list[i-1][1]))

    edges.append((y_list[i][0]-y_list[i-1][0],y_list[i][1],y_list[i-1][1]))

edges.sort()
uf=UnionFind(n)
ans=0
for e in edges:
    wt=e[0]
    x=e[1]
    y=e[2]
    if uf.find(x)==uf.find(y):
        continue
    ans+=wt
    uf.unite(x,y)
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,n):
        super().__init__()
        self.par = [-1]*n
        self.rank = [0]*n
        self.tsize = [1]*n
    
    def root(self,x):
        if self.par[x] == -1:
            return x 
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x_r = self.root(x)
        y_r = self.root(y)
        
        if self.rank[x_r]>self.rank[y_r]:
            self.par[y_r] = x_r

        elif self.rank[x_r]<self.rank[y_r]:
            self.par[x_r] = y_r

        elif x_r != y_r:
            self.par[y_r] = x_r
            self.rank[x_r] += 1

        if x_r != y_r:
            size = self.tsize[x_r]+self.tsize[y_r]
            self.tsize[x_r] = size
            self.tsize[y_r] = size

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

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

def main():

    n= int(input())
    edge = []
    for i in range(n):
      x,y = list(map(int,input().split()))
      edge.append((x,y,i))
    
    xs = sorted(edge,key=lambda a:a[0])
    ys = sorted(edge,key=lambda a:a[1])

    edge = []
    
    for i in range(n-1):
      x1,y1,p1 = xs[i]
      x2,y2,p2 = xs[i+1]
      edge.append((p1,p2,min(x2-x1,abs(y2-y1))))
      
      x1,y1,p1 = ys[i]
      x2,y2,p2 = ys[i+1]
      edge.append((p1,p2,min(abs(x2-x1),y2-y1)))
    edge.sort(key = lambda a:a[2])  
    uf = UnionFind(n)
    
    ans = 0
    for x,y,w in edge:
      if uf.isSame(x,y):continue
      uf.unite(x,y)
      ans+=w
    print(ans)
      
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from operator import itemgetter
from collections import defaultdict
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix

n = int(input())
xy = [list(map(int, input().split())) + [i] for i in range(n)]
INF = 10 ** 9 + 1

d = defaultdict(lambda: INF)

for key in (itemgetter(0), itemgetter(1)):
    xy.sort(key=key)
    for (x1, y1, i1), (x2, y2, i2) in zip(xy, xy[1:]):
        c = min(abs(x1 - x2), abs(y1 - y2))
        d[(i1, i2)] = min(d[(i1, i2)], c)

row = []
col = []
cost = []
for (k1, k2), c in d.items():
    row.append(k1)
    col.append(k2)
    cost.append(c)

graph = csr_matrix((cost, (row, col)), shape=(n, n))
mst = minimum_spanning_tree(graph, overwrite=True).astype(int)
ans = mst.sum()
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix

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

xyi = [[x, y, i] for i, (x, y) in enumerate(xy)]
edge = set()

xyi.sort()
for (x1, y1, i1), (x2, y2, i2) in zip(xyi, xyi[1:]):
    c = min(abs(x1 - x2), abs(y1 - y2))
    edge.add((i1, i2, c))

xyi.sort(key=itemgetter(1))
for (x1, y1, i1), (x2, y2, i2) in zip(xyi, xyi[1:]):
    c = min(abs(x1 - x2), abs(y1 - y2))
    edge.add((i1, i2, c))

row, col, cost = zip(*edge)

graph = csr_matrix((cost, (row, col)), shape=(n, n))
mst = minimum_spanning_tree(graph, overwrite=True).astype(int)
ans = mst.sum()
print(ans)

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

    # ノードxが属する木のサイズを返す
    def size(self, x):
        return -self.root[self.find_root(x)]

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

#今回の問題では,高々xが隣のやつとyが隣のやつを全部考えればよし
#（詳しくは解説pdfより）
x_sort = sorted(xy, key=lambda x: x[0])
y_sort = sorted(xy, key=lambda x: x[1])

edge = [] #edge=[i番目と,j番目が,コストk]
for i in range(n-1):
    edge.append([x_sort[i][2],x_sort[i+1][2],x_sort[i+1][0]-x_sort[i][0]])
    edge.append([y_sort[i][2],y_sort[i+1][2],y_sort[i+1][1]-y_sort[i][1]])

#クラスカル法では辺のコストを小さい順にみていき閉路ができなければ追加する。を繰り返す
#閉路ができるかどうかはUnionFindで効率的に判定できる
ans = 0
edge.sort(key=lambda x:x[2])
u=UnionFind(n)
for i,j,cost in edge:
    if u.isSame(i,j) == False:
        u.unite(i,j)
        ans+=cost

print(ans)

Submission status: Accepted

Solution code:
#最小全域木　プリム法
from heapq import *

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

#今回の問題では,高々xが隣のやつとyが隣のやつを全部考えればよし
#（詳しくは解説pdfより）
x_sort = sorted(xy, key=lambda x: x[0])
y_sort = sorted(xy, key=lambda x: x[1])

cost = [[]for _ in range(n+3)] #cost[i]にはi番目から(j,k)でj番目にコストkかかる
for i in range(n-1):
    cost[x_sort[i][2]].append((x_sort[i+1][2],x_sort[i+1][0]-x_sort[i][0]))
    cost[x_sort[i+1][2]].append((x_sort[i][2],x_sort[i+1][0]-x_sort[i][0]))

    cost[y_sort[i][2]].append((y_sort[i+1][2],y_sort[i+1][1]-y_sort[i][1]))
    cost[y_sort[i+1][2]].append((y_sort[i][2],y_sort[i+1][1]-y_sort[i][1]))


used=[False]*(n+3)#頂点が最小全域木にもうすでに含まれているかどうか
q=[]
#すでに最小全域木が決まっている部分からまだ決まっていない部分への辺をヒープで管理
#(a,b)でaには向かう先の頂点,bにはかかるコスト
#ヒープで小さいコストからとりだせる

#初期条件
#はじめはどこでもよいので０番目スタートとする(0番目だけではコストは0)
used[0] = True
ans = 0

#0番目からの辺をすべてヒープに挿入
for to,cst in cost[0]:
    heappush(q,(cst,to))

#すでに決まっている最小全域木部分からまだ決まっていない部分を貪欲的にひたすら追加する
#はじめは初期条件の通り
while(len(q)!=0):
    c,ver=heappop(q)
#すでに決まっている部分から一番小さいコストの辺を取り出す
    if used[ver] == True:
        continue
#もしすでに最小全域木部分であればやり直し
#そうでなければコストの分を加算し、新しい頂点を最小全域木部分に追加する
    ans += c
    used[ver] = True
#新しく追加した頂点からの辺をヒープに追加する
    for to,cst in cost[ver]:
        heappush(q,(cst,to))
#これを貪欲的に繰り返すことでうまくいくらしい
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(2147483647)

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

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

x_dif = [((x[i][0], x[i+1][0]), abs(x[i+1][1]-x[i][1])) for i in range(n-1)]
y_dif = [((y[i][0], y[i+1][0]), abs(y[i+1][1]-y[i][1])) for i in range(n-1)]

xy_dif = x_dif + y_dif
xy_dif.sort(key = lambda x:x[1])

p = [-1]*n

def root(x):
  if p[x]<0:
    return x
  p[x] = root(p[x])
  return p[x]

ans = 0
for ab, cost in xy_dif:
  a, b = ab
  #print(a, b, p[a], p[b], p)
  if root(a)!=root(b):
    p[root(a)] = root(b)
    ans += cost

print(ans)

Submission status: Accepted

Solution code:

import heapq
n = int(input())
stw = []
x_list = []
y_list = []
for i in range(n):
  x, y = map(int, input().split())
  x_list += [[x, i]]
  y_list += [[y, i]]

x_list.sort()
y_list.sort()

for i in range(n-1):
  stw += [[x_list[i][1], x_list[i+1][1], abs(x_list[i][0]-x_list[i+1][0])]]
for i in range(n-1):
  stw += [[y_list[i][1], y_list[i+1][1], abs(y_list[i][0]-y_list[i+1][0])]]

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

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 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())


def kruskal():
  # stw = [[s0, t0, w0], [s1, t1, w1], ..., [sn, tn, wn]]
  # stw: s: 始点, t: 終点, w: st間の重み
  # stwはwを小さい順にソートされたものとする
  # s, tを入れ替えたものはいれなくていい
  res = 0
  uf = UnionFind(n)
  for i in range(len(stw)):
    s, t, w = stw[i]
    if not uf.isSameGroup(s, t):
      uf.Unite(s, t)
      res += w
  return res

ans = kruskal()
print(ans)

Submission status: Accepted

Solution code:
from heapq import *
from collections import defaultdict
INF = float('inf')
class Prim:

    def __init__(self,N):#Nはグラフのノード数
        self.N = N
        self.cost = defaultdict(list)
        self.used = [False for _ in range(N)]
    
    def setcost(self,u,v,w):
        self.cost[u].append((v,w))
        self.cost[v].append((u,w))
    
    def prim(self):
        que = []
        heapify(que)
        used = self.used
        for e in self.cost[0]:
            heappush(que,[e[1],e[0]])
        used[0] = True
        res = 0
        while que:
            p = heappop(que)
            cos,v = p
            if used[v]:continue
            self.used[v] = True
            for e in self.cost[v]:
                if not used[e[0]]:
                    heappush(que,[e[1],e[0]])      
            res += cos
        return res

def main():
    N = int(input())
    cost = []
    for i in range(N):
        x,y = map(int,input().split())
        cost.append((x,y,i))
    prim = Prim(N)
    x = tuple(sorted(cost,key=lambda x: x[0]))
    y = tuple(sorted(cost,key=lambda x: x[1]))
    for i in range(N-1):
        a,b,u = x[i]
        c,d,v = x[i+1]
        w = min(abs(a-c),abs(b-d))
        prim.setcost(u,v,w)
        e,f,s = y[i]
        g,h,t = y[i+1]
        u = min(abs(e-g),abs(f-h))
        prim.setcost(s,t,u)
    ans = prim.prim()
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict
N=int(input())
X=[]
Y=[]
dic_x=defaultdict(list)
dic_y=defaultdict(list)
for i in range(N):
  x,y=map(int,input().split())
  dic_x[x].append(i)
  dic_y[y].append(i)
  X.append(x)
  Y.append(y)
X=sorted(X)
Y=sorted(Y)
V=N
E=(V-1)*2
G=[]
for i in range(N-1):
  heapq.heappush(G,(X[i+1]-X[i],dic_x[X[i]].pop(),dic_x[X[i+1]][0]))
  heapq.heappush(G,(Y[i+1]-Y[i],dic_y[Y[i]].pop(),dic_y[Y[i+1]][0]))
 
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]

def Minmum_Spanning_Tree(G,V,E):
  uf=UnionFind(V)
  cnt=0
  tot_weight=0
  while cnt!=V-1:
    w,u,v=heapq.heappop(G)
    if uf.same(u-1,v-1)==False:
      uf.unite(u-1,v-1)
      tot_weight+=w
      cnt+=1
  return tot_weight

weight=Minmum_Spanning_Tree(G,V,E)
print(weight)

Submission status: Accepted

Solution code:
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()

edge = []
for i in range(n):
    x, a = X[i]
    y, s = Y[i]
    if i > 0:
        xb, b = X[i-1]
        ty, t = Y[i-1]
        edge.append((a, b, abs(x - xb)))
        edge.append((s, t, abs(y - ty)))
    if i + 1 < n:
        xb, b = X[i+1]
        ty, t = Y[i+1]
        edge.append((a, b, abs(x - xb)))
        edge.append((s, t, abs(y - ty)))

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

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

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

    def union(self, x, y):
        xp = self.find(x)
        yp = self.find(y)
        if xp != yp:
            if self.table[xp] < self.table[yp]:
                self.table[xp] += self.table[yp]
                self.table[yp] = xp
            else:
                self.table[yp] += self.table[xp]
                self.table[xp] = yp

u = Unionfind(n)
ans = 0
for a, b, c in sorted(edge, key = lambda x: x[2]):
    if not u.same(a, b):
        ans += c
        u.union(a, b)
print(ans)