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 UF():
  def __init__(self, N):
    self.par = [-1]*N
 
  def find(self, x):
    if self.par[x] < 0:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
 
  def union(self, x,y):
    p1,p2 = self.find(x),self.find(y)
    if p1 == p2: return
    if p1 > p2:
      p1,p2 = p2,p1
    self.par[p1] += self.par[p2]
    self.par[p2] = p1
 
  def same(self, x,y):
    return self.find(x) == self.find(y)

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

edges = []

sorted_x = sorted(coords, key=lambda x: x[1])
for i in range(n-1):
  c = abs(sorted_x[i][1] - sorted_x[i+1][1])
  u,v = sorted_x[i][0], sorted_x[i+1][0]
  edges.append((c,u,v))

sorted_y = sorted(coords, key=lambda x: x[2])
for i in range(n-1):
  c = abs(sorted_y[i][2] - sorted_y[i+1][2])
  u,v = sorted_y[i][0], sorted_y[i+1][0]
  edges.append((c,u,v))

edges.sort()

uf = UF(n)
res = 0
for c,u,v in edges:
  if not uf.same(u,v):
    uf.union(u,v)
    res += c
 
print(res)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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():
    from operator import itemgetter
    import heapq

    n = int(readline())
    cities = [list(map(int, readline().split())) + [i] for i in range(n)]
    uf = UnionFind(n)

    cx = sorted(cities, key=itemgetter(0))
    cy = sorted(cities, key=itemgetter(1))

    edge = []

    for i in range(1, n):
        dx = cx[i][0] - cx[i - 1][0]
        heapq.heappush(edge, (dx, cx[i][2], cx[i - 1][2]))

    for i in range(1, n):
        dy = cy[i][1] - cy[i - 1][1]
        heapq.heappush(edge, (dy, cy[i][2], cy[i - 1][2]))

    ans = 0
    while edge:
        cost, u, v = heapq.heappop(edge)
        if not uf.same(u, v):
            uf.union(u, v)
            ans += cost

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main 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 same(self, x, y):
        return self.find(x) == self.find(y)

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

N = getN()
query = []
for i in range(N):
    a, b = getNM()
    query.append([a, b, i])

q_a = sorted(query, key = lambda i: i[0])
q_b = sorted(query, key = lambda i: i[1])
edges = []

a1 = q_a[0]
b1 = q_b[0]
for i in range(1, N):
    a2 = q_a[i]
    b2 = q_b[i]
    edges.append([abs(a1[0] - a2[0]), a1[2], a2[2]])
    edges.append([abs(b1[1] - b2[1]), b1[2], b2[2]])
    a1, b1 = a2, b2
edges.sort()

def kruskal(n, edges):
    U = UnionFind(n)
    res = 0
    for e in edges:
        w, s, t = e
        if not U.same(s, t):
            res += w
            U.union(s, t)
        if U.size(0) == N:
            break
    return res
print(kruskal(N, edges))

Submission status: Accepted

Solution code:
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        if deep[x] > deep[y]:
            par[x] += par[y]
            par[y] = x
        elif deep[x] < deep[y]:
            par[y] += par[x]
            par[x] = y
        else:
            par[x] += par[y]
            par[y] = x
            deep[x] += 1
        return True
def same(x,y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
n = int(input())
par = [-1]*n
deep = [1]*n
p = []
edge = []
for i in range(n):
    x,y = map(int,input().split())
    p.append([x,y,i])
p.sort(key=lambda x:x[0])
for i in range(n-1):
    x_0,_,j=p[i]
    x_1,_,k=p[i+1]
    edge.append([x_1-x_0,j,k])
p.sort(key=lambda x:x[1])
for i in range(n-1):
    _,y_0,j=p[i]
    _,y_1,k=p[i+1]
    edge.append([y_1-y_0,j,k])
edge.sort()
ans = 0
for i in range(len(edge)):
    cost,u,v = edge[i]
    if not same(u,v):
        unite(u,v)
        ans+=cost
print(ans)

Submission status: Accepted

Solution code:
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x,y):
    parx = find(x)
    pary = find(y)
    if parx == pary:
        return False
    else:
        par[parx] += par[pary]
        par[pary] = x
        return True
