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 bisect
import collections
import sys
import heapq

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 32


class UnionFind(object):
    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 members_dict(self):
        pass

    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 lmi():
    return list(map(int, input().split()))


def llmi_index(n):
    return [[i] + lmi() for i in range(n)]


N = int(input())
XY = llmi_index(N)
x_sorted = sorted(XY, key=lambda v: v[1])
y_sorted = sorted(XY, key=lambda v: v[2])
# print(x_sorted)
# # print(y_sorted)

uf = UnionFind(N)
cost_hq = []  # cost , index,index
for i in range(N - 1):
    cost = x_sorted[i + 1][1] - x_sorted[i][1]
    heapq.heappush(cost_hq, (cost, x_sorted[i][0], x_sorted[i + 1][0]))
for i in range(N - 1):
    cost = y_sorted[i + 1][2] - y_sorted[i][2]
    heapq.heappush(cost_hq, (cost, y_sorted[i][0], y_sorted[i + 1][0]))

ans = 0
while cost_hq:
    cost, index1, index2 = heapq.heappop(cost_hq)
    # print(cost, index1, index2)
    if uf.same(index1, index2):
        continue
    # print('join {},{}'.format(index1,index2))
    uf.union(index1, index2)
    ans += cost

print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
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((abs(x[i][0]-x[i+1][0]),x[i][1],x[i+1][1]))
  edges.append((abs(y[i][0]-y[i+1][0]),y[i][1],y[i+1][1]))
edges.sort()
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 kruskal(n, edges):#edges: wでソート済み
    uf = UnionFind(n)
    res = 0
    for e in edges:
        w, s, t = e
        if not uf.same(s, t):
            res+=w
            uf.union(s, t)
    return res
print(kruskal(n, edges))

Submission status: Accepted

Solution code:
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 [u, fr], [v, to] in zip(x_list, x_list[1:]):
  stw += [[abs(u-v), fr, to]]
for [u, fr], [v, to] in zip(y_list, y_list[1:]):
  stw += [[abs(u-v), fr, to]]

stw = sorted(stw, key=lambda x:x[0])

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を小さい順にソートされたものとする
  res = 0
  uf = UnionFind(n)
  #while stw:
  for i in range(len(stw)):
    #w, s, t = heapq.heappop(stw)
    w, s, t = stw[i]
    if not uf.isSameGroup(s, t):
      uf.Unite(s, t)
      res += w
  return res

print(kruskal())

Submission status: Accepted

Solution code:
import itertools
import heapq
from heapq import heappush, heappop
global G, inp_x, inp_y

def input_graph(N):
  global G, inp_x, inp_y
  inp_x = []
  inp_y = []
  for i in range(N):
    x, y = map(int, input().split())
    inp_x.append((x, i))
    inp_y.append((y, i))
  inp_x.sort()
  inp_y.sort()
  for i in range(N-1):
    xa = inp_x[i][1]
    xb = inp_x[i+1][1]
    ya = inp_y[i][1]
    yb = inp_y[i+1][1]
    cost_x = abs(inp_x[i][0]-inp_x[i+1][0])
    cost_y = abs(inp_y[i][0]-inp_y[i+1][0])
    G[xa] += [(cost_x, xb)]
    G[xb] += [(cost_x, xa)]
    G[ya] += [(cost_y, yb)]
    G[yb] += [(cost_y, ya)]

  
def prim(V):
  global G, used
  edgelist = []
  for e in G[0]:
    heappush(edgelist, e)
  used[0] = True
  res = 0
  while edgelist:
    minedge = heappop(edgelist)
    if used[minedge[1]]:
      continue 
    v = minedge[1]
    used[v] = True 
    for e in G[v]:
      if not used[e[1]]:
        heappush(edgelist, e)
    res += minedge[0]
  return res

def main():
  global G, used
  N = int(input())
  G = [[] for _ in range(N)]
  used = [False for _ in range(N)]
  input_graph(N)
  print(prim(N))

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from heapq import heappop, heapify
import sys
input = sys.stdin.buffer.readline

