Problem:


Score : 500 points

Problem Statement

There are N towns on a plane. The i-th town is located at the coordinates (x_i,y_i). There may be more than one town at the same coordinates.

You can build a road between two towns at coordinates (a,b) and (c,d) for a cost of min(|a-c|,|b-d|) yen (the currency of Japan). It is not possible to build other types of roads.

Your objective is to build roads so that it will be possible to travel between every pair of towns by traversing roads. At least how much money is necessary to achieve this?

Constraints

2 ≤ N ≤ 10^5

0 ≤ x_i,y_i ≤ 10^9

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

Print the minimum necessary amount of money in order to build roads so that it will be possible to travel between every pair of towns by traversing roads.

Sample Input 1

3
1 5
3 9
7 8

Sample Output 1

3

Build a road between Towns 1 and 2, and another between Towns 2 and 3. The total cost is 2+1=3 yen.

Sample Input 2

6
8 3
4 9
12 19
18 1
13 5
7 6

Sample Output 2

8



Sample input:
3
1 5
3 9
7 8


Sample output:
3

Submission status: Accepted

Solution code:
import sys
read=sys.stdin.readline
def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
        else:
            par[a]=b
            if rank[a]==rank[b]:
                rank[b]+=1
def same(a,b):
    return find(a)==find(b)
def Kruskal(Edge,E):
    cost=0
    Edge.sort(key=lambda x:x[2])
    for i in range(E):
        f,t,c=Edge[i]
        if(not same(f,t)):
            union(f,t)
            cost+=c
    return cost
    
N=int(input())
par=[];p=[];dic={};rank=[]
for i in range(N):
    par.append(i)
    rank.append(0)
    p.append(tuple(map(int,read().split())))
    dic[p[i]]=i
xp,yp=sorted(p,key=lambda x:x[0]),sorted(p,key=lambda x:x[1])
Edge=[]
for i in range(N):
    if(i>0):
        Edge.append((dic[xp[i]],dic[xp[i-1]],abs(xp[i][0]-xp[i-1][0])))
        Edge.append((dic[yp[i]],dic[yp[i-1]],abs(yp[i][1]-yp[i-1][1])))
    if(i<N-1):
        Edge.append((dic[xp[i]],dic[xp[i+1]],abs(xp[i][0]-xp[i+1][0])))
        Edge.append((dic[yp[i]],dic[yp[i+1]],abs(yp[i][1]-yp[i+1][1])))
print(Kruskal(Edge,len(Edge)))

Submission status: Accepted

Solution code:
import sys
read=sys.stdin.readline
def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
        else:
            par[a]=b
            if rank[a]==rank[b]:
                rank[b]+=1
def same(a,b):
    return find(a)==find(b)
def Kruskal(Edge,E):
    cost=0
    Edge.sort(key=lambda x:x[2])
    for i in range(E):
        f,t,c=Edge[i]
        if(not same(f,t)):
            union(f,t)
            cost+=c
    return cost

N=int(input())
par=[];p=[];dic={};rank=[]
for i in range(N):
    par.append(i)
    rank.append(0)
    p.append(tuple(map(int,read().split())))
    dic[p[i]]=i
xp=sorted(p,key=lambda x:x[0])
yp=sorted(p,key=lambda x:x[1])
Edge=[]
for i in range(N):
    if(i>0):
        Edge.append((dic[xp[i]],dic[xp[i-1]],abs(xp[i][0]-xp[i-1][0])))
    if(i<N-1):
        Edge.append((dic[xp[i]],dic[xp[i+1]],abs(xp[i][0]-xp[i+1][0])))
    if(i>0):
        Edge.append((dic[yp[i]],dic[yp[i-1]],abs(yp[i][1]-yp[i-1][1])))
    if(i<N-1):
        Edge.append((dic[yp[i]],dic[yp[i+1]],abs(yp[i][1]-yp[i+1][1])))
print(Kruskal(Edge,len(Edge)))

