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 numpy as np

def solve(n, x, y):
    def dist(i, j):
        return min(abs(x[i]-x[j]), abs(y[i]-y[j]))
    que = []
    for p in map(np.argsort, [x, y]):
        for i in range(n-1):
            u, v = p[i], p[i+1]
            que.append((u, v, dist(u, v)))
    parent = [i for i in range(n)]
    def find(i):
        if parent[i] == i:
            return i
        else:
            j = find(parent[i])
            parent[i] = j
            return j
    ans = 0
    for u, v, d in sorted(que, key=lambda _: _[2]):
        u = find(u)
        v = find(v)
        if u != v:
            ans += d
            if u > v:
                u, v = v, u
            parent[v] = u
    return ans

n = int(input())
x = np.zeros(n, dtype=int)
y = np.zeros(n, dtype=int)
for i in range(n):
    x[i], y[i] = map(int, input().split())
print(solve(n, x, y))

Submission status: Accepted

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

from operator import itemgetter
margin = []
XY.sort(key = itemgetter(1))

for j in range(n-1):
    margin.append([XY[j][0],XY[j+1][0],XY[j+1][1]-XY[j][1]])

XY.sort(key = itemgetter(2))
for j in range(n-1):
    margin.append([XY[j][0],XY[j+1][0],XY[j+1][2]-XY[j][2]])

margin.sort(key = itemgetter(2))
def search(UF,loc):
    if UF[loc] == loc:
        return UF[loc]
    else:
        UF[loc] = search(UF,UF[loc])
        return UF[loc]
UF = [k for k in range(n+1)]
count = 1
ans = 0
for p,q,m in margin:
        if count == n:
            break
        UF[p] = search(UF,p)
        UF[q] = search(UF,q)
        if UF[p] != UF[q]:
            ans += m
            UF[max(UF[p],UF[q])] = min(UF[p],UF[q])
            count += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

def MST(n, E):
    def par(m):
        if UF[m] == m:
            return m
        ret = par(UF[m])
        UF[m] = ret
        return ret
    
    UF = [i for i in range(n)]
    E = sorted(E, key=lambda x: x[2])
    ans = 0
    for i, j, d in E:
        if par(i) != par(j):
            ans += d
            UF[par(i)] = par(j)
    return ans

N = int(input())

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

F = []
Y = sorted(X, key = lambda x: x[1])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][1]-Y[i][1])))

Y = sorted(X, key = lambda x: x[2])
for i in range(len(Y)-1):
    F.append((Y[i][0], Y[i+1][0], abs(Y[i+1][2]-Y[i][2])))

print(MST(N, F))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
Edge=[[] for i in range(n)]
XY=[]
append=XY.append
for i in range(n):
  x,y=map(int,input().split())
  append([i,x,y])
XY.sort(key=lambda x:x[1])
for i in range(1,n):
  n1,x1,y1=XY[i-1][0],XY[i-1][1],XY[i-1][2]
  n2,x2,y2=XY[i][0],XY[i][1],XY[i][2]
  Edge[n1].append([min(abs(x2-x1),abs(y2-y1)),n2])
  Edge[n2].append([min(abs(x2-x1),abs(y2-y1)),n1])
XY.sort(key=lambda x:x[2])
for i in range(1,n):
  n1,x1,y1=XY[i-1][0],XY[i-1][1],XY[i-1][2]
  n2,x2,y2=XY[i][0],XY[i][1],XY[i][2]
  Edge[n1].append([min(abs(x2-x1),abs(y2-y1)),n2])
  Edge[n2].append([min(abs(x2-x1),abs(y2-y1)),n1])
import heapq
def prim_heap():
  used=[True]*n
  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())

Submission status: Accepted

Solution code:
import sys
import heapq
input = sys.stdin.readline
N = int(input())
XYI = sorted([[int(_) for _ in input().split()] + [_] for _ in range(N)])
visited = [False] * N
H = []
for j in range(N - 1):
    heapq.heappush(H, (XYI[j + 1][0] - XYI[j][0], XYI[j][2], XYI[j + 1][2]))
