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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from __future__ import division, print_function
import sys


def main():
    n = int(sys.stdin.readline().strip())
    xy = []
    for _ in range(n):
        xy.append(map(int, sys.stdin.readline().strip().split(" ")))

    table = [-1 for _ in xrange(n)]

    def find(x):
        if table[x] < 0:
            return x
        else:
            # 経路の圧縮
            table[x] = find(table[x])
            return table[x]

    def union(x, y):
        s1 = find(x)
        s2 = find(y)
        if s1 != s2:
            if table[s1] <= table[s2]:
                # 小さいほうが個数が多い
                table[s1] += table[s2]
                table[s2] = s1
            else:
                table[s2] += table[s1]
                table[s1] = s2
            return True
        return False

    costs = []
    for i in range(n):
        for j in range(i + 1, n):
            ax, ay = xy[i]
            bx, by = xy[j]
            costs.append((i, j, min(abs(ax - bx), abs(ay - by))))
    costs.sort(key=lambda (x, y, c): c)

    result = 0
    while len(costs) > 0:
        x, y, c = costs.pop(0)
        if union(x, y):
            result += c
        # print(x, y, c)
    print(result)


if __name__ == '__main__':
    main()

Submission status: Memory Limit Exceeded

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

class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.components = n  # 連結成分の数

    def root(self, x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.p[x] = y
            self.components -= 1
    
    def same(self, x,y):
        return (self.root(x) == self.root(y))

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

X.sort()
Y.sort()

edges = []
for i in range(N-1):
    edges.append([X[i+1][0]-X[i][0], X[i][1], X[i+1][1]])
    edges.append([Y[i+1][0]-Y[i][0], Y[i][1], Y[i+1][1]])
edges.sort()

UF = UnionFind(N)
ans = 0
for cost, s, t in edges:
    if UF.same(s,t): continue

    UF.unite(s,t)
    ans += cost
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
from heapq import heappop,heappush
import sys
sys.setrecursionlimit(10**6)
n=int(input())
pair=[i for i in range(n)]
que=[]
e=[None]*n
for i in range(n):
  x,y=map(int,input().split())
  e[i]=(i,x,y)
ex=sorted(e,key=lambda x:x[1])
ey=sorted(e,key=lambda x:x[2])
for i in range(n-1):
  w=ex[i+1][1]-ex[i][1]
  heappush(que,(w,ex[i][0],ex[i+1][0]))
for i in range(n-1):
  w=ey[i+1][2]-ey[i][2]
  heappush(que,(w,ey[i][0],ey[i+1][0]))
def find(x):
  if x==pair[x]:return x
  else:
    tmp=find(pair[x])
    pair[x]=tmp
    return tmp
q=[]
ans=0
while que:
  w,s,t=heappop(que)
  root_s=find(s)
  root_t=find(t)
  if root_s!=root_t:
    pair[root_s]=root_t
    ans+=w
print(ans)

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop, heapify

input = sys.stdin.buffer.readline
in_n = lambda: int(input())
in_nn = lambda: map(int, input().split())
in_s = lambda: input().rstrip().decode('utf-8')
in_map = lambda: [s == ord('.') for s in input() if s != ord('\n')]

MOD = 10**9 + 7
INF = 8 * 10**18


# 最小全域木 O(ElogV)
def prims_algorithm(N, cost):

    used = [False] * N
    used[0] = True
    que = [(c, w) for c, w in cost[0]]
    heapify(que)

    ret = 0
    while que:
        cv, v = heappop(que)
        if used[v]:
            continue
        used[v] = True
        ret += cv
        for c, w in cost[v]:
            if used[w]:
                continue
            heappush(que, (c, w))

    return ret


def main():

    N = in_n()
    x = [0] * N
    y = [0] * N

    for i in range(N):
        x[i], y[i] = in_nn()

    sort_ind_x = sorted(range(N), key=lambda i: x[i])
    sort_ind_y = sorted(range(N), key=lambda i: y[i])

    cost = [[] for _ in range(N)]
    for i in range(N - 1):
        j1, j2 = sort_ind_x[i], sort_ind_x[i + 1]
        c = abs(x[j1] - x[j2])
        cost[j1].append((c, j2))
        cost[j2].append((c, j1))

        j1, j2 = sort_ind_y[i], sort_ind_y[i + 1]
        c = abs(y[j1] - y[j2])
        cost[j1].append((c, j2))
        cost[j2].append((c, j1))

    ans = prims_algorithm(N, cost)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop, heapify

input = sys.stdin.buffer.readline
in_n = lambda: int(input())
in_nn = lambda: map(int, input().split())
in_s = lambda: input().rstrip().decode('utf-8')
in_map = lambda: [s == ord('.') for s in input() if s != ord('\n')]

MOD = 10**9 + 7
INF = 8 * 10**18


def main():

    N = in_n()
    x = [0] * N
    y = [0] * N

    for i in range(N):
        x[i], y[i] = in_nn()

    sort_ind_x = sorted(range(N), key=lambda i: x[i])
    sort_ind_y = sorted(range(N), key=lambda i: y[i])

    cost = [[] for _ in range(N)]
    for i in range(N - 1):
        j1, j2 = sort_ind_x[i], sort_ind_x[i + 1]
        c = abs(x[j1] - x[j2])
        cost[j1].append((c, j2))
        cost[j2].append((c, j1))

        j1, j2 = sort_ind_y[i], sort_ind_y[i + 1]
        c = abs(y[j1] - y[j2])
        cost[j1].append((c, j2))
        cost[j2].append((c, j1))

    used = [0] * N
    used[0] = 1
    que = [(c, w) for c, w in cost[0]]
    heapify(que)

    ans = 0
    while que:
        cv, v = heappop(que)
        if used[v]:
            continue
        used[v] = 1
        ans += cv
        for c, w in cost[v]:
            if used[w]:
                continue
            heappush(que, (c, w))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.buffer.readline
in_n = lambda: int(input())
in_nn = lambda: map(int, input().split())
in_s = lambda: input().rstrip().decode('utf-8')
in_map = lambda: [s == ord('.') for s in input() if s != ord('\n')]

MOD = 10**9 + 7
INF = 8 * 10**18


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):
        ret = dict()
        for i in range(self.n):
            r = self.find(i)
            if r in ret:
                ret[r].append(i)
            else:
                ret[r] = [i]
        return ret

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():

    N = in_n()
    x = [0] * N
    y = [0] * N

    for i in range(N):
        x[i], y[i] = in_nn()

    sort_ind_x = sorted(range(N), key=lambda i: x[i])
    sort_ind_y = sorted(range(N), key=lambda i: y[i])

    cost = []
    for i in range(N - 1):
        j1, j2 = sort_ind_x[i], sort_ind_x[i + 1]
        c = abs(x[j1] - x[j2])
        cost.append((c, j1, j2))

        j1, j2 = sort_ind_y[i], sort_ind_y[i + 1]
        c = abs(y[j1] - y[j2])
        cost.append((c, j1, j2))

    cost.sort()
    uni = UnionFind(N)
    ans = 0

    for c, v1, v2 in cost:
        if not uni.same(v1, v2):
            ans += c
            uni.union(v1, v2)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