Submission status: Accepted

Solution code:
import sys


class UnionFind:
    def __init__(self, n):
        # total number of nodes.
        self.n = n
        # node id -> root node id
        self._root_table = list(range(n))
        # root node id -> group size
        self._size_table = [1] * n

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            # Update the cache on query.
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        # Ensure that x is the larger (or equal) group.
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

    def size(self, x):
        return self._size_table[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._root_table) if x == i]

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


input = sys.stdin.readline


def main():
    N = int(input())
    cities, xs, ys = [], [], []
    for i in range(N):
        x, y = map(int, input().split())
        cities.append((x, y))
        xs.append((x, i))
        ys.append((y, i))
    xs.sort()
    ys.sort()
    xd, yd = [], []
    for i in range(1, N):
        x1, c1 = xs[i - 1]
        x2, c2 = xs[i]
        if x2 - x1 <= abs(cities[c1][1] - cities[c2][1]):
            xd.append((x2 - x1, c1, c2))
        y1, c1 = ys[i - 1]
        y2, c2 = ys[i]
        if y2 - y1 < abs(cities[c1][0] - cities[c2][0]):
            xd.append((y2 - y1, c1, c2))
    xd.sort()

    uf = UnionFind(N)
    cost = 0
    merged_cnt = 0
    for d1, c1, c2 in xd:
        if not uf.same(c1, c2):
            uf.union(c1, c2)
            cost += d1
            merged_cnt += 1
            if merged_cnt == N - 1:
                break
    print(cost)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/joisc2010/tasks/joisc2010_finals
import sys
input = sys.stdin.readline


class UnionFind:
    # この時点でそれぞれのノードは自分を親としている
    # 初期化時に問題が0の頂点を認めるかに注意すること
    def __init__(self, n):
        self.N = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    # xの根を返す関数
    def root(self, x):
        visited_nodes = []
        while True:
            p = self.parent[x]
            if p == x:
                # 縮約
                for node in visited_nodes:
                    self.parent[node] = x
                return x
            else:
                visited_nodes.append(x)
                x = p

    # 木の結合を行う。親の配下に入る
    def unite(self, x, y):
        if not self.root(x) == self.root(y):
            if self.rank[x] > self.rank[y]:
                self.parent[self.root(y)] = self.root(x)
            else:
                self.parent[self.root(x)] = self.root(y)
                if self.rank[x] == self.rank[y]:
                    self.rank[self.root(y)] += 1

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

    # 木の根に到達すまでにたどるノードの配列を返す
    def printDebugInfo(self):
        print([self.root(i) for i in range(self.N)])

# edge=[cost, place, place] sorted by cost.
# place are expected to be 0 to N-1
# N : vertical count


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

omega = []
for i in range(N-1):
    omega.append((X[i+1][0] - X[i][0], X[i][1], X[i+1][1], 0))
    omega.append((Y[i+1][0] - Y[i][0], Y[i][1], Y[i+1][1], 1))
omega.sort()
tree = UnionFind(N)
weight = 0
counter = N
i = 0
while True:
    # omega = [cost, place, place, type(0:x. 1:y)]
    minimum_edge = omega[i]
    a = minimum_edge[1]
    b = minimum_edge[2]
    kind = minimum_edge[3]
    cost = minimum_edge[0]
    if counter == 1:
        break
    i += 1
    if tree.ifSame(a, b):
        continue
    else:
        tree.unite(a, b)
        weight += cost
        counter -= 1
print(weight)

Submission status: Accepted

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

  from collections import deque
  n = int(input())
  st = deque([])

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

  from operator import itemgetter
  bb = tuple(sorted(st,key=itemgetter(1)))
  chk = tuple(sorted(st,key=itemgetter(2)))
  #print(bb,chk)

  for i in range(n-1):
    x = bb[i][0]
    y = bb[i+1][0]
    z = bb[i+1][1]-bb[i][1]
    edge[x].append((z,y))
    edge[y].append((z,x))

  for i in range(n-1):
    a = chk[i][0]
    b = chk[i+1][0]
    c = chk[i+1][2]-chk[i][2]
    edge[a].append((c,b))
    edge[b].append((c,a))

  edge = tuple(edge)
  print(prim_heap())