XYI.sort(key=lambda xs: xs[1])
for j in range(N - 1):
    heapq.heappush(H, (XYI[j + 1][1] - XYI[j][1], XYI[j + 1][2], XYI[j][2]))
ans = 0

UF = list(range(N + 1))
SIZE = [0] + [1] * N  # 1-indexed


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    if not is_same(x, y):
        X, Y = find(x), find(y)
        SX, SY = SIZE[X], SIZE[Y]
        if SX > SY:
            m = UF[X] = Y
        else:
            m = UF[Y] = X
        SIZE[m] = SX + SY
        SIZE[X + Y - m] = 0


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


def scan_uf():
    for i in range(len(UF)):
        find(i)


while H:
    d, i1, i2 = heapq.heappop(H)
    if not is_same(i1, i2):
        unite(i1, i2)
        ans += d
print(ans)

Submission status: Accepted

Solution code:
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

X = np.array(X)
Y = np.array(Y)
Xargs = X.argsort()
Yargs = Y.argsort()

# X 座標上または Y 座標上で隣り合わないやつは隣り合うやつをたどっていけるので考えなくていい
graph = [[] for _ in range(N)]
for v, u in zip(Xargs[:-1], Xargs[1:]):
    graph[v].append((abs(X[v] - X[u]), u))
    graph[u].append((abs(X[v] - X[u]), v))
for v, u in zip(Yargs[:-1], Yargs[1:]):
    graph[v].append((abs(Y[v] - Y[u]), u))
    graph[u].append((abs(Y[v] - Y[u]), v))

heap = graph[0]
heapq.heapify(heap)
fixed = np.zeros(N, dtype=bool)
fixed[0] = True

cnt = 1
ans = 0
while cnt < N:
    dist, v = heapq.heappop(heap)
    if fixed[v]:
        continue
    fixed[v] = True
    cnt += 1
    ans += dist
    for d, u in graph[v]:
        if fixed[u]:
            continue
        heapq.heappush(heap, (d, u))

print(ans)

Submission status: Accepted

Solution code:
class Kruskal_UnionFind():
    def __init__(self, N):
        self.edges = []
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

    def add(self, u, v, d):
        """
        u = from, v = to, d = cost
        """
        self.edges.append([u, v, d])

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        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 size(self, x):
        x = self.find(x)
        return self.counter[x]

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

    def Kruskal(self):
        """
        return: 最小全域木のコストの和
        """
        edges = sorted(self.edges, key=lambda x: x[2])  # costでself.edgesをソートする
        res = 0
        for e in edges:
            if not self.same(e[0], e[1]):
                self.unite(e[0], e[1])
                res += e[2]
        return res
N = int(input())
G = Kruskal_UnionFind(N)
x = []
y = []
for i in range(N):
    xx,yy = map(int,input().split())
    x.append([i,xx])
    y.append([i,yy])

x = sorted(x,key=lambda t:t[1])
y = sorted(y,key=lambda t:t[1])

for i in range(N-1):
    G.add(x[i][0],x[i+1][0],abs(x[i+1][1] - x[i][1]))
    G.add(y[i][0],y[i+1][0],abs(y[i+1][1] - y[i][1]))

print(G.Kruskal())

Submission status: Accepted

Solution code:
#from numpy import* #import numpy as np
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) #dijkstra #floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

class UNION_FIND(object):
    def __init__(self,n):
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])
            return self.parent[x]
 
    def size(self,x):
        return -self.parent[self.root(x)]
    def union(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]
        self.parent[y]=x
        return True

def KRUSKAL(n, edges, TF_of_maximize):
    edges.sort(key=lambda x: x[2],reverse=TF_of_maximize)
    uf = UNION_FIND(n)
    cost = []
    for (a,b,c) in edges:
        if uf.root(a)!= uf.root(b):
            uf.union(a,b)
            cost.append(c)
    return cost