from heapq import heappop, heappush

def prim(adjacent:list, root=0):
    '''
    Prim法。最小全域木のコストを求める。負の閉路も可
    --------
        adjacent : 隣接リスト
        root     : 探索開始頂点
    --------
        min_cost : 最小コスト
    '''
    n = len(adjacent)
    visited = [False] * n
    min_cost = 0
    q = [(0, root)]
    while q:
        weight, vi = heappop(q)
        if visited[vi]:
            continue
        visited[vi] = True
        min_cost += weight
        for vj, weight in adjacent[vi]:
            if not visited[vj]:
                heappush(q, (weight, vj))
    return min_cost

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

adjacent = [[] for _ in range(n)]
for i in range(n-1):
    x0, y0, v0 = xordered[i]
    x1, y1, v1 = xordered[i+1]
    weight = min(abs(x0-x1), abs(y0-y1))
    adjacent[v0].append((v1, weight))
    adjacent[v1].append((v0, weight))
    x0, y0, v0 = yordered[i]
    x1, y1, v1 = yordered[i+1]
    weight = min(abs(x0-x1), abs(y0-y1))
    adjacent[v0].append((v1, weight))
    adjacent[v1].append((v0, weight))

print(prim(adjacent))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

def prim(adjacent:list, root=0):
    n = len(adjacent)
    visited = [False] * n
    min_cost = 0
    q = [(0, root)]

    count = 0
    while q and count < n:
        weight, vi = heappop(q)
        if visited[vi]:
            continue
        visited[vi] = True
        min_cost += weight
        count += 1
        for vj, weight in adjacent[vi]:
            heappush(q, (weight, vj))
    return min_cost

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