if __name__ == '__main__':
    main()

Submission status: Accepted

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

from collections import deque
n = int(input())
st = deque([])

edge = deque([[] for i in range(n)])
for i in range(n):
    x,y = map(int,input().split())
    st_append = st.append
    st_append((i,x,y))
    
from operator import itemgetter
bb = tuple(sorted(st,key=itemgetter(1)))
chk = tuple(sorted(st,key=itemgetter(2)))
#print(bb,chk)

for i in range(n-1):
  x = bb[i][0]
  y = bb[i+1][0]
  z = bb[i+1][1]-bb[i][1]
  edge[x].append((z,y))
  edge[y].append((z,x))
  
for i in range(n-1):
  a = chk[i][0]
  b = chk[i+1][0]
  c = chk[i+1][2]-chk[i][2]
  edge[a].append((c,b))
  edge[b].append((c,a))
  
edge = tuple(edge)
print(prim_heap())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

class UnionFind:
    def __init__(self, n):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.find(self.d[x])
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True
    
    def same(self, x, y):
        if self.find(x)==self.find(y):
            return True
        return False
    
    def size(self, x):
        return (-1) * self.d[self.find(x)]

N = ii()

l_x = []
l_y = []
for i in range(N):
    x, y = mi()
    l_x.append([i, x])
    l_y.append([i, y])
l_x.sort(key=lambda x:x[1])
l_y.sort(key=lambda x:x[1])

path = []
for i in range(N-1):
    path.append([l_x[i][0], l_x[i+1][0], l_x[i+1][1]-l_x[i][1]])
    path.append([l_y[i][0], l_y[i+1][0], l_y[i+1][1]-l_y[i][1]])
path.sort(key=lambda x:x[2])

T = UnionFind(N)
cnt = 0
for i in range(2*N-2):
    s, t, d = path[i][0], path[i][1], path[i][2]
    if not T.same(s, t):
        T.unite(s, t)
        cnt += d

print(cnt)

Submission status: Accepted

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

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

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


def main():
    N = int(input())
    X = []
    Y = []
    for i, _ in enumerate(range(N)):
        x, y = map(int, input().split())
        X.append((x, i))
        Y.append((y, i))
    X.sort()
    Y.sort()
    hq = []
    for i in range(N-1):
        x1, x1_ind = X[i]
        x2, x2_ind = X[i+1]
        y1, y1_ind = Y[i]
        y2, y2_ind = Y[i+1]
        heappush(hq, (x2-x1, x1_ind, x2_ind))
        heappush(hq, (y2-y1, y1_ind, y2_ind))
    ans = 0
    union_find = UnionFind(N)
    while hq:
        w, s, t = heappop(hq)
        if not union_find.is_same(s, t):
            union_find.union(s, t)
            ans += w

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappop, heappush
def prim(G):
    used = [False] * len(G) 
    hq = [(0, 0)]
    res = 0
    while hq:
        w, v = heappop(hq)
        if used[v]:
            continue
        used[v] = True
        res += w
        for cv, cw in G[v]:
            if used[cv]:
                continue
            heappush(hq, (cw, cv))
    return res

def main():
    N = int(input())
    X = []
    Y = []
    for i, _ in enumerate(range(N)):
        x, y = map(int, input().split())
        X.append((x, i))
        Y.append((y, i))
    X.sort()
    Y.sort()
    graph = [[] for _ in range(N)]
    prev_x, prev_x_ind = X[0]
    prev_y, prev_y_ind = Y[0]
    for i in range(1, N):
        x, x_ind = X[i]
        y, y_ind = Y[i]
        graph[prev_x_ind].append((x_ind, x - prev_x))
        graph[x_ind].append((prev_x_ind, x - prev_x))
        graph[prev_y_ind].append((y_ind, y - prev_y))
        graph[y_ind].append((prev_y_ind, y - prev_y))
        prev_x, prev_x_ind = x, x_ind
        prev_y, prev_y_ind = y, y_ind
    print(prim(graph))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

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())
xy = mylistinput(n)