def main():
    n=int(input())
    inp=[[i]+list(map(int,input().split()))for i in range(n)]
    inpX=sorted(inp,key=lambda x:x[1])
    inpY=sorted(inp,key=lambda x:x[2])
    edges=[]
    for i in range(1,n):
        a,b,c=inpX[i]
        d,e,f=inpX[i-1]
        edges.append((a,d,min(abs(b-e),abs(c-f))))
        a,b,c=inpY[i]
        d,e,f=inpY[i-1]
        edges.append((a,d,min(abs(b-e),abs(c-f))))
    
    print(sum(KRUSKAL(n, edges, 0))) #頂点数 辺(コスト) #最大化するか否か 
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph)
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse import csr_matrix

#from collections import* #defaultdict Counter deque appendleft
#from fractions import gcd
#from functools import* #reduce
#from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
#from operator import mul,itemgetter
#from bisect import* #bisect_left bisect_right
#from heapq import* #heapify heappop heappushpop
#from math import factorial,pi
#from copy import deepcopy
import sys
#sys.setrecursionlimit(10**8)
input=sys.stdin.readline  #危険！基本オフにしろ！

class UNION_FIND(object):
    def __init__(self,n):
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])
            return self.parent[x]
 
    def size(self,x):
        return -self.parent[self.root(x)]
    def union(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]
        self.parent[y]=x
        return True

def compute_mst_kruskal(max_v, edges, flip):
    edges.sort(key=lambda x: x[2],reverse=flip)
    uf = UNION_FIND(max_v)
    mst = []
    for (a,b,c) in edges:
        if uf.root(a)!= uf.root(b):
            uf.union(a,b)
            mst.append(c)
    return mst


def main():
    n=int(input())
    inp=[[i]+list(map(int,input().split()))for i in range(n)]
    inpX=sorted(inp,key=lambda x:x[1])
    inpY=sorted(inp,key=lambda x:x[2])
    edges=[]
    for i in range(1,n):
        a,b,c=inpX[i]
        d,e,f=inpX[i-1]
        edges.append((a,d,min(abs(b-e),abs(c-f))))
        a,b,c=inpY[i]
        d,e,f=inpY[i-1]
        edges.append((a,d,min(abs(b-e),abs(c-f))))
    
    print(sum(compute_mst_kruskal(n, edges, 0)))
        
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph)
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！

class UNION_FIND(object):
    def __init__(self,n):
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])
            return self.parent[x]
 
    def size(self,x):
        return -self.parent[self.root(x)]
    def union(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]
        self.parent[y]=x
        return True

def compute_mst_kruskal(max_v, edges, flip):
    edges.sort(key=lambda x: x[2],reverse=flip)
    uf = UNION_FIND(max_v)
    mst = []
    for (a,b,c) in edges:
        if uf.root(a)!= uf.root(b):
            uf.union(a,b)
            mst.append(c)
    return mst