adjacent = [[] for _ in range(n)]
for i in range(n-1):
    x0, y0, v0 = xordered[i]
    x1, y1, v1 = xordered[i+1]
    weight = min(abs(x0-x1), abs(y0-y1))
    adjacent[v0].append((v1, weight))
    adjacent[v1].append((v0, weight))
    x0, y0, v0 = yordered[i]
    x1, y1, v1 = yordered[i+1]
    weight = min(abs(x0-x1), abs(y0-y1))
    adjacent[v0].append((v1, weight))
    adjacent[v1].append((v0, weight))

print(prim(adjacent))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

def prim(adjacent:list, root=0):
    n = len(adjacent)
    visited = [False] * n
    min_cost = 0
    q = [(0, root)]
    while q:
        weight, vi = heappop(q)
        if visited[vi]:
            continue
        visited[vi] = True
        min_cost += weight
        for vj, weight in adjacent[vi]:
            heappush(q, (weight, vj))
    return min_cost

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

adjacent = [[] for _ in range(n)]
for i in range(n-1):
    x0, y0, v0 = xordered[i]
    x1, y1, v1 = xordered[i+1]
    weight = min(abs(x0-x1), abs(y0-y1))
    adjacent[v0].append((v1, weight))
    adjacent[v1].append((v0, weight))
    x0, y0, v0 = yordered[i]
    x1, y1, v1 = yordered[i+1]
    weight = min(abs(x0-x1), abs(y0-y1))
    adjacent[v0].append((v1, weight))
    adjacent[v1].append((v0, weight))

print(prim(adjacent))

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
import sys
input=sys.stdin.readline
class unionfind():
    def __init__(self,n):
        self.par = list(range(n))
        self.size = [1]*n
        self.rank = [0]*n
        self.n = n
        #self.ps=set(range(n)) #not tested
    def root(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

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

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x==y:return
        else:
            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.ps.discard(y)##親の集合からyを取り除く
            self.size[x] +=self.size[y]
    def get_size(self,x):
        x = self.root(x)
        return self.size[x]
    def parent_set(self):
        for x in range(self.n):
            self.root(x)
        s = set()
        for par in self.par:
            s.add(par)
        return s

"""
edges :: [(cost,u,v) for every Edge]
"""
def Kruskal(edges,n):
    tot=0
    edges.sort()
    uf = unionfind(n)
    for cost,u,v in edges:
        if uf.same(u,v):
            pass
        else:
            uf.unite(u,v)
            tot+=cost
    return tot

xy=[]
n = ni()
for i in range(n):
    x,y=lma()
    xy.append((i,x,y))
xy.sort(key=lambda x:x[1])
#print(xy)
ed=[]
INF=10**15
ip=INF
xp=INF
yp=INF
for i,x,y in xy:
    if ip!=INF:
        ed.append((x-xp,i,ip))
    ip=i;xp=x;yp=y

xy.sort(key=lambda x:x[2])
#print(xy)
ip=INF
xp=INF
yp=INF
for i,x,y in xy:
    if ip!=INF:
        ed.append((y-yp,i,ip))
    ip=i;xp=x;yp=y
#print(ed)
print(Kruskal(ed,n))

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]


def kruskal(n, edges):
    """
    Solve Minimum Spanning Tree by Kruskal's algorithm.
    :param n: Number of nodes
    :param edges: [u, v, cost]
    :return: Total cost
    """
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(n)
    total_cost = 0
    for u, v, c in edges:
        if not uf.is_same(u, v):
            total_cost += c
            uf.union(u, v)
    return total_cost


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()

edges = []

for x1, x2 in zip(X[:-1], X[1:]):
    edges.append([x1[1], x2[1], x2[0] - x1[0]])