G = Kruskal_UnionFind(n)

xy0 = []
for i in range(n):
    x = xy[i][0]
    y = xy[i][1]
    xy0.append([i,x,y])

xy1 = mysort(xy0,1)
for i in range(n-1):
    No1 = xy1[i][0]
    a = xy1[i][1]
    b = xy1[i][2]
    No2 = xy1[i+1][0]
    c = xy1[i+1][1]
    d = xy1[i+1][2]
    cost = min(abs(c-a),abs(d-b))
    G.add(No1,No2,cost)

xy2 = mysort(xy0,2)
for i in range(n-1):
    No1 = xy2[i][0]
    a = xy2[i][1]
    b = xy2[i][2]
    No2 = xy2[i+1][0]
    c = xy2[i+1][1]
    d = xy2[i+1][2]
    cost = min(abs(c-a),abs(d-b))
    G.add(No1,No2,cost)

ans = G.Kruskal()
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

def kruskal(edges, size):
    uf = UnionFind(size)
    edges = sorted(edges, key=lambda e: e[2])
    ret = 0
    for u, v, weight in edges:
        if not uf.same(u, v):
            uf.unite(u, v)
            ret += weight
    return ret

N = int(input())
x = [0] * N
y = [0] * N
for i in range(N):
    a, b = map(int, input().split())
    x[i] = (a, i)
    y[i] = (b, i)
x.sort()
y.sort()
edges = []
for i in range(N-1):
    x1, u = x[i]
    x2, v = x[i+1]
    edges.append((u, v, x2 - x1))
    y1, u = y[i]
    y2, v = y[i+1]
    edges.append((u, v, y2 - y1))
ans = kruskal(edges, N)
print(ans)

Submission status: Accepted

Solution code:
INF = 10 ** 7
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from  heapq import heappop,heapify,heappush

def prim(G):
    ans = 0
    used = [0] * len(G)
    used[0] = 1
    q = []
    for e,c in G[0]:
        heappush(q,(c,e))
    
    while len(q):
        c1,e1 = heappop(q)
        if used[e1]:
            continue
        used[e1] = 1
        for e2,c2 in G[e1]:
            if used[e2] == 0:
                heappush(q,(c2,e2))
        ans += c1
    return ans

def main():
    n = int(input())
    G = [[] for _ in range(n)]
    P = []
    Q = []
    for i in range(n):
        x,y = map(int,input().split())
        P.append((i,x))
        Q.append((i,y))
    
    P.sort(key = lambda x:x[1])
    Q.sort(key = lambda x:x[1])
    for index in range(n - 1):
        i,x1 = P[index]
        j,x2 = P[index + 1]
        G[i].append((j,x2 - x1))
        G[j].append((i,x2 - x1))
        i,y1 = Q[index]
        j,y2 = Q[index + 1]
        G[i].append((j,y2 - y1))
        G[j].append((i,y2 - y1))
    
    ans = prim(G)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# kotae mita
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
def main():
    N = int(input())
    l = []
    for i in range(N):
        x, y = map(int, input().split())
        l.append((x,y,i))
    X = sorted(l, key=lambda x:x[0])
    Y = sorted(l, key=lambda x:x[1])
    d = {}
    for i in range(N-1):
        p = max(X[i][2], X[i+1][2])
        q = min(X[i][2], X[i+1][2])
        if (p, q) in d:
            d[(p, q)] = min(d[(p,q)], abs(X[i][0] - X[i+1][0]))
        else:
            d[(p, q)] = abs(X[i][0] - X[i+1][0])
        p = max(Y[i][2], Y[i+1][2])
        q = min(Y[i][2], Y[i+1][2])
        if (p, q) in d:
            d[(p, q)] = min(d[(p,q)], abs(Y[i][1] - Y[i+1][1]))
        else:
            d[(p, q)] = abs(Y[i][1] - Y[i+1][1])
    p = []
    q = []
    w = []
    for i in d:
        p.append(i[0])
        q.append(i[1])
        w.append(d[i])
    csr = csr_matrix((w, (p,q)), shape=(N,N))
    return int(minimum_spanning_tree(csr).sum())