def same(x,y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
n = int(input())
par = [-1]*n
p = []
edge = []
for i in range(n):
    x,y = map(int,input().split())
    p.append([x,y,i])
p.sort(key=lambda x:x[0])
for i in range(n-1):
    x_0,_,j=p[i]
    x_1,_,k=p[i+1]
    edge.append([x_1-x_0,j,k])
p.sort(key=lambda x:x[1])
for i in range(n-1):
    _,y_0,j=p[i]
    _,y_1,k=p[i+1]
    edge.append([y_1-y_0,j,k])
edge.sort()
ans = 0
for i in range(len(edge)):
    cost,u,v = edge[i]
    if not same(u,v):
        unite(u,v)
        ans+=cost
print(ans)

Submission status: Accepted

Solution code:
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        par[x] += par[y]
        par[y] = x
        return True
def same(x,y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
n = int(input())
par = [-1]*n
p = []
edge = []
for i in range(n):
    x,y = map(int,input().split())
    p.append([x,y,i])
p.sort(key=lambda x:x[0])
for i in range(n-1):
    x_0,_,j=p[i]
    x_1,_,k=p[i+1]
    edge.append([x_1-x_0,j,k])
p.sort(key=lambda x:x[1])
for i in range(n-1):
    _,y_0,j=p[i]
    _,y_1,k=p[i+1]
    edge.append([y_1-y_0,j,k])
edge.sort()
ans = 0
for i in range(len(edge)):
    cost,u,v = edge[i]
    if not same(u,v):
        unite(u,v)
        ans+=cost
print(ans)

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)


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

l.sort()
for i in range(N-1):
    x1, y1, s = l[i]
    x2, y2, t = l[i+1]
    q.append((abs(x1-x2), s, t))

l.sort(key=lambda x:x[1])
for i in range(N-1):
    x1, y1, s = l[i]
    x2, y2, t = l[i+1]
    q.append((abs(y1-y2), s, t))

uft = UnionFind(N)
ans = 0
q.sort()

for cost, s, t in q:
    if not uft.isunited(s, t):
        ans += cost
        uft.unite(s, t)

print(ans)

Submission status: Accepted

Solution code:
import sys
buf = sys.stdin.buffer


class UnionFind:
    def __init__(self, num_of_node):
        self.roots = [-1] * num_of_node
        self.groups = num_of_node

    def get_root(self, node):
        root = self.roots[node]
        if root == -1:
            return node

        else:
            root = self.get_root(root)
            self.roots[node] = root
            return root

    def is_same_group(self, node1, node2):
        return self.get_root(node1) == self.get_root(node2)

    def unite(self, node1, node2):
        self.groups -= 1
        root1, root2 = self.get_root(node1), self.get_root(node2)
        self.roots[root2] = root1


def main():
    n = int(buf.readline())
    XY = map(int, buf.read().split())
    Xs = []
    Ys = []
    for i, (x, y) in enumerate(zip(XY, XY)):
        Xs.append((x-1, i))
        Ys.append((y-1, i))

    Xs.sort()
    Ys.sort()

    edges = []
    for i in range(n-1):
        x1, node1 = Xs[i]
        x2, node2 = Xs[i+1]
        y1, node3 = Ys[i]
        y2, node4 = Ys[i+1]
        edges.append((x2-x1, node1, node2))
        edges.append((y2-y1, node3, node4))

    edges.sort(reverse=True)

    ans = 0
    uf = UnionFind(n)
    while uf.groups != 1:
        d, node1, node2 = edges.pop()
        if uf.is_same_group(node1, node2):
            continue
        uf.unite(node1, node2)
        ans += d

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
buf = sys.stdin.buffer


class UnionFind:
    def __init__(self, num_of_node):
        self.roots = [-1] * num_of_node
        self.groups = num_of_node

    def get_root(self, node):
        root = self.roots[node]
        if root == -1:
            return node

        else:
            root = self.get_root(root)
            self.roots[node] = root
            return root

    def is_same_group(self, node1, node2):
        return self.get_root(node1) == self.get_root(node2)

    def unite(self, node1, node2):
        self.groups -= 1
        root1, root2 = self.get_root(node1), self.get_root(node2)
        self.roots[root2] = root1


def main():
    n = int(buf.readline())
    XY = map(int, buf.read().split())
    Xs = []
    Ys = []
    for i, (x, y) in enumerate(zip(XY, XY)):
        Xs.append((x-1, i))
        Ys.append((y-1, i))

    Xs.sort()
    Ys.sort()

    edges = []
    for i, ((x, node), (nx, new_node)) in enumerate(zip(Xs[:-1], Xs[1:])):
        edges.append((nx-x, node, new_node))

    for i, ((y, node), (ny, new_node)) in enumerate(zip(Ys[:-1], Ys[1:])):
        edges.append((ny-y, node, new_node))

    edges.sort(reverse=True)

    ans = 0
    uf = UnionFind(n)
    while uf.groups != 1:
        d, node1, node2 = edges.pop()
        if uf.is_same_group(node1, node2):
            continue
        uf.unite(node1, node2)
        ans += d

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
buf = sys.stdin.buffer


class UnionFind:
    def __init__(self, num_of_node):
        self.roots = [-1] * num_of_node
        self.ranks = [1] * num_of_node
        self.groups = num_of_node

    def get_root(self, node):
        root = self.roots[node]
        if root == -1:
            return node

        else:
            root = self.get_root(root)
            self.roots[node] = root
            return root

    def is_same_group(self, node1, node2):
        return self.get_root(node1) == self.get_root(node2)

    def unite(self, node1, node2):
        self.groups -= 1
        root1, root2 = self.get_root(node1), self.get_root(node2)
        rank1, rank2 = self.ranks[root1], self.ranks[root2]
        if rank1 < rank2:
            root1, root2 = root2, root1

        self.roots[root2] = root1
        self.ranks[root2] += self.ranks[root1]


def main():
    n = int(buf.readline())
    XY = map(int, buf.read().split())
    Xs = []
    Ys = []
    for i, (x, y) in enumerate(zip(XY, XY)):
        Xs.append((x-1, i))
        Ys.append((y-1, i))

    Xs.sort()
    Ys.sort()

    edges = []
    for i, ((x, node), (nx, new_node)) in enumerate(zip(Xs[:-1], Xs[1:])):
        edges.append((nx-x, node, new_node))

    for i, ((y, node), (ny, new_node)) in enumerate(zip(Ys[:-1], Ys[1:])):
        edges.append((ny-y, node, new_node))

    edges.sort(reverse=True)

    ans = 0
    uf = UnionFind(n)
    while uf.groups != 1:
        d, node1, node2 = edges.pop()
        if uf.is_same_group(node1, node2):
            continue
        uf.unite(node1, node2)
        ans += d

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop
buf = sys.stdin.buffer


def main():
    n = int(buf.readline())
    XY = map(int, buf.read().split())
    Xs = []
    Ys = []
    for i, (x, y) in enumerate(zip(XY, XY)):
        Xs.append((x-1, i))
        Ys.append((y-1, i))

    Xs.sort()
    Ys.sort()

    edges = [[] for _ in range(n)]
    for i, ((x, node), (nx, new_node)) in enumerate(zip(Xs[:-1], Xs[1:])):
        edges[node].append((nx-x, new_node))
        edges[new_node].append((nx-x, node))

    for i, ((y, node), (ny, new_node)) in enumerate(zip(Ys[:-1], Ys[1:])):
        edges[node].append((ny-y, new_node))
        edges[new_node].append((ny-y, node))

    seen = [False] * n
    dist = [float('INF')] * n
    todo = [(0, 0)]

    while todo:
        d, node = heappop(todo)
        if seen[node]:
            continue
        seen[node] = True
        dist[node] = d

        while edges[node]:
            edge = edges[node].pop()
            nd, to = edge
            if dist[to] <= nd:
                continue
            heappush(todo, (nd, to))

    print(sum(dist))


if __name__ == "__main__":
    main()

Submission status: Accepted

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


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

Xs.sort()
Ys.sort()

edges = [[] for _ in range(n)]
for i in range(n-1):
    x, node = Xs[i]
    nx, new_node = Xs[i+1]
    edges[node].append((nx-x, new_node))
    edges[new_node].append((nx-x, node))

for i in range(n-1):
    y, node = Ys[i]
    ny, new_node = Ys[i+1]
    edges[node].append((ny-y, new_node))
    edges[new_node].append((ny-y, node))

seen = [False] * n
dist = [float('INF')] * n
todo = [(0, 0)]

while todo:
    d, node = heapq.heappop(todo)
    if seen[node]:
        continue
    seen[node] = True
    dist[node] = d

    for edge in edges[node]:
        nd, to = edge
        if dist[to] <= nd:
            continue
        heapq.heappush(todo, (nd, to))

print(sum(dist))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    XY = [[int(i) for i in input().split()] for j in range(N)]
    X = sorted([(xy[0], xy[1], i) for i, xy in enumerate(XY)])
    Y = sorted(X, key=lambda p: p[1])
    edges = []
    for i in range(N-1):
        (x1, y1, a) = X[i]
        (x2, y2, b) = X[i+1]
        cost = min(abs(x1-x2), abs(y1-y2))
        edges.append((cost, a, b))

    for i in range(N-1):
        (x1, y1, a) = Y[i]
        (x2, y2, b) = Y[i+1]
        cost = min(abs(x1-x2), abs(y1-y2))
        edges.append((cost, a, b))

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

    def find_root(x):
        if par[x] == x:
            return x
        else:
            par[x] = find_root(par[x])
            return par[x]

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

    def unite(x, y):
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            x, y = y, x
        rank[x] += rank[y]
        par[y] = x

    def size(x):
        return rank[find_root(x)]

    edges.sort()

    ans = 0
    for (c, a, b) in edges:
        if find_root(a) != find_root(b):
            ans += c
            unite(a, b)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
# list(map(int, input().split()))

class UnionFind(object):
    def __init__(self, n = 1):
        self.link = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.link[x] == x:
            return x

        # re-connect union find to make the height of tree lower
        # you can use while, but recursion makes it easier to reconnect
        self.link[x] = self.find(self.link[x])
        return self.link[x]

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

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

        if self.size[x] < self.size[y]:
            x, y = y, x
        self.link[y] = x
        self.size[x] += self.size[y]
    
    def get_size(self, x):
        x = self.find(x)
        return self.size[x]


N = int(input())

townsX = [0] * N
townsY = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    townsX[i] = (x - 1, y - 1, i)
    townsY[i] = (y - 1, x - 1, i)
townsX = sorted(townsX)
townsY = sorted(townsY)

edges = []
for i in range(1, N):
    a = townsX[i]
    b = townsX[i - 1]
    c = townsY[i]
    d = townsY[i - 1]
    e1 = (abs(a[0] - b[0]), a[2], b[2])
    e2 = (abs(c[0] - d[0]), c[2], d[2])
    edges.append(e1)
    edges.append(e2)
edges = sorted(edges)

u = UnionFind(N)


ans = 0
for e in edges:
    w, s, t = e
    if u.is_same(s, t):
        continue
    u.unite(s, t)
    ans += w
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
n = int(input())
xy = []
for i in range(n):
    x, y = map(int, input().split())
    xy.append((i, x, y))
xx = sorted(xy, key=lambda x:x[1])
yy = sorted(xy, key=lambda x:x[2])
li = []
for i in range(n-1):
    li.append((xx[i][0], xx[i+1][0], xx[i+1][1]-xx[i][1]))
    li.append((yy[i][0], yy[i+1][0], yy[i+1][2]-yy[i][2]))
li.sort(key=lambda x:x[2])
class UnionFind():
    def __init__(self, li):
        self.li = li
    def root(self, x):
        if self.li[x]==x:
            return x
        self.li[x] = self.root(self.li[x])
        return self.li[x]
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx==ry:
            return
        self.li[ry] = rx
    def same(self, x, y):
        return self.root(x)==self.root(y)
uf = UnionFind(list(range(n)))
ans = 0
for x, y, cost in li:
    if uf.same(x, y):
        continue
    uf.unite(x, y)
    ans += cost
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
N = int(input())
xy = [list(map(int,input().split())) for i in range(N)]
x,y = zip(*xy)

#import random
#N = 200000
#x = [random.randint(0,10**9) for i in range(N)]
#y = [random.randint(0,10**9) for i in range(N)]

def Prim(g,cost):
    h = []
    N = len(g.keys())
    visited = [False]*(N+1)
    visited[1] = True
    v = 1
    for nv in g[v]:
        heappush(h, (cost[(v,nv)], (v,nv)))
    res = []
    d = 0
    while True:
        c, (v,nv) = heappop(h)
        if visited[nv]:
            continue
        res.append((v,nv))
        d += c
        if len(res) == N-1:
            break
        visited[nv] = True
        for nnv in g[nv]:
            if not visited[nnv]:
                heappush(h, (cost[(nv,nnv)], (nv,nnv)))
    return res, d

xi = [(x,i+1) for i,x in enumerate(x)]
yi = [(y,i+1) for i,y in enumerate(y)]

xi.sort()
yi.sort()

diffx = [(x1-x0,i0,i1) for (x0,i0),(x1,i1) in zip(xi,xi[1:])]
diffy = [(y1-y0,i0,i1) for (y0,i0),(y1,i1) in zip(yi,yi[1:])]

g = defaultdict(set)
cost = defaultdict(lambda : 10**10)
for d,i0,i1 in diffx:
    g[i0].add(i1)
    g[i1].add(i0)
    cost[(i0,i1)] = min(cost[(i0,i1)],d)
    cost[(i1,i0)] = min(cost[(i0,i1)],d)
for d,i0,i1 in diffy:
    g[i0].add(i1)
    g[i1].add(i0)
    cost[(i0,i1)] = min(cost[(i0,i1)],d)
    cost[(i1,i0)] = min(cost[(i0,i1)],d)

res,ans = Prim(g,cost)
print(ans)

Submission status: Accepted

Solution code:
# ABC065D

import sys
input=sys.stdin.readline
import heapq

class UnionFind:
    def __init__(self, n):
        self.p=[-1]*n
        self.size=[1]*n
    def root(self, x):
        st=set()
        while(self.p[x]>=0):
            st.add(x)
            x=self.p[x]
        for y in st:
            self.p[y]=x
        return x
    def find(self, x, y):
        return self.root(x)==self.root(y)
    def union(self, x, y):
        r1=self.root(x)
        r2=self.root(y)
        if r1==r2:
            return
        p1=self.p[r1]
        p2=self.p[r2]
        if p1<=p2:
            self.p[r2]=r1
            self.size[r1]+=self.size[r2]
            if p1==p2:
                self.p[r1]-=1
        else:
            self.p[r1]=r2
            self.size[r2]+=self.size[r1]

def main():
    N=int(input())
    r=[tuple([i]+list(map(int,input().split()))) for i in range(N)]
    rx=sorted(r,key=lambda x:x[1])
    ry=sorted(r,key=lambda x:x[2])
    pq=[]
    for i in range(1,N):
        dx=abs(rx[i][1]-rx[i-1][1])
        heapq.heappush(pq,(dx,rx[i][0],rx[i-1][0]))
        dy=abs(ry[i][2]-ry[i-1][2])
        heapq.heappush(pq,(dy,ry[i][0],ry[i-1][0]))
    uft=UnionFind(N)
    ans=0
    while(uft.size[uft.root(0)]<N):
        e=heapq.heappop(pq)
        if not(uft.find(e[1],e[2])):
            ans+=e[0]
            uft.union(e[1],e[2])
    print(ans)
    
if __name__=="__main__":
    main()

Submission status: Accepted

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

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

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

import copy
N = int(input())
A = [0] * N
for i in range(N):
  a, b = map(int, input().split())
  A[i] = [i, a, b]

B = copy.deepcopy(A)  
A = sorted(A, key = lambda x:x[1])
B = sorted(B, key = lambda x:x[2])
#print(A, B)

#それぞれの辺のながさを求めて、小さい順にする
#[点の番号、点の番号、２点間距離]
A2 = [0] * (N - 1)
for i in range(1, N):
  l = abs(A[i][1] - A[i - 1][1])
  A2[i - 1] = [A[i][0], A[i - 1][0], l]

B2 = [0] * (N - 1)
for i in range(1, N):
  l = abs(B[i][2] - B[i - 1][2])
  B2[i - 1] = [B[i][0], B[i - 1][0], l]  
Len = A2 + B2
Len = sorted(Len, key = lambda x:x[2])
#print(Len)

data = UnionFind(N + 1)
cost = 0
for i in range(len(Len)):
    if not data.same_check(Len[i][0], Len[i][1]):
      data.union(Len[i][0], Len[i][1])
      cost += Len[i][2]

  
print(cost)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
from scipy.sparse import csr_matrix
import numpy as np

N = int(input())

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

edge = set()
for key in [itemgetter(1),itemgetter(2)]:
  XY.sort(key = key)
  for i in range(N-1):
    i1,x1,y1 = XY[i]
    i2,x2,y2 = XY[i+1]
    d = min(abs(x1-x2),abs(y1-y2))
    edge.add((i1,i2,d))
    
row,col,value = zip(*edge)
value = np.array(value,dtype=int)
graph = csr_matrix((value,(row,col)),shape=(N,N))

from scipy.sparse.csgraph import minimum_spanning_tree
tree = minimum_spanning_tree(graph, overwrite = True).astype(int)
answer = tree.sum()
print(answer)

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy


class UnionFind:

    def __init__(self, n: int):
        self._n = n
        self._parents = [i for i in range(n)]
        self._rank = [1 for _ in range(n)]

    def unite(self, x: int, y: int) -> None:
        px = self.find(x)
        py = self.find(y)

        # 一致していないときはリンクをつける
        if px != py:
            self._link(px, py)

    def _link(self, x: int, y: int):
        if self._rank[x] < self._rank[y]:
            self._parents[x] = y
        elif self._rank[x] > self._rank[y]:
            self._parents[y] = x
        else:
            self._parents[x] = y
            self._rank[y] += 1

    def same(self, x: int, y: int) -> bool:
        px = self.find(x)
        py = self.find(y)
        return px == py

    def find(self, x: int) -> int:
        if self._parents[x] == x:
            return x

        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]