def main():
    n=int(input())
    inp=[[i]+list(map(int,input().split()))for i in range(n)]
    inpX=sorted(inp,key=lambda x:x[1])
    inpY=sorted(inp,key=lambda x:x[2])
    edges=[]
    for i in range(1,n):
        a,b,c=inpX[i]
        d,e,f=inpX[i-1]
        edges.append((a,d,min(abs(b-e),abs(c-f))))
        a,b,c=inpY[i]
        d,e,f=inpY[i-1]
        edges.append((a,d,min(abs(b-e),abs(c-f))))
    
    print(sum(compute_mst_kruskal(n, edges, 0)))
        
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    # UnionFind
    class UnionFind():
        def __init__(self, n):
            self.nodes=[-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

        def get_root(self, x):
            # nodes[x]が負ならxが根
            if self.nodes[x] < 0:
                return x
            # 根に直接つなぎ直しつつ、親を再帰的に探す
            else:
                self.nodes[x]=self.get_root(self.nodes[x])
                return self.nodes[x]

        def unite(self, x, y):
            root_x=self.get_root(x)
            root_y=self.get_root(y)
            # 根が同じなら変わらない
            # if root_x == root_y:
            # pass
            if root_x != root_y:
                # 大きい木の方につないだほうが計算量が減る
                if self.nodes[root_x] < self.nodes[root_y]:
                    big_root=root_x
                    small_root=root_y
                else:
                    small_root=root_x
                    big_root=root_y
                self.nodes[big_root] += self.nodes[small_root]
                self.nodes[small_root]=big_root
    
    N = I()
    uf=UnionFind(N)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes
    xlist = []
    ylist = []
    for i in range(N):
        x, y = MI()
        xlist.append((x, i))
        ylist.append((y, i))
    xlist.sort()
    ylist.sort()
    
    edges = [] #(重み、頂点a,b)
    for i in range(N - 1):
        edges.append((xlist[i+1][0]-xlist[i][0], xlist[i][1],xlist[i+1][1]))
        edges.append((ylist[i+1][0]-ylist[i][0],ylist[i][1], ylist[i + 1][1]))
    edges.sort(reverse=True)

    cnt = 1
    ans=0
    while cnt<N:
        c, a, b = edges.pop()
        if get_root(a) != get_root(b):
            unite(a, b)
            cnt += 1
            ans += c
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[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)


n = int(input())
x_list = [(0, 0)] * n
y_list = [(0, 0)] * n
for i in range(n):
    x, y = map(int, input().split())
    x_list[i] = (x, i)
    y_list[i] = (y, i)
x_list.sort()
y_list.sort()
h = []
heapq.heapify(h)
for i in range(n - 1):
    x1, ix1 = x_list[i]
    x2, ix2 = x_list[i + 1]
    y1, iy1 = y_list[i]
    y2, iy2 = y_list[i + 1]
    heapq.heappush(h, (x2 - x1, ix1, ix2))
    heapq.heappush(h, (y2 - y1, iy1, iy2))

ans = 0
uf = UnionFind(n)
while h:
    w, s, t = heapq.heappop(h)
    if not uf.same_check(s, t):
        ans += w
        uf.union(s, t)
print(ans)

Submission status: Accepted

Solution code:
# ARC 076 D
# クラスカル法による最小全域木問題

# 辺をコストの小さい順に見ていき、閉路ができない(Union-Findで判定)場合は追加する

from heapq import heappush, heappop


class UnionFind(object):

    def __init__(self, N):
        self.tree = [i for i in range(N)]
        self.rank = [0] * (N + 1)

    def find(self, x):
        if self.tree[x] == x:
            return x
        else:
            self.tree[x] = self.find(self.tree[x])  # 経路圧縮
            return self.tree[x]

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

        # ランクを考慮しない場合はどちらが親になっても良い
        if self.rank[x] < self.rank[y]:
            self.tree[x] = y
        else:
            self.tree[y] = x

        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

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


class Edge(object):

    def __init__(self, src, dst, cost):
        self.src = src
        self.dst = dst
        self.cost = cost


def mst_kruskal():
    """
    kruskalのアルゴリズムによって最小全域木を構成する。

    :return: 最小全域木、つまりMSTに含まれる辺のリスト
    """
    pass


N = int(input())
V = list()
for i in range(N):
    x, y = map(int, input().split())
    V.append((i, x, y))

# グラフがx, yの格子のみなので、全ての頂点をそれぞれx座標についてy座標についてソートした列で隣接する2点の張る辺だけを考えれば良い
edges = list()
V.sort(key=lambda v: v[1])
for i in range(1, N):
    (src_i, src_x, src_y), (dst_i, dst_x, dst_y) = V[i - 1], V[i]
    heappush(edges, (abs(dst_x - src_x), src_i, dst_i))
V.sort(key=lambda v: v[2])
for i in range(1, N):
    (src_i, src_x, src_y), (dst_i, dst_x, dst_y) = V[i - 1], V[i]
    heappush(edges, (abs(dst_y - src_y), src_i, dst_i))

total_cost = 0
uf = UnionFind(N)
while len(edges) != 0:
    cost, src, dst = heappop(edges)
    if uf.find(src) != uf.find(dst):
        uf.unite(src, dst)
        total_cost += cost

print(total_cost)

Submission status: Accepted

Solution code:
N=int(input())
city=[0]*N
for i in range(N):
    x,y=map(int,input().split())
    city[i]=(i,x,y)
city.sort(key=lambda x:x[1])
data=[(city[i][0],city[i+1][0],city[i+1][1]-city[i][1]) for i in range(N-1)]
city.sort(key=lambda x:x[2])
data+=[(city[i][0],city[i+1][0],city[i+1][2]-city[i][2]) for i in range(N-1)]
data.sort(key=lambda x:x[2])
root=[-1]*N
def search(i):
    global root
    if root[i]>=0:
        root[i]=search(root[i])
        return root[i]
    return i
cost=0
for i,j,k in data:
    ri=search(i)
    rj=search(j)
    if ri==rj:
        continue
    elif root[ri]<=root[rj]:
        cost+=k
        root[ri]+=root[rj]
        root[rj]=ri
    elif root[ri]>root[rj]:
        cost+=k
        root[rj]+=root[ri]
        root[ri]=rj
print(cost)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc065/tasks/arc076_b

import itertools
from collections import Counter
from collections import defaultdict
import collections
from functools import reduce
import bisect
import math
import heapq
import copy

# Union find
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]  # 負の値の場合根を表す。正の値は次の要素を返す、根まで続く
        self.size = [1 for _  in range(size)]

    #集合の代表を求める
    def find(self,x):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

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

    #併合
    def union(self,x,y):
        s1 = self.find(x)#根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        if s1 != s2:#根が異なる場合
            if self.table[s1] != self.table[s2]:#グラフの高さが異なる場合
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                    self.size[s1] += self.size[s2]
                else:
                    self.table[s1] = s2
                    self.size[s2] += self.size[s1]
            else:
                #グラフの長さが同じ場合,どちらを根にしても変わらない
                #その際,グラフが1長くなることを考慮する
                self.table[s1] += -1
                self.table[s2] = s1
                self.size[s1] += self.size[s2]
        return

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