class UnionFind :
    """
    Union Find木
    ---
    頂点のインデックスは0~

    Attributes
    ---
    parent : list<int>
        親のリスト．parent[頂点のインデックス] = 親のインデックス
    height : list<int>
        各木の高さ
    size : list<int>
        各木の頂点数
    component : int
        連結成分の数
    """

    def __init__(self, size) :
        """
        Parameters
        ---
        size : int
            頂点数
        """
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        """
        親のインデックスの取得

        Parameters
        ---
        index : int
            取得する頂点のインデックス

        Returns
        ---
        rootIndex : int
            指定した頂点の根のインデックス
        """
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        """
        木の結合

        Parameters
        ---
        index1 : int
        index2 : int
            結合する頂点のインデックス
        """
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        """
        同じ木に属するかを判定する

        Parameters
        ---
        index1 : int
        index2 : int

        Returns
        ---
        boolean
        """
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        """
        指定した頂点の属する木の大きさを取得する
        """
        return self.size[self.root(index)]

    def getComponent(self) :
        """
        連結成分数を取得する
        """
        return self.component

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 (u, fr), (v, to) in zip(X, X[1:]):
    edges.append((abs(u - v), fr, to,))
for (u, fr), (v, to) in zip(Y, Y[1:]):
    edges.append((abs(u - v), fr, to,))

heapify(edges)
tree = UnionFind(N)
ans = 0
while edges:
    cost, fr, to = heappop(edges)
    if not tree.isSameRoot(fr, to):
        ans += cost
        tree.union(fr, to)

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 1000000007

    N = int(input())
    xy = []
    for i in range(N):
        x,y = map(int, input().split())
        xy.append([x, y, i])
    x_sort = sorted(xy, key=lambda x: x[0])
    y_sort = sorted(xy, key=lambda x: x[1])

    #[cost, 頂点1, 頂点2]
    cost = []
    for i in range(N-1):
        cost.append([x_sort[i+1][0]-x_sort[i][0], x_sort[i][2], x_sort[i+1][2]])
        cost.append([y_sort[i+1][1]-y_sort[i][1], y_sort[i][2], y_sort[i+1][2]])
    cost.sort()
    #cost = sorted(cost, key=lambda x: x[0])

    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 par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True
    
    def same(x,y):
        return find(x) == find(y)

    par = [-1]*N

    res = 0
    for c, v1, v2 in cost:
        if not same(v1, v2):
            unite(v1, v2)
            res += c
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 1000000007

    N = int(input())
    xy = []
    for i in range(N):
        x,y = map(int, input().split())
        xy.append([x, y, i])
    x_sort = sorted(xy, key=lambda x: x[0])
    y_sort = sorted(xy, key=lambda x: x[1])

    #[cost, 頂点1, 頂点2]
    cost = []
    for i in range(N-1):
        cost.append([x_sort[i+1][0]-x_sort[i][0], x_sort[i][2], x_sort[i+1][2]])
        cost.append([y_sort[i+1][1]-y_sort[i][1], y_sort[i][2], y_sort[i+1][2]])
    cost = sorted(cost, key=lambda x: x[0])

    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 par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True
    
    def same(x,y):
        return find(x) == find(y)

    par = [-1]*N

    res = 0
    for c, v1, v2 in cost:
        if not same(v1, v2):
            unite(v1, v2)
            res += c
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''
https://atcoder.jp/contests/abc065/tasks/arc076_b
最小全域木を考える際にある頂点について他の頂点への最小コストを
考えて繋げていくのは間違い(全域木になる保証がない)
考えたいのはあくまでも全辺のコスト

今回はxとyでそれぞれソートして隣り合う2点のコストのみを考えれば良い
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 1000000007

    N = int(input())
    xy = []
    for i in range(N):
        x,y = map(int, input().split())
        xy.append([x, y, i])
    x_sort = sorted(xy, key=lambda x: x[0])
    y_sort = sorted(xy, key=lambda x: x[1])

    #[cost, 頂点1, 頂点2]
    cost = []
    for i in range(N-1):
        cost.append([abs(x_sort[i][0]-x_sort[i+1][0]), x_sort[i][2], x_sort[i+1][2]])
        cost.append([abs(y_sort[i][1]-y_sort[i+1][1]), y_sort[i][2], y_sort[i+1][2]])
    cost = sorted(cost, key=lambda x: x[0])

    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 par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True
    
    def same(x,y):
        return find(x) == find(y)

    par = [-1]*N

    res = 0
    for c, v1, v2 in cost:
        if not same(v1, v2):
            unite(v1, v2)
            res += c
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

def find(x):
    if parents[x] < 0:
        return x
    else:
        parents[x] = find(parents[x])
        return parents[x]

def union(x, y):

    x = find(x)
    y = find(y)

    if x == y:
        return

    if parents[x] > parents[y]:
        x,y = y,x

    parents[x] += parents[y]
    parents[y] = x

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

N = int(input())