N = int(input())
ps = [list(map(int, input().split())) + [i] for i in range(N)]
ps.sort(key=lambda t: t[0])
xs = []
for i in range(N - 1):
    xs.append((ps[i + 1][0] - ps[i][0], ps[i][2], ps[i + 1][2]))

ps.sort(key=lambda t: t[1])
ys = []
for i in range(N - 1):
    ys.append((ps[i + 1][1] - ps[i][1], ps[i][2], ps[i + 1][2]))

xs += [(1<< 40, -1, -1)]
ys += [(1<< 40, -1, -1)]

xs.sort()
ys.sort()

xc, yc = 0, 0
uf = UnionFind(N)

ans = 0
while xc < N - 1 and yc < N - 1:
    if xs[xc][0] < ys[yc][0]:
        if not uf.same(xs[xc][1], xs[xc][2]):
            uf.unite(xs[xc][1], xs[xc][2])
            ans += xs[xc][0]
        xc += 1
    else:
        if not uf.same(ys[yc][1], ys[yc][2]):
            uf.unite(ys[yc][1], ys[yc][2])
            ans += ys[yc][0]
        yc += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
machi = []
li_x = []
li_y = []
for i in range(n):
    x, y = map(int, input().split())
    li_x.append((x, i))
    li_y.append((y, i))
    machi.append((x, y, i))