Edge = collections.namedtuple("Edge", "start end weight")


def solve_by_kraskal(n, edges):
    """
        最小全域木を計算してそのルートを返す
        Parameters
        ----------
        n : int
            頂点の数
        edges: [Edge]
            辺のリスト

        Returns
        -------
        route : [Edge]
            最小全域木を構築する辺
    """

    edges.sort(key=lambda edge: edge.weight)
    uf = UnionFind(n)
    route = []

    for edge in edges:
        if not uf.is_same(edge.start, edge.end):
            uf.union(edge.start, edge.end)
            route.append(edge)

    return route


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

    x_dots.sort(key=lambda x: x[1])
    y_dots = copy.copy(x_dots)
    y_dots.sort(key=lambda x: x[2])
    # print(x_dots)
    # print(y_dots)

    x_edges = []
    for i in range(N - 1):
        dot = x_dots[i]
        next_dot = x_dots[i + 1]
        x_edges.append(Edge(dot[0], next_dot[0], min(abs(dot[1] - next_dot[1]), abs(dot[2] - next_dot[2]))))
        x_edges.append(Edge(next_dot[0], dot[0], min(abs(dot[1] - next_dot[1]), abs(dot[2] - next_dot[2]))))

    y_edges = []
    for i in range(N - 1):
        dot = y_dots[i]
        next_dot = y_dots[i + 1]
        y_edges.append(Edge(dot[0], next_dot[0], min(abs(dot[1] - next_dot[1]), abs(dot[2] - next_dot[2]))))
        y_edges.append(Edge(next_dot[0], dot[0], min(abs(dot[1] - next_dot[1]), abs(dot[2] - next_dot[2]))))

    route = solve_by_kraskal(N, x_edges + y_edges)
    ans = 0
    for r in route:
        ans += r[2]

    print(ans)


if __name__ == '__main__':
    main()

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))
    
# csr形式に直す
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
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))
    
# csr形式に直す
edge = sorted(list(edge))
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
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 _ in range(N)]
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[i1].add((i2,d))
    