parents = [-1] * N
ver_x = []
ver_y = []
for i in range(N):
    x,y = map(int, input().split())
    ver_x.append((x,i))
    ver_y.append((y,i))

ver_x.sort()
ver_y.sort()

edge_list = []

for i in range(N-1):
    x_dist = ver_x[i+1][0]-ver_x[i][0]
    y_dist = ver_y[i+1][0]-ver_y[i][0]

    edge_list.append((x_dist, ver_x[i+1][1], ver_x[i][1]))
    edge_list.append((y_dist, ver_y[i+1][1], ver_y[i][1]))

ans = 0

edge_list.sort()

for w,s,t in edge_list:
    if not same(s,t):
        union(s,t)
        ans += w
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

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

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    n = I()
    p = LIR(n)
    for i in range(n):
        p[i].append(i)
    p.sort()
    v = []
    for i in range(n-1):
        x,y,c = p[i]
        a,b,d = p[i+1]
        v.append((min(abs(x-a),abs(y-b)),c,d))
    p.sort(key = lambda x:x[1])
    for i in range(n-1):
        x,y,c = p[i]
        a,b,d = p[i+1]
        v.append((min(abs(x-a),abs(y-b)),c,d))
    v.sort()
    par = [i for i in range(n)]
    rank = [0]*n
    ans = 0
    s = 1
    for c,a,b in v:
        if root(a) != root(b):
            ans += c
            s += 1
            if s >= n:
                break
            unite(a,b)
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

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

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    n = I()
    p = LIR(n)
    for i in range(n):
        p[i].append(i)
    p.sort()
    v = []
    for i in range(n-1):
        x,y,c = p[i]
        a,b,d = p[i+1]
        v.append((min(abs(x-a),abs(y-b)),c,d))
    p.sort(key = lambda x:x[1])
    for i in range(n-1):
        x,y,c = p[i]
        a,b,d = p[i+1]
        v.append((min(abs(x-a),abs(y-b)),c,d))
    v.sort()
    par = [i for i in range(n)]
    rank = [0]*n
    ans = 0
    s = 0
    for c,a,b in v:
        if root(a) != root(b):
            ans += c
            s += 1
            if s >= n:
                break
            unite(a,b)
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

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

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    n = I()
    p = LIR(n)
    for i in range(n):
        p[i].append(i)
    p.sort()
    v = []
    for i in range(n-1):
        x,y,c = p[i]
        a,b,d = p[i+1]
        v.append((min(abs(x-a),abs(y-b)),c,d))
    p.sort(key = lambda x:x[1])
    for i in range(n-1):
        x,y,c = p[i]
        a,b,d = p[i+1]
        v.append((min(abs(x-a),abs(y-b)),c,d))
    v.sort()
    par = [i for i in range(n)]
    rank = [0]*n
    ans = 0
    for c,a,b in v:
        if root(a) != root(b):
            ans += c
            unite(a,b)
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

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

u, v, c = zip(*edge)

graph = csr_matrix((c, (u, v)), shape=(n, n))
mst = minimum_spanning_tree(graph, overwrite=True).astype(int)
ans = mst.sum()
print(ans)

Submission status: Accepted

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

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

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

u, v, c = zip(*edge)

graph = csr_matrix((c, (u, v)), shape=(n, n), dtype=int)
mst = minimum_spanning_tree(graph, overwrite=True).astype(int)
ans = mst.sum()
print(ans)

Submission status: Accepted

Solution code:
class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
import sys
input=sys.stdin.readline
n=int(input())
l=[tuple(map(int,input().split())) for i in range(n)]
l.sort()
import collections
d=collections.defaultdict(int)
j=1
for i in l:
    if d[i]==0:
        d[i]=j
        j+=1