li_x.sort()
li_y.sort()
edge = [[] for _ in range(n)]
for i in range(n-1):
    edge[li_x[i][1]].append((li_x[i+1][0]-li_x[i][0], li_x[i+1][1]))
    edge[li_x[i+1][1]].append((li_x[i+1][0]-li_x[i][0], li_x[i][1]))
    edge[li_y[i][1]].append((li_y[i+1][0]-li_y[i][0], li_y[i+1][1]))
    edge[li_y[i+1][1]].append((li_y[i+1][0]-li_y[i][0], li_y[i][1]))

import heapq
def prim_heap(edge, n):
    used = [True] * n # True ：　不使用husiyou
    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
print(prim_heap(edge, n))

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())
    
import heapq    
    
n = int(input())
a = []
b = []
for i in range(n):
    x,y= map(int, input().split())
    a.append((x,y,i))
    b.append((y,x,i))
a.sort()
b.sort()
edgea = []
edgeb = []
for i in range(n-1):
    edgea.append((a[i+1][0]-a[i][0],a[i][2],a[i+1][2]))
    edgeb.append((b[i+1][0]-b[i][0],b[i][2],b[i+1][2]))
edge = edgea+edgeb
heapq.heapify(edge)

uf = UnionFind(n)
ans = 0
while len(edge):
    x,y,z = heapq.heappop(edge)
    if not uf.same(y,z):
        ans += x
        uf.union(y,z)
print(ans)