# csr形式に直す
col = []
row = []
value = []
for i in range(N):
  for j,v in edge[i]:
    col.append(i)
    row.append(j)
    value.append(v)
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
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 _ in range(N)]
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[i1].add((i2,d))
    
# csr形式に直す
indptr = []
indrow = []
value = []
ptr = 0
for i in range(N):
  indptr.append(ptr)
  for j,v in edge[i]:
    indrow.append(j)
    value.append(v)
    ptr += 1
indptr.append(ptr)
value = np.array(value,dtype=int)
graph = csr_matrix((value,indrow,indptr),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:
from heapq import heappush, heappop

def prim(ad): # ad[i][j]: (重み, ノード)
    N = len(ad)
    used = [0]*N
    hq = []
    for ad_i in ad[0]:
        heappush(hq, ad_i)
    used[0] = 1
    res = 0
    while hq:
        w, v = heappop(hq)
        if used[v]: continue
        used[v] = 1
        for nw, nv in ad[v]:
            if used[nv]: continue
            heappush(hq, (nw, nv))
        res += w
    return res

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

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

for t in range(N-1):
    a, i = X[t]
    c, j = X[t+1]
    wx = abs(a-c)
    ad[i].append((wx,j))
    ad[j].append((wx,i))
    b, k = Y[t]
    d, l = Y[t+1]
    wy = abs(b-d)
    ad[k].append((wy,l))
    ad[l].append((wy,k))

ans = prim(ad)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

li = [ [int(it) for it in input().split() ] for i in range(N) ]

lix = [0]*N
liy = [0]*N
for i in range(N):
  lix[i] = (i,li[i][0])
  liy[i] = (i,li[i][1])
lix.sort( key=lambda x:x[1] )
liy.sort( key=lambda x:x[1] )

edge = [0]*(2*(N-1))
c = 0
for i in range(N-1):
  edge[c] = ( lix[i][0],lix[i+1][0], lix[i+1][1] - lix[i][1] )
  c +=1
  edge[c] = ( liy[i][0],liy[i+1][0], liy[i+1][1] - liy[i][1] )
  c +=1

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

class Union():
  def __init__(me,N):
    me.N = N
    me.up = [-1]*N
    me.down = [ [] for i in range(N) ]
  def union(me,a,b):
    ua = me.up[a] if me.up[a]!=-1 else a
    ub = me.up[b] if me.up[b]!=-1 else b
    if (ua == ub):
      return
    if ( len(me.down[ua]) < len(me.down[ub]) ):
      ub,ua = ua,ub
    for v in me.down[ub]:
      me.up[v] = ua
    me.down[ua].extend( me.down[ub] )
    me.down[ub] = []
    me.up[ub] = ua
    me.down[ua].append( ub )
  def count(me,a):
    ua = me.up[a] if me.up[a]!=-1 else a
    return len(me.down[ua])+1
  
u = Union(N)

cost = 0
for a,b,c in edge:
  ua = u.up[a] if u.up[a]!=-1 else a
  ub = u.up[b] if u.up[b]!=-1 else b
  if ( ua != ub ):
    u.union(ua,ub)
    cost += c
print ( cost )

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def unite(i, j):
    j = get_par(j)
    par[j] = get_par(i)
    return

def get_par(p):
    if par[p] is None:
        return p
    par[p] = get_par(par[p])
    return par[p]

N = int(input())
points = []
edges = []
for i in range(N):
    x,y = map(int, input().split())
    points.append([x,y,i])
points.sort()
for i in range(N-1):
    edges.append((abs(points[i][0] - points[i+1][0]), points[i][2], points[i+1][2]))
points.sort(key=lambda x:x[1])
for i in range(N-1):
    edges.append((abs(points[i][1] - points[i+1][1]), points[i][2], points[i+1][2]))
edges.sort(key=lambda x:x[0], reverse=True)

par = [None] * N
cost = 0
count = 0
points.sort()
while count < N - 1:
    c, i, j = edges.pop()
    if get_par(i) == get_par(j):
        continue
    unite(i, j)
    cost += c
    count += 1
print(cost)