print(main())

Submission status: Accepted

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

def main():
    N = int(input())
    M = 10**10
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    xy = [(x, i) for i, (x, _) in enumerate(XY)]
    yx = [(y, i) for i, (_, y) in enumerate(XY)]
    xy.sort()
    yx.sort()
    d = {}
    x1, i1 = xy[0]
    for x, i in xy[1:]:
        t = (i1, i) if i1 < i else (i, i1)
        d[t] = min(abs(x1 - x), d.get(t, M))
        x1, i1 = x, i
    x1, i1 = yx[0]
    for x, i in yx[1:]:
        t = (i1, i) if i1 < i else (i, i1)
        d[t] = min(abs(x1 - x), d.get(t, M))
        x1, i1 = x, i
    row = list(map(itemgetter(0), d.keys()))
    col = list(map(itemgetter(1), d.keys()))
    c = coo_matrix((list(d.values()), (row, col)), shape=(N, N))
    a = minimum_spanning_tree(c, overwrite=True)
    return int(a.sum())

print(main())

Submission status: Accepted

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

def main():
    N = int(input())
    M = 10**10
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    xy = [(x, i) for i, (x, _) in enumerate(XY)]
    yx = [(y, i) for i, (_, y) in enumerate(XY)]
    xy.sort()
    yx.sort()
    d = {}
    x1, i1 = xy[0]
    for x, i in xy[1:]:
        t = (i1, i) if i1 < i else (i, i1)
        d[t] = min(abs(x1 - x), d.get(t, M))
        x1, i1 = x, i
    x1, i1 = yx[0]
    for x, i in yx[1:]:
        t = (i1, i) if i1 < i else (i, i1)
        d[t] = min(abs(x1 - x), d.get(t, M))
        x1, i1 = x, i
    row = list(map(itemgetter(0), d.keys()))
    col = list(map(itemgetter(1), d.keys()))
    c = csr_matrix((list(d.values()), (row, col)), shape=(N, N))
    a = minimum_spanning_tree(c, overwrite=True)
    return int(a.sum())

print(main())

Submission status: Accepted

Solution code:
n = int(input())
xy = []
for i in range(n):
    tmp = list(map(int,input().split()))
    tmp.append(i)
    xy.append(tmp)
link = []

xy.sort(key=lambda x:x[0])
for i in range(n-1):
    x1,_,node1 = xy[i]
    x2,_,node2 = xy[i+1]
    cost = abs(x1-x2)
    link.append([node1,node2,cost])

xy.sort(key=lambda x:x[1])
for i in range(n-1):
    _,y1,node1 = xy[i]
    _,y2,node2 = xy[i+1]
    cost = abs(y1-y2)
    link.append([node1,node2,cost])
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 krs(g,num_v):
    g.sort(key=lambda x:x[2])

    uf = UnionFind(num_v)
    mst = []
    for edge in g:
        if not uf.same(edge[0], edge[1]):
            uf.union(edge[0], edge[1])
            mst.append(edge)
    return mst


ret = krs(link,n)
ans=0
for i in range(len(ret)):
    ans+=ret[i][2]
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    #ｎは頂点数
    def __init__(self, n):
        self.parent = [-1]*n

    #aの属する集合の根を取得
    def root(self,a):
        if self.parent[a] < 0:return a
        self.parent[a] = self.root(self.parent[a])
        return self.parent[a]
    
    #aの属する集合の要素数を取得
    def size(self,a):
        return -self.parent[self.root(a)]

    #aとbをくっつける
    def connect(self,a,b):
        if self.root(a) == self.root(b):return False
        a = self.root(a);b = self.root(b)
        if self.size(a) < self.size(b):a,b = b,a
        self.parent[a] += self.parent[b]
        self.parent[b] = a
        return True