for y1, y2 in zip(Y[:-1], Y[1:]):
    edges.append([y1[1], y2[1], y2[0] - y1[0]])

print(kruskal(N, edges))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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())


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

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

diff_list.sort()
uf = UnionFind(N)

cost = 0
for w,f,t in diff_list:
    if uf.same(f-1,t-1):
        continue
    cost += w
    uf.union(f-1,t-1)
    if uf.group_count == 1:
        break

print(cost)

Submission status: Accepted

Solution code:
# D - Built?
import sys
import heapq

# input
N = int(input())

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

# build matrix
G = [[] for _ in range(N)]

X.sort()
Y.sort()
for i in range(N - 1):
    d_u, u = X[i]
    d_v, v = X[i + 1]

    G[u].append((d_v - d_u, v))
    G[v].append((d_v - d_u, u))

    d_u, u = Y[i]
    d_v, v = Y[i + 1]

    G[u].append((d_v - d_u, v))
    G[v].append((d_v - d_u, u))


# 最小全域木
q = []
fp = [False] * N  # 探索済み
fp[0] = True

for d, u in G[0]:
    heapq.heappush(q, (d, u))

ans = 0
while q:
    d, u = heapq.heappop(q)

    if fp[u]:
        continue
    fp[u] = True
    ans += d

    for d_v, v in G[u]:
        if fp[v]:
            continue
        heapq.heappush(q, (d_v, v))

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.components = n  # 連結成分の数

    def root(self, x):
        if self.p[x] != x:
            stack = [x]
            while True:
                top = stack[-1]
                if self.p[top] == top:
                    break
                else:
                    stack.append(self.p[top])
            for v in stack:
                self.p[v] = top
        return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.p[x] = y
            self.components -= 1
    
    def same(self, x,y):
        return (self.root(x) == self.root(y))

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

X.sort()
Y.sort()

edges = []
for i in range(N-1):
    edges.append([X[i+1][0]-X[i][0], X[i][1], X[i+1][1]])
    edges.append([Y[i+1][0]-Y[i][0], Y[i][1], Y[i+1][1]])
edges.sort()

UF = UnionFind(N)
ans = 0
for cost, s, t in edges:
    if UF.same(s,t): continue

    UF.unite(s,t)
    ans += cost
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.components = n  # 連結成分の数

    def root(self, x):
        if self.p[x] != x:
            x_now = x
            while self.p[x_now] != x_now:
                x_now = self.p[x_now]
            self.p[x] = x_now
        return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.p[x] = y
            self.components -= 1
    
    def same(self, x,y):
        return (self.root(x) == self.root(y))

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

X.sort()
Y.sort()

edges = []
for i in range(N-1):
    edges.append([X[i+1][0]-X[i][0], X[i][1], X[i+1][1]])
    edges.append([Y[i+1][0]-Y[i][0], Y[i][1], Y[i+1][1]])
edges.sort()

UF = UnionFind(N)
ans = 0
for cost, s, t in edges:
    if UF.same(s,t): continue

    UF.unite(s,t)
    ans += cost
print(ans)

Submission status: Accepted

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

es = []
for (x0,_,i0),(x1,_,i1) in zip(sx,sx[1:]):
  es.append((x1-x0, i0, i1))
for (_,y0,i0),(_,y1,i1) in zip(sy,sy[1:]):
  es.append((y1-y0, i0, i1))
es.sort(key=lambda x:x[0])
 
class UnionFind:
  def __init__(self,N):
    self.parent = [i for i in range(N)]
    self._size = [1] * N
    self.count = 0
  def root(self,a):
    if self.parent[a] == a:
      return a
    else:
      self.parent[a] = self.root(self.parent[a])
      return self.parent[a]
  def is_same(self,a,b):
    return self.root(a) == self.root(b)
  def unite(self,a,b):
    ra = self.root(a)
    rb = self.root(b)
    if ra == rb: return
    if self._size[ra] < self._size[rb]: ra,rb = rb,ra
    self._size[ra] += self._size[rb]
    self.parent[rb] = ra
    self.count += 1
  def size(self,a):
    return self._size[self.root(a)]

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