pq=[]
for i in range(n-1):
    pq.append((l[i+1][0]-l[i][0],d[l[i]],d[l[i+1]]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
    pq.append((l[i+1][1]-l[i][1],d[l[i]],d[l[i+1]]))
ans=0
pq.sort()
uf=unionfind(n)
for c,x,y in pq:
    if not uf.same(x,y):
        ans+=c
        uf.unite(x,y)
print(ans)

Submission status: Accepted

Solution code:
class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
import sys
input=sys.stdin.readline
n=int(input())
l=[tuple(map(int,input().split())) for i in range(n)]
l.sort()
import collections
d=collections.defaultdict(int)
j=1
for i in l:
    if d[i]==0:
        d[i]=j
        j+=1
pq=[]
for i in range(n-1):
    pq.append((l[i+1][0]-l[i][0],d[l[i]],d[l[i+1]]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
    pq.append((l[i+1][1]-l[i][1],d[l[i]],d[l[i+1]]))
ans=0
pq.sort(key=lambda x:x[0])
uf=unionfind(n)
for c,x,y in pq:
    if not uf.same(x,y):
        ans+=c
        uf.unite(x,y)
print(ans)

Submission status: Accepted

Solution code:
class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
import sys
input=sys.stdin.readline
n=int(input())
l=[tuple(map(int,input().split())) for i in range(n)]
l.sort(key=lambda x:x[0])
import collections
d=collections.defaultdict(int)
j=1
for i in l:
    if d[i]==0:
        d[i]=j
        j+=1
pq=[]
for i in range(n-1):
    pq.append((l[i+1][0]-l[i][0],d[l[i]],d[l[i+1]]))
l.sort(key=lambda x:x[1])
for i in range(n-1):
    pq.append((l[i+1][1]-l[i][1],d[l[i]],d[l[i+1]]))
ans=0
pq.sort(key=lambda x:x[0])
uf=unionfind(n)
for c,x,y in pq:
    if not uf.same(x,y):
        ans+=c
        uf.unite(x,y)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, x: "List[int]", y: "List[int]"):
    par = [-1] * N

    def getroot(a: int):
        if par[a] != -1:
            par[a] = getroot(par[a])
            return par[a]
        else:
            return a

    def union(a: int, b: int):
        par[getroot(b)] = getroot(a)

    xpts = sorted((xi, i) for i, xi in enumerate(x))
    ypts = sorted((yi, i) for i, yi in enumerate(y))
    edges = [
        (xj - xi, i, j) for (xi, i), (xj, j) in zip(xpts, xpts[1:])
    ] + [
        (yj - yi, i, j) for (yi, i), (yj, j) in zip(ypts, ypts[1:])
    ]
    edges.sort()
    ans = 0
    for cost, i, j in edges:
        if getroot(i) == getroot(j):
            continue
        union(i, j)
        ans += cost
    print(ans)


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve_abc065d():
    from collections import namedtuple
    from heapq import heappush, heappop
    from operator import attrgetter
    from itertools import tee
    import sys

    input = sys.stdin.readline

    City = namedtuple('City', 'x y idx')
    Edge = namedtuple('Edge', 'cost to')
    N = int(input())

    cities = []
    for city_idx in range(N):
        x, y = map(int, input().split())
        c_ = City(x, y, city_idx)
        cities.append(c_)
    cities_x_asc = sorted(cities, key=attrgetter('x'))
    cities_y_asc = sorted(cities, key=attrgetter('y'))

    graph = tuple(set() for _ in range(N))

    it_x = iter(cities_x_asc)
    gx1, gx2 = tee(it_x, 2)
    next(gx2)
    for c1, c2 in zip(gx1, gx2):
        d_ = c2.x - c1.x
        graph[c1.idx].add(Edge(d_, c2.idx))
        graph[c2.idx].add(Edge(d_, c1.idx))
    # x方向にN-1本の辺を張る

    it_y = iter(cities_y_asc)
    gy1, gy2 = tee(it_y, 2)
    next(gy2)
    for c1, c2 in zip(gy1, gy2):
        d_ = c2.y - c1.y
        graph[c1.idx].add(Edge(d_, c2.idx))
        graph[c2.idx].add(Edge(d_, c1.idx))
    # y方向にN-1本の辺を張る

    # <Prim’s Algorithm>
    # https://tjkendev.github.io/procon-library/python/graph/min_st_prim.html
    # プリム法では、グラフGの1頂点からなる木から始め、
    # 木に含まれる頂点と木に含まれない頂点を繋ぐ辺のうち、
    # 一番コストが小さい辺が繋ぐ(木に含まれない方の)頂点を木に追加する、
    # ことを繰り返すことで最小全域木を求める。
    # G[v] = [w, ...]
    #     グラフG上で頂点vが隣接する辺集合

    start = 0  # 起点とする頂点

    used = [-1] * N
    used[start] = 1

    h = []
    for e_ in graph[start]:
        heappush(h, e_)

    mi = 0
    while h:
        e_ = heappop(h)
        if ~used[e_.to]: continue

        used[e_.to] = 1
        mi += e_.cost

        for ne_ in graph[e_.to]:
            if ~used[ne_.to]: continue
            heappush(h, ne_)

    # miが最小全域木の解

    print(mi)
    return


if __name__ == '__main__':
    solve_abc065d()