n = int(input())
x = [0]*n
y = [0]*n
for i in range(n):
    a,b = list(map(int,input().split()))
    x[i] = [a-1,i]
    y[i] = [b-1,i]
x.sort(key=lambda f: f[0])
y.sort(key=lambda f: f[0])

kouho = []
for i in range(n-1):
    kouho.append([abs(x[i][0] - x[i+1][0]),x[i][1],x[i+1][1]])
    kouho.append([abs(y[i][0] - y[i+1][0]),y[i][1],y[i+1][1]])
kouho.sort(key=lambda x: x[0])
uni = UnionFind(n)

ans = 0
for i in range(len(kouho)):
    c,f,t = kouho[i]
    if uni.root(f) == uni.root(t):continue
    ans += c
    uni.connect(f,t)
print(ans)

Submission status: Accepted

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

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

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

P.sort()
edge = [[] for _ in range(n)]
for i in range(n-1):
    d = min(abs(P[i+1][0]-P[i][0]), abs(P[i+1][1]-P[i][1]))
    edge[P[i][2]].append((d, P[i+1][2]))
    edge[P[i+1][2]].append((d, P[i][2]))

P.sort(key = lambda x: x[1])
for i in range(n-1):
    d = min(abs(P[i+1][0]-P[i][0]), abs(P[i+1][1]-P[i][1]))
    edge[P[i][2]].append((d, P[i+1][2]))
    edge[P[i+1][2]].append((d, P[i][2]))

print(prim_heap())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

xi = [(i,x[i]) for i in range(n)]
yi = [(i,y[i]) for i in range(n)]

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

INF = float('inf')

# xycost = [[INF]*n for i in range(n)]
# for i in range(n-1):
#     xycost[xi[i][0]][xi[i+1][0]] = min(xycost[xi[i][0]][xi[i+1][0]], xi[i+1][1] -xi[i][1])
#     xycost[xi[i+1][0]][xi[i][0]] = min(xycost[xi[i+1][0]][xi[i][0]], xi[i+1][1] -xi[i][1])
#     xycost[yi[i][0]][yi[i+1][0]] = min(xycost[yi[i][0]][yi[i+1][0]], yi[i+1][1] -yi[i][1])
#     xycost[yi[i+1][0]][yi[i][0]] = min(xycost[yi[i+1][0]][yi[i][0]], yi[i+1][1] -yi[i][1])

xycost = []

for i in range(n-1):
    tmp = (xi[i][0], xi[i+1][0], xi[i+1][1] -xi[i][1])
    xycost.append(tmp)
    tmp = (yi[i][0], yi[i+1][0], yi[i+1][1] -yi[i][1])
    xycost.append(tmp)

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

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

    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(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.root(x)]

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

    def members(self, x):  # 計算量n
        root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == root]

    def all_roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.all_roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.all_roots()}

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

uf = UnionFind(n)
ans = 0
for i,j, cost in xycost:
    if not uf.is_same(i,j):
        uf.union(i,j)
        ans += cost
    if uf.size == n: break

print(ans)

Submission status: Accepted

Solution code:
# ユニオンファインド
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

        self.parents[x] += self.parents[y]
        self.parents[y] = x



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


n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
b=[]
a.sort()
# aの各点に通し番号を振る
for i in range(n):
    a[i].append(i)

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

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

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

uf=UnionFind(n)
ans=0
cnt=0
# クラスカル法
for x,y,z in b:
    if not uf.same(x,y):
        uf.union(x,y)
        cnt+=1
        ans+=z
        if cnt==n-1:
            break
print(ans)