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:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
# mod = 998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"
INF = 1<<32-1
# INF = 10**18

#UnionFindのクラス,0-indexed
class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents = [-1,0,-4,1,1,1]のように、親の添字かマイナス要素数を表す
        self.parents = [-1] * n

    def find(self, x): # find: xの親がすべてrootになる。これにより計算量削減(O(N) for all (not each))
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n = int(ipt())
    xs = []
    ys = []
    for i in range(n):
        x,y = map(int,ipt().split())
        xs.append(x*n+i)
        ys.append(y*n+i)
    xs.sort()
    ys.sort()
    ways = []
    x0 = xs[0]//n
    xi = xs[0]%n
    y0 = ys[0]//n
    yi = ys[0]%n
    for i in xs[1::]:
        x = i//n
        j = i%n
        ways.append((x-x0)*(n**2)+xi*n+j)
        x0 = x
        xi = j
    for i in ys[1::]:
        y = i//n
        j = i%n
        ways.append((y-y0)*(n**2)+yi*n+j)
        y0 = y
        yi = j

    ways.sort()
    ans = 0
    uf = UnionFind(n)
    for i in ways:
        d = i//(n**2)
        i1 = (i//n)%n
        i2 = i%n
        # print(i,d,i1,i2)
        if not uf.same(i1,i2):
            uf.union(i1,i2)
            ans += d

    print(ans)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

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

N = int(input())
x = [None] * N
y = [None] * N
for i in range(N):
    a, b = map(int, input().split())
    x[i] = (a,i)
    y[i] = (b,i)

x.sort()
y.sort()
q = []
for i in range(N-1):
    heappush(q, (abs(x[i][0]-x[i+1][0]), x[i][1], x[i+1][1]))
    heappush(q, (abs(y[i][0]-y[i+1][0]), y[i][1], y[i+1][1]))

uf = UnionFind(N)
ans = 0
# クラスカル法
while len(q) > 0:
    w, s, t = heappop(q)
    if uf.find(s) != uf.find(t):
        ans += w
        uf.union(s,t)
print(ans)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N = I()
X,Y = [],[]
for i in range(N):
    x,y = MI()
    X.append((x,i+1))
    Y.append((y,i+1))

X.sort()
Y.sort()


# Kruskal


class Kruskal():
    def __init__(self,n):
        self.e = []
        self.par = [i for i in range(n+1)]  # 親のノード番号
        self.rank = [0]*(n+1)
    def add(self,u,v,d):  # クラスカル法で考えるのは無向グラフ
        self.e.append([u,v,d])
    def find(self,x):  # xの根のノード番号
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self,x,y):  # x,yが同じグループか否か
        return self.find(x) == self.find(y)
    def unite(self,x,y):  # x,yの属するグループの併合
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1
    def Kruskal(self):
        edges = sorted(self.e,key=lambda x: x[2])  # 距離でソート
        a = 0
        for e in edges:
            if not self.same_check(e[0],e[1]):
                self.unite(e[0],e[1])
                a += e[2]
        return a


K = Kruskal(N)
for j in range(N-1):
    x0,i0 = X[j]
    x1,i1 = X[j+1]
    K.add(i0,i1,x1-x0)
for j in range(N-1):
    y0,i0 = Y[j]
    y1,i1 = Y[j+1]
    K.add(i0,i1,y1-y0)