Submission status: Accepted

Solution code:
N = int(input())

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

#Union Find
#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]


V = N#頂点の数、辺の数
v=[]

xy.sort()
for i in range(1,N):#[0][1]つなぐところ[2]距離
    v.append([xy[i-1][2],xy[i][2],min(abs(xy[i][0]-xy[i-1][0]),abs(xy[i][1]-xy[i-1][1]))])
xy.sort(key = lambda x:x[1])
for i in range(1,N):#[0][1]つなぐところ[2]距離
    v.append([xy[i-1][2],xy[i][2],min(abs(xy[i][0]-xy[i-1][0]),abs(xy[i][1]-xy[i-1][1]))])

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

#初期化
#根なら-size,子なら親の頂点
par = [-1]*V

cost = 0

for i in range(0,len(v),1):
    if not same(v[i][0],v[i][1]):
        unite(v[i][0],v[i][1])
        cost+=v[i][2]

print(cost)

Submission status: Accepted

Solution code:
from heapq import *
N = int(input())
X,Y=[],[]
for n in range(N):
  x,y=map(int,input().split())
  X.append((x, n))
  Y.append((y, n))
X.sort()
Y.sort()
D=[[] for v in range(N)]
for n in range(N-1):
  cost = X[n+1][0]-X[n][0]
  D[X[n+1][1]].append((cost,X[n][1]))
  D[X[n][1]].append((cost,X[n+1][1]))
  cost=Y[n+1][0]-Y[n][0]
  D[Y[n+1][1]].append((cost,Y[n][1]))
  D[Y[n][1]].append((cost,Y[n+1][1]))

visited=[0]*N
pq = []
for w, t in D[0]:
  heappush(pq,(w,t))
visited[0]=1

ans = 0
while pq:
  w,t=heappop(pq)
  if visited[t]:
    continue
  visited[t]=1
  ans+=w
  for w,s in D[t]:
    if visited[s]==0:
      heappush(pq,(w,s))
print (ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    xy = [LI() for _ in range(N)]

    x = [(xy[i][0],i) for i in range(N)]
    y = [(xy[i][1],i) for i in range(N)]

    x.sort()
    y.sort()

    edge = []
    p,i = x[0]
    for q,j in x[1:]:
        edge.append((q-p,i,j))
        p,i = q,j

    p,i = y[0]
    for q,j in y[1:]:
        edge.append((q-p,i,j))
        p,i = q,j

    edge.sort()

    g = [i for i in range(N + 1)]
    g_num = [1 for i in range(N + 1)]

    def find(x):
        if g[x] == x: return x
        g[x] = find(g[x])
        return g[x]

    def union(x, y):
        if find(x) == find(y): return
        if g_num[g[x]] < g_num[g[y]]: x, y = y, x
        g_num[g[x]] += g_num[g[y]]
        g_num[g[y]] = 0
        g[g[y]] = g[x]

    ans = 0
    for v,i,j in edge:
        if find(i) != find(j):
            ans += v
            union(i,j)

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# UnionFind
#############################################################
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, v):  # vが属する集合の根を返す
        if self.parents[v] < 0:
            return v
        else:
            self.parents[v] = self.find(self.parents[v])
            return self.parents[v]

    def unite(self, u, v):  # 「uが属する集合」と「vが属する集合」を併合（根同士を結ぶ）
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        if self.parents[u] > self.parents[v]:  # u < v に統一する
            u, v = v, u
        self.parents[u] += self.parents[v]
        self.parents[v] = u

    def size(self, v):  # vが属する集合の要素数
        return -self.parents[self.find(v)]

    def same(self, u, v):  # uとvが同じ集合に属するか否か
        return self.find(u) == self.find(v)
#############################################################
import sys
input = sys.stdin.readline

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

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

dist = []
for i in range(N - 1):
    # iとi+1の距離、iのindex, i+1のindex
    dist.append([X[i + 1][0] - X[i][0], X[i][2], X[i + 1][2]])
    dist.append([Y[i + 1][1] - Y[i][1], Y[i][2], Y[i + 1][2]])

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

uf = UnionFind(N)
# クラスカル法
for cost, i, j in dist:
    if uf.same(i, j):
        continue
    uf.unite(i, j)
    ans += cost

print(ans)

Submission status: Accepted

Solution code:
# UnionFind
#############################################################
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, v):  # vが属する集合の根を返す
        if self.parents[v] < 0:
            return v
        else:
            self.parents[v] = self.find(self.parents[v])
            return self.parents[v]

    def unite(self, u, v):  # 「uが属する集合」と「vが属する集合」を併合（根同士を結ぶ）
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        if self.parents[u] > self.parents[v]:  # u < v に統一する
            u, v = v, u
        self.parents[u] += self.parents[v]
        self.parents[v] = u

    def size(self, v):  # vが属する集合の要素数
        return -self.parents[self.find(v)]

    def same(self, u, v):  # uとvが同じ集合に属するか否か
        return self.find(u) == self.find(v)
#############################################################

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

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

dist = []
for i in range(N - 1):
    # iとi+1の距離、iのindex, i+1のindex
    dist.append([X[i + 1][0] - X[i][0], X[i][2], X[i + 1][2]])
    dist.append([Y[i + 1][1] - Y[i][1], Y[i][2], Y[i + 1][2]])

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

uf = UnionFind(N)
# クラスカル法
for cost, i, j in dist:
    if uf.same(i, j):
        continue
    uf.unite(i, j)
    ans += cost

print(ans)

Submission status: Accepted

Solution code:
# UnionFind
#############################################################
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, v):  # vが属する集合の根を返す
        if self.parents[v] < 0:
            return v
        else:
            self.parents[v] = self.find(self.parents[v])
            return self.parents[v]

    def unite(self, u, v):  # 「uが属する集合」と「vが属する集合」を併合（根同士を結ぶ）
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        if self.parents[u] > self.parents[v]:  # u < v に統一する
            u, v = v, u
        self.parents[u] += self.parents[v]
        self.parents[v] = u

    def size(self, v):  # vが属する集合の要素数
        return -self.parents[self.find(v)]

    def same(self, u, v):  # uとvが同じ集合に属するか否か
        return self.find(u) == self.find(v)
#############################################################

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

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

side = []
for i in range(N - 1):
    # iとi+1の距離、iのindex, i+1のindex
    side.append([X[i + 1][0] - X[i][0], X[i][2], X[i + 1][2]])
    side.append([Y[i + 1][1] - Y[i][1], Y[i][2], Y[i + 1][2]])

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

uf = UnionFind(N)

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

print(ans)

Submission status: Accepted

Solution code:
with open(0) as f:
    N, *xy = map(int, f.read().split())

from collections import namedtuple
v = namedtuple('v',['coordinate','num'])
#最小全域木に使われる辺は高々座標(xまたはy)が隣接する頂点間のものである
#したがって、x座標・y座標それぞれでソートして辺を求める
X = sorted([v(x,i) for x,i in zip(xy[::2], range(N))])
Y = sorted([v(y,i) for y,i in zip(xy[1::2], range(N))])

diffiter = lambda X:zip(X[:len(X)-1], X[1:]) #Xの1階階差差分のイテレータを返す関数
cost = lambda u,v:abs(u.coordinate - v.coordinate)
from itertools import chain
Edge = sorted([(cost(u,v), u.num, v.num) for u,v in chain(diffiter(X),diffiter(Y))])

root = namedtuple('root',['num', 'rank']) #(num_of_root, rank_of_root)
Root = [root(i,0) for i in range(N)]

def fr(i): #findRoot
    if i == Root[i].num:
        return Root[i]
    Root[i] = fr(Root[i].num)
    return Root[i]


def unionT(i, j): #unionTree
    p, q = fr(i), fr(j)
    if p.rank < q.rank:
        Root[p.num] = q
    elif p.rank > q.rank:
        Root[q.num] = p
    elif p.rank == q.rank:
        r, s = min(p, q), max(p, q)
        Root[r.num] = Root[s.num] = root(r.num, r.rank+1)
    

ans = 0
#最小全域木の大きさ算出(環状にならないように辺を小さい順に足してゆく)
for w, i, j in Edge:
    if fr(i).num == fr(j).num: #既に連結済み
        continue
    else:
        unionT(i,j)
        ans += w
print(ans)