print(K.Kruskal())

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]
    def find(self, x):
        """
        x が属するグループを探索して親を出す。
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)
    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]

from heapq import heapify, heappop, heappush
N = int(input())
X = [];Y = []
for i in range(N):
  a,b = map(int,input().split())
  X.append((a,b,i))
  Y.append((a,b,i))
X.sort(key=lambda x:x[0])
Y.sort(key=lambda x:x[1])
#print(X,Y)
PQ = []
for i in range(N-1):
  difx = (X[i+1][0]-X[i][0],X[i][2],X[i+1][2])
  dify = (Y[i+1][1]-Y[i][1],Y[i][2],Y[i+1][2])
  #print(difx,dify)
  heappush(PQ,difx);heappush(PQ,dify)
uf = UnionFind(N)
ans = 0
while PQ:
  dis,a,b = heappop(PQ)
  if uf.is_same(a, b):
    continue
  ans += dis
  uf.union(a,b)
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
X,Y = [],[]
for i in range(N):
    x,y = MI()
    X.append((x,i+1))
    Y.append((y,i+1))

X.sort()
Y.sort()


# Kruskal


class Kruskal():
    def __init__(self,n):
        self.e = []
        self.par = [i for i in range(n+1)]  # 親のノード番号
        self.rank = [0]*(n+1)
    def add(self,u,v,d):  # クラスカル法で考えるのは無向グラフ
        self.e.append([u,v,d])
    def find(self,x):  # xの根のノード番号
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self,x,y):  # x,yが同じグループか否か
        return self.find(x) == self.find(y)
    def unite(self,x,y):  # x,yの属するグループの併合
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[x] > self.rank[y]:
            self.par[y] = x
        else:
            self.par[y] = x
            self.rank[x] += 1
    def Kruskal(self):
        edges = sorted(self.e,key=lambda x: x[2])  # 距離でソート
        a = 0
        for e in edges:
            if not self.same_check(e[0],e[1]):
                self.unite(e[0],e[1])
                a += e[2]
        return a


K = Kruskal(N)
for j in range(N-1):
    x0,i0 = X[j]
    x1,i1 = X[j+1]
    K.add(i0,i1,x1-x0)
for j in range(N-1):
    y0,i0 = Y[j]
    y1,i1 = Y[j+1]
    K.add(i0,i1,y1-y0)

print(K.Kruskal())

Submission status: Accepted

Solution code:
import heapq
# n,m=map(int,input().split())
n=int(input())
def deka(a,b,c):
    return a*10**12+b*10**6+c
parents=[-1 for i in range(n)] #ひとつ親、自分が根の場合はその木のサイズ*(-1)
HEN=[] #距離が小さいものが、一番ちっちゃい数になってる
MST=[[] for i in range(n)] #答えである最小全域木
A=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append([i,a,b])
A=sorted(A,key=lambda x:x[1])
for i in range(1,n):
    heapq.heappush(HEN, deka(A[i][1]-A[i-1][1],A[i][0],A[i-1][0]))
A=sorted(A,key=lambda x:x[2])
for i in range(1,n):
    heapq.heappush(HEN, deka(A[i][2]-A[i-1][2],A[i][0],A[i-1][0]))
# for i in range(m):
#     a,b,d=map(int,input().split())
#     heapq.heappush(HEN, deka(d,a,b))

def find(x): #xの最親(根)はなに？
    if parents[x] <0 : return x  #自分自身が根
    parents[x]=find(parents[x])
    return parents[x]
def union(x,y): #くっつける
    xx=find(x) ; yy=find(y)
    if xx==yy: return #xとyの根が同じ(同じグループ)ならなにもしない
    size_xx=abs(parents[xx])
    size_yy=abs(parents[yy]) #xやyの属する木のサイズ
    if size_xx>size_yy: xx,yy=yy,xx #yyの方が大きい
    parents[yy]+=parents[xx]
    parents[xx]=yy  #サイズが小さい木を大きい木に接ぐ

ans=0
while HEN:
    dd= heapq.heappop(HEN)
    d=dd//(10**12) ; a=(dd-d*10**12)//(10**6) ; b=dd%(10**6)
    if find(a)==find(b):continue
    union(a,b) #ループができるようなやつは勝手に飛ばしてくれる
    # MST[a].append(b)
    # MST[b].append(a)
    ans+=d
    #parentsは同じグループかどうかの判定用。だから経路圧縮してもよい。

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    """
    UnionFindTreeのクラス
    
    Attributes:
    n: int: ノード数
    parents: そのノードが属する木の根を格納, 根の場合は-1

    """
    def __init__(self, n):
        """ノード数nで初期化"""
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """ノード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が属するグループと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):
        """xが属するグループの要素数を返す"""
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """x, yが同じグループに属するかどうかを返す"""
        return self.find(x) == self.find(y)

    def members(self, x):
        """xが属するグループ内の要素をリストで返す"""
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """全ての根に対する要素をリストで返す"""
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """グループの総数を返す"""
        return len(self.roots())

    def all_group_members(self):
        """{root: [そのグループの要素リスト]}の辞書を返す"""
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        """printデバッグ用. root: [要素リスト]をstrで返す"""
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def kruskal(edge_list: list, n_V: int):
    """
    クラスカル法
    edge_list: 各要素が(weight, node1, node2)のリスト
    n_V: ノード数
    sortがボトルネックとなりO(|E|log(|E|))
    """
    edge_list = sorted(edge_list) # 重み昇順に整列
    ret = 0
    uf = UnionFind(n_V) # UnionFind
    n_edges = 0
    for w, s, t in edge_list:
        if n_edges == n_V-1: #全域木になったら終了
            break
        if uf.same(s, t):
            #s, tが同じグループの場合,
            #構築するものが木ではなくなってしまう(閉路ができる)
            #のでcontinue
            continue
        
        uf.union(s, t) # s, tを併合
        ret += w
        n_edges += 1
    
    return ret

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

edges = []
x.sort()
y.sort()
for i in range(N-1):
    id1 = x[i][1]
    id2 = x[i+1][1]
    cost = abs(x[i][0]-x[i+1][0])
    edges.append((cost, id1, id2))
for i in range(N-1):
    id1 = y[i][1]
    id2 = y[i+1][1]
    cost = abs(y[i][0]-y[i+1][0])
    edges.append((cost, id1, id2))

ret = kruskal(edges, N)
print(ret)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
#https://note.nkmk.me/python-union-find/

    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n
    
        def find(self, x):
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]
    
        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)
    
            if x == y:
                return
    
            if self.parents[x] > self.parents[y]:
                x, y = y, x
    
            self.parents[x] += self.parents[y]
            self.parents[y] = x
    
        def size(self, x):
            return -self.parents[self.find(x)]
    
        def same(self, x, y):
            return self.find(x) == self.find(y)
    
        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]
    
        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]
    
        def group_count(self):
            return len(self.roots())
    
        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}
    
        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    n=I()
    lisx=[]
    lisy=[]
    edge=[]
    for i in range(n):
        x,y=MI()
        lisx.append([x,i])
        lisy.append([y,i])
    lisx.sort(key=lambda x:x[0])
    lisy.sort(key=lambda x:x[0])
    for i in range(n-1):
        edge.append([lisx[i][1],lisx[i+1][1],lisx[i+1][0]-lisx[i][0]])
        edge.append([lisy[i][1],lisy[i+1][1],lisy[i+1][0]-lisy[i][0]])
    edge.sort(key=lambda x:x[2])
    #print(edge)
    ans=0
    uf=UnionFind(n)
    count=0
    for x,y,z in edge:
        if uf.same(x,y):
            continue
        else:
            uf.union(x,y)
            ans+=z
            count+=1
        if count==n-1:
            break
    print(ans)
        
        
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
#https://note.nkmk.me/python-union-find/

    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n
    
        def find(self, x):
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]
    
        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)
    
            if x == y:
                return
    
            if self.parents[x] > self.parents[y]:
                x, y = y, x
    
            self.parents[x] += self.parents[y]
            self.parents[y] = x
    
        def size(self, x):
            return -self.parents[self.find(x)]
    
        def same(self, x, y):
            return self.find(x) == self.find(y)
    
        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]
    
        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]
    
        def group_count(self):
            return len(self.roots())
    
        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}
    
        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    n=I()
    lisx=[]
    lisy=[]
    edge=[]
    for i in range(n):
        x,y=MI()
        lisx.append([x,i])
        lisy.append([y,i])
    lisx.sort(key=lambda x:x[0])
    lisy.sort(key=lambda x:x[0])
    for i in range(n-1):
        edge.append([lisx[i][1],lisx[i+1][1],lisx[i+1][0]-lisx[i][0]])
        edge.append([lisy[i][1],lisy[i+1][1],lisy[i+1][0]-lisy[i][0]])
    edge.sort(key=lambda x:x[2])
    #print(edge)
    ans=0
    uf=UnionFind(n)
    for x,y,z in edge:
        if uf.same(x,y):
            continue
        else:
            uf.union(x,y)
            ans+=z
    print(ans)
        
        
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from scipy.sparse import *
from scipy.sparse.csgraph import *
N = int(input())
T = [[n]+list(map(int,input().split())) for n in range(N)]
P = set()

for i in [1,2]:
  T.sort(key=lambda a: a[i])
  for j in range(1,N):
    i0,x0,y0 =  T[j-1]
    i1,x1,y1 =  T[j]
    P.add((min(abs(x1-x0),abs(y1-y0)),i0,i1))

d,i,j = zip(*P)
G = csr_matrix((d,(i,j)),shape=(N,N))
print(int(minimum_spanning_tree(G).sum()))

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_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(N, stw):
  # stw = [[s0, t0, w0], [s1, t1, w1], ..., [sn, tn, wn]]
  # stw: s: 始点, t: 終点, w: st間の重み
  # stwはwを小さい順にソートされたものとする
  # s, tを入れ替えたものはいれなくていい
  res = 0
  uf = UnionFind(N)
  for i in range(len(stw)):
    s, t, w = stw[i]
    if not uf.isSameGroup(s, t):
      uf.Unite(s, t)
      res += w
  return res

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

stw = []

ixy = sorted(ixy, key=lambda x:x[1])
for j in range(N-1):
  i, x, y = ixy[j]
  ii, xx, yy = ixy[j+1]
  stw += [[i, ii, min(abs(x-xx), abs(y-yy))]]

ixy = sorted(ixy, key=lambda x:x[2])
for j in range(N-1):
  i, x, y = ixy[j]
  ii, xx, yy = ixy[j+1]
  stw += [[i, ii, min(abs(x-xx), abs(y-yy))]]

stw = sorted(stw, key=lambda x:x[2])
print(kruskal(N, stw))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10**9)

N = int(input())
# XY_L = [[int(_) for _ in input().split()] for __ in range(N)]
X_L = [None] * N
Y_L = [None] * N
for i in range(N):
    _x, _y = map(int, input().split())
    X_L[i] = [_x, i]
    Y_L[i] = [_y, i]

class UnionFind():
    def __init__(self, n):
        self.rank = [1] * n
        self.par = [int(_) for _ in range(n)]

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

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

        if x == y:
            return

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

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



X_L.sort()
Y_L.sort()
dx_l = [None] * (N-1)
dy_l = [None] * (N-1)
for i in range(N-1):
    dx_l[i] = [X_L[i+1][0] - X_L[i][0], X_L[i][1], X_L[i+1][1]]
    dy_l[i] = [Y_L[i+1][0] - Y_L[i][0], Y_L[i][1], Y_L[i+1][1]]

tmp_l = dx_l+dy_l
tmp_l.sort()

UF = UnionFind(N)
ans = 0

for _ in range(2*N-2):
    _d, _i, _j = tmp_l[_]
    if _i >= N or _j >= N:
        print(_i, _j)
    if UF.same(_i, _j):
        continue
    UF.unite(_i, _j)
    ans += _d

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10**9)

N = int(input())
# XY_L = [[int(_) for _ in input().split()] for __ in range(N)]
X_L = [None] * N
Y_L = [None] * N
for i in range(N):
    _x, _y = map(int, input().split())
    X_L[i] = [_x, i]
    Y_L[i] = [_y, i]

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

# class UnionFind():
#     def __init__(self, n):
#         self.rank = [1] * n
#         self.par = [int(_) for _ in range(n)]

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

#     def unite(self, x, y):
#         p_x = self.find(x)
#         p_y = self.find(y)
#         if p_x == p_y:
#             return False
#         if self.rank[p_x] < self.rank[p_y]:
#             self.par[p_x] = p_y
#         else:
#             self.par[p_y] = p_x
#             if self.rank[p_x] == self.rank[p_y]:
#                 self.rank[p_x] += 1
#         return True
    
#     def same(self, x, y):
#         if self.find(x) == self.find(y):
#             return True
#         else:
#             return False

X_L.sort()
Y_L.sort()
dx_l = [None] * (N-1)
dy_l = [None] * (N-1)
for i in range(N-1):
    dx_l[i] = [X_L[i+1][0] - X_L[i][0], X_L[i][1], X_L[i+1][1]]
    dy_l[i] = [Y_L[i+1][0] - Y_L[i][0], Y_L[i][1], Y_L[i+1][1]]

tmp_l = dx_l+dy_l
tmp_l.sort()

UF = UnionFind(N)
ans = 0

for _ in range(2*N-2):
    _d, _i, _j = tmp_l[_]
    if UF.same(_i, _j):
        continue
    UF.unite(_i, _j)
    ans += _d
    # if _ % 1000 == 0:
    #     print(_,ans)



print(ans)

Submission status: Accepted

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

N = int(input())
P = []
for i in range(N):
  x,y = map(int, input().split())
  P.append((x,y,i))
  
data = [10, 20, 30, 40]
row = [0, 0, 1, 1]
col = [1, 2, 0, 2]

#print(csr_matrix((data, (row, col))).toarray())
  
data = []
row = []
col = []

P.sort() 
D = {}
for i in range(N-1):
  a,b,p = P[i]
  c,d,q = P[i+1]
  cost = min(abs(a-c), abs(b-d))
  data.append(cost)
  row.append(p)
  col.append(q)
  data.append(cost)
  row.append(q)
  col.append(p)
  D[(p,q)] = cost
  D[(q,p)] = cost

P.sort(key=itemgetter(1))
for i in range(N-1):
  a,b,p = P[i]
  c,d,q = P[i+1]
  if (p,q) in D:
    continue
  cost = min(abs(a-c), abs(b-d))
  data.append(cost)
  row.append(p)
  col.append(q)
  data.append(cost)
  row.append(q)
  col.append(p)
  D[(p,q)] = cost
  D[(q,p)] = cost

coo = coo_matrix((data, (row, col)), (N, N))
mst = minimum_spanning_tree(coo)
print(int(mst.sum()))

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*n
        self.rank=[-1]*n

    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
        elif self.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y] +=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def size(self,x):
        return -self.root[self.Find_Root(x)]

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

    def roots(self):
        return[i for i,j in enumerate(self.root) if j<0]

    def group_members(self):
        return {i:self.members(i) for i in self.roots()}

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


def kruskal():
    D,M=[],[]

    A,B=sorted(XY),sorted(XY,key=lambda x:x[1])
    for i in range(n-1):
        M.append([abs(A[i][0]-A[i+1][0]),A[i][2],A[i+1][2]])
        M.append([abs(B[i][1]-B[i+1][1]),B[i][2],B[i+1][2]])

    M.sort()
    for i,j,k in M:
        if UnionFind.isSameGroup(j,k) is False:
            UnionFind.Unite(j,k)
            D.append(i)

    return D


n=int(input())
XY=[list(map(int,input().split()))+[i+1] for i in range(n)]
UnionFind=UnionFind(n+1)
print(sum(kruskal()))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop,heapify

N=int(sys.stdin.readline().strip())
V=[]    #頂点の集合 (x座標、y座標、頂点番号)
for v in range(N):   #v:頂点番号
    x,y=tuple(map(int, sys.stdin.readline().split()))
    V.append((x,y,v+1))

#頂点をy軸でソート
V.sort(key=lambda x:(x[0]) )
E=[]    #辺の集合 (辺の長さ、頂点番号、頂点番号)
for i in range(N-1):
    fro_x,fro=V[i][0],V[i][2]
    to_x,to=V[i+1][0],V[i+1][2]
    E.append( (abs(fro_x-to_x),fro,to))

#頂点をx軸でソート
V.sort(key=lambda x:(x[1]) )
for i in range(N-1):
    fro_y,fro=V[i][1],V[i][2]
    to_y,to=V[i+1][1],V[i+1][2]
    E.append( (abs(fro_y-to_y),fro,to))

#隣接リスト
al=[[] for _ in range(N+1)]
for cost,fro,to in E:
    al[fro].append((cost,to))
    al[to].append((cost,fro))

#確定した頂点のリスト
fixed_v=[ 0 for _ in range(N+1) ]
hq=[]   #最短の辺を取得するためのヒープキュー
V=[1]   #次に処理する頂点が常に1つだけ入る、頂点1が常にスタート地点

ans=0
while V:
    cur=V.pop()
    #確定した頂点の更新
    fixed_v[cur]=1
    #頂点curから出て行く辺を全てhqに入れる
    for cost,to in al[cur]:
        heappush(hq,(cost,to))
    while hq:
        #hqから辺を取り出す
        cost,to=heappop(hq)
        #未確定の頂点が見つかれば、次に見る頂点としてVにappendし、whileループはbreak
        if fixed_v[to]==0:
            ans+=cost
            V.append(to)
            break
        #確定済みの頂点の場合は、#未確定の頂点が見つかるまでheapqからpopする

print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop,heapify

N=int(sys.stdin.readline().strip())
V=[]    #頂点の集合 (x座標、y座標、頂点番号)
for v in range(N):   #v:頂点番号
    x,y=tuple(map(int, sys.stdin.readline().split()))
    V.append((x,y,v+1))

#頂点をy軸でソート
V.sort(key=lambda x:(x[0]) )
E=[]    #辺の集合 (辺の長さ、頂点番号、頂点番号)
for i in range(N-1):
    fro_x,fro=V[i][0],V[i][2]
    to_x,to=V[i+1][0],V[i+1][2]
    E.append( (abs(fro_x-to_x),fro,to))

#頂点をx軸でソート
V.sort(key=lambda x:(x[1]) )
for i in range(N-1):
    fro_y,fro=V[i][1],V[i][2]
    to_y,to=V[i+1][1],V[i+1][2]
    E.append( (abs(fro_y-to_y),fro,to))


al=[[] for _ in range(N+1)]
for cost,fro,to in E:
    al[fro].append((cost,to))
    al[to].append((cost,fro))


#確定した頂点のリスト
fixed_v=[ 0 for _ in range(N+1) ]
hq=[]   #最短の辺を取得するためのヒープキュー
V=[1]   #次に処理する頂点が常に1つだけ入る、頂点1が常にスタート地点

ans=0
while V:
    cur=V.pop()
    #確定した頂点の更新
    fixed_v[cur]=1
    #頂点curから出て行く辺を全てhqに入れる
    for cost,to in al[cur]:
        heappush(hq,(cost,to))
    while hq:
        #hqから辺を取り出す
        cost,to=heappop(hq)
        #未確定の頂点が見つかれば、次に見る頂点としてVにappendし、whileループはbreak
        if fixed_v[to]==0:
            ans+=cost
            V.append(to)
            break
        #確定済みの頂点の場合は、#未確定の頂点が見つかるまでheapqからpopする

print ans