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:
N = int(input())
Points = [[i] + list(map(int, input().split())) for i in range(N)]

# x, yそれぞれについてソートして、一番近いところを見れば十分
Edges = []
Points.sort(key=lambda p: p[1])
for i in range(N - 1):
    n1, x1, y1 = Points[i]
    n2, x2, y2 = Points[i + 1]
    Edges.append([n1, n2, x2 - x1])

Points.sort(key=lambda p: p[2])
for i in range(N - 1):
    n1, x1, y1 = Points[i]
    n2, x2, y2 = Points[i + 1]
    Edges.append([n1, n2, y2 - y1])


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

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

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

        if x == y:
            return

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

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


uf = UnionFind(N)
Edges.sort(key=lambda e: e[2], reverse=True)
MST_cost = 0
i = 0

# 辺のコストが小さいものから、閉路を作らないように、木を構成する
# 最小全域木の必要辺は(頂点数-1)本
while i != N - 1:
    x, y, cost = Edges.pop()
    # 同じ辺集合に属していないならば（閉路が生まれないならば）
    if not uf.same_check(x, y):
        MST_cost += cost
        uf.union(x, y)
        i += 1

print(MST_cost)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
T = [[int(_) for _ in input().split()] for i in range(N)]


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

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

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

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


E = []
indices_x = np.argsort([x for x, y in T])
indices_y = np.argsort([y for x, y in T])

for i in range(N - 1):
    a, _ = T[indices_x[i]]
    c, _ = T[indices_x[i + 1]]
    E.append((indices_x[i], indices_x[i + 1], abs(a - c)))

    _, b = T[indices_y[i]]
    _, d = T[indices_y[i + 1]]
    E.append((indices_y[i], indices_y[i + 1], abs(b - d)))

uf = UnionFind(N)
ans = 0
for i, j, cost in sorted(E, key=lambda x: x[2]):
    if uf.same_check(i, j):
        continue

    uf.union(i, j)
    ans += cost

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

class UnionFind:
    def __init__(self, n: int) -> None:
        #マイナスならルートでその深さを表す。プラスならルートのノードを指す。
        self.nodes = [-1]*n
 
    def find_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find_root(self.nodes[x])
            return self.nodes[x]
 
    def unite(self, x: int, y: int) -> None:
        x, y = self.find_root(x), self.find_root(y)
        #浅い方につなぐ
        if (x != y):
            if (x < y):
                self.nodes[y] += self.nodes[x]
                self.nodes[x] = y
            else:
                self.nodes[x] += self.nodes[y]
                self.nodes[y] = x
        
    def is_same(self, x: int, y: int) -> bool:
        return self.find_root(x) == self.find_root(y)

from operator import itemgetter

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

#X,Yそれぞれでソートして各都市の最短距離を求める
G_sorted_by_x = sorted(G, key=itemgetter(1))
G_sorted_by_y = sorted(G, key=itemgetter(2))
R = []
for i in range(N-1):
    i0, x0, _ = G_sorted_by_x[i]
    i1, x1, _ = G_sorted_by_x[i+1]
    R.append((x1-x0, i0, i1))
    i0, _, y0 = G_sorted_by_y[i]
    i1, _, y1 = G_sorted_by_y[i+1]
    R.append((y1-y0, i0, i1))

R_sorted_by_cost = sorted(R, key=itemgetter(0))

#print(R_sorted_by_cost)

uf = UnionFind(N)
total_cost = 0
for cost, i, j in R_sorted_by_cost:
    if (not uf.is_same(i, j)):
        uf.unite(i, j)
        total_cost += cost
    #print((cost, i, j))
print(total_cost)

Submission status: Accepted

Solution code:
from collections import defaultdict 
  
#Class to represent a graph 
class Graph: 
  
    def __init__(self,vertices): 
        self.V= vertices #No. of vertices 
        self.graph = [] # default dictionary  
                                # to store graph 
          
   
    # function to add an edge to graph 
    def addEdge(self,u,v,w): 
        self.graph.append([u,v,w]) 
  
    # A utility function to find set of an element i 
    # (uses path compression technique) 
    def find(self, parent, i): 
        if parent[i] == i: 
            return i 
        return self.find(parent, parent[i]) 
  
    # A function that does union of two sets of x and y 
    # (uses union by rank) 
    def union(self, parent, rank, x, y): 
        xroot = self.find(parent, x) 
        yroot = self.find(parent, y) 
  
        # Attach smaller rank tree under root of  
        # high rank tree (Union by Rank) 
        if rank[xroot] < rank[yroot]: 
            parent[xroot] = yroot 
        elif rank[xroot] > rank[yroot]: 
            parent[yroot] = xroot 
  
        # If ranks are same, then make one as root  
        # and increment its rank by one 
        else : 
            parent[yroot] = xroot 
            rank[xroot] += 1
  
    # The main function to construct MST using Kruskal's  
        # algorithm 
    def KruskalMST(self): 
  
        result =[] #This will store the resultant MST 
  
        i = 0 # An index variable, used for sorted edges 
        e = 0 # An index variable, used for result[] 
  
            # Step 1:  Sort all the edges in non-decreasing  
                # order of their 
                # weight.  If we are not allowed to change the  
                # given graph, we can create a copy of graph 
        self.graph =  sorted(self.graph,key=lambda item: item[2]) 
  
        parent = [] ; rank = [] 
  
        # Create V subsets with single elements 
        for node in range(self.V): 
            parent.append(node) 
            rank.append(0) 
      
        # Number of edges to be taken is equal to V-1 
        while e < self.V -1 : 
  
            # Step 2: Pick the smallest edge and increment  
                    # the index for next iteration 
            u,v,w =  self.graph[i] 
            i = i + 1
            x = self.find(parent, u) 
            y = self.find(parent ,v) 
  
            # If including this edge does't cause cycle,  
                        # include it in result and increment the index 
                        # of result for next edge 
            if x != y: 
                e = e + 1     
                result.append([u,v,w]) 
                self.union(parent, rank, x, y)             
            # Else discard the edge 
  
        # print the contents of result[] to display the built MST 
        ans = 0
        for u,v,weight  in result:
        	ans += weight
        print ans

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

g = Graph(n)
for i in range(n-1):
	g.addEdge(arr1[i][2],arr1[i+1][2],arr1[i+1][0]-arr1[i][0])
arr2 = sorted(arr,key = lambda x : x[1])
for i in range(n-1):
	g.addEdge(arr2[i][2],arr2[i+1][2],arr2[i+1][1]-arr2[i][1])
g.KruskalMST()

Submission status: Accepted

Solution code:
#065-D
#クラスカル法
import heapq
V=int(input())#Eは辺の数、Vは頂点の数
vlist=[]
eque=[]
for i in range(V):
    x,y=map(int,input().split())
    vlist.append([i,x,y])

vlist.sort(key=lambda x:x[1])
for i in range(V-1):
    heapq.heappush(eque,[vlist[i+1][1]-vlist[i][1],vlist[i][0],vlist[i+1][0]])

vlist.sort(key=lambda x:x[2])
for i in range(V-1):
    heapq.heappush(eque,[vlist[i+1][2]-vlist[i][2],vlist[i][0],vlist[i+1][0]])


#Union-Find木
par=[]
rank=[]
def init(a): #初期化
    for i in range(a):
        par.append(i)
        rank.append(0)
def find(x): #根を見つける
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
    return par[x]
def unite(x,y): #併合
    x=find(x)
    y=find(y)
    if rank[x]==rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x]+=1
    return
def same(x,y): #同じ集合か判定
    return find(x)==find(y)

init(V) #同じ木に属しているかどうかはUFTで判断する、初めは全部孤立した木

res=0 #合計コスト
while len(eque)!=0:
    te=heapq.heappop(eque)
    cost,u,v=te[0],te[1],te[2]
    if same(u,v): #同じ木に属していたら閉路ができるのでcontinue
        continue
    res+=cost
    unite(u,v) #辺を追加したら同じ木にする

print(res)

Submission status: Accepted

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


class UnionFind(object):
    def __init__(self, N):
        self.__root = list(range(N))
    

    def root(self, x):
        if self.__root[x] == x:
            return x
        else:
            # root abbreviation
            self.__root[x] = self.root(self.__root[x])
            return self.__root[x]

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


    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if (x == y):
            return
        self.__root[y] = x
        return


# assuming that the vertices are 0, 1, ..., N - 1
# if V^2 >> E, use a hashmap representation of w
# time complexity: O(ElgE)
# space complexity: O(E)
def prim(adj, w):
    num_vertices = len(adj)
    # initialize
    min_cost = [float('inf')] * num_vertices
    min_cost[0] = 0
    used = [False] * num_vertices
    priority_queue = [(0, 0)]
    total_cost = 0

    while priority_queue:
        cost, vertex = heappop(priority_queue)
        if cost > min_cost[vertex] or used[vertex]:
            continue
        used[vertex] = True
        total_cost += cost

        for neighbor in adj[vertex]:
            cost_v_to_n = w[(vertex, neighbor)]
            if min_cost[neighbor] > cost_v_to_n:
                min_cost[neighbor] = cost_v_to_n
                heappush(priority_queue, (cost_v_to_n, neighbor))

    return total_cost


# input should be [(s1, t1, cost1), (s2, t2, cost2), ...]
# time complexity: O(ElgV)
# space complexity: O(E)
def kruskal(edges_with_cost, num_vertices):
    # num_edges = len(edges_with_cost)
    edges_with_cost.sort(key=lambda x: x[-1])
    uf = UnionFind(num_vertices)
    total_cost = 0
    for source, target, cost in edges_with_cost:
        if not uf.same(source, target):
            uf.unite(source, target)
            total_cost += cost
    
    return total_cost


N = int(fin())
coords = [[int(elem) for elem in fin().split()] + [i] for i in range(N)]

# edges_with_cost = []
# # sort coords in increasing order of x
# coords.sort(key=lambda x: x[0])
# for i, (x, _, vertex) in enumerate(coords[:-1]):
#     next_x, _, next_vertex = coords[i + 1]
#     weight = next_x - x
#     edges_with_cost.append((vertex, next_vertex, weight))
#     edges_with_cost.append((next_vertex, vertex, weight))


# # sort coods in increasing order of y
# coords.sort(key=lambda x: x[1])
# for i, (_, y, vertex) in enumerate(coords[:-1]):
#     _, next_y, next_vertex = coords[i + 1]
#     weight = next_y - y
#     edges_with_cost.append((vertex, next_vertex, weight))
#     edges_with_cost.append((next_vertex, vertex, weight))

# print(kruskal(edges_with_cost, N))

adj = [set() for _ in range(N)]
w = {}
# sort coords in increasing order of x
coords.sort(key=lambda x: x[0])
for i, (x, _, vertex) in enumerate(coords[:-1]):
    next_x, _, next_vertex = coords[i + 1]
    adj[vertex].add(next_vertex)
    adj[next_vertex].add(vertex)
    weight = next_x - x
    if (vertex, next_vertex) not in w or w[(vertex, next_vertex)] > weight:
        w[(vertex, next_vertex)] = weight
    if (next_vertex, vertex) not in w or w[(next_vertex, vertex)] > weight:
        w[(next_vertex, vertex)] = weight

# sort coods in increasing order of y
coords.sort(key=lambda x: x[1])
for i, (_, y, vertex) in enumerate(coords[:-1]):
    _, next_y, next_vertex = coords[i + 1]
    adj[vertex].add(next_vertex)
    adj[next_vertex].add(vertex)
    weight = next_y - y
    if (vertex, next_vertex) not in w or w[(vertex, next_vertex)] > weight:
        w[(vertex, next_vertex)] = weight
    if (next_vertex, vertex) not in w or w[(next_vertex, vertex)] > weight:
        w[(next_vertex, vertex)] = weight

print(prim(adj, w))

Submission status: Accepted

Solution code:
import sys
fin = sys.stdin.readline
from heapq import heappop, heappush
from operator import itemgetter

# assuming that the vertices are 0, 1, ..., N - 1
# if V^2 >> E, use a hashmap representation of w
# time complexity: O(ElgE)
# space complexity: O(E)
def prim(adj, w):
    num_vertices = len(adj)
    # initialize
    min_cost = [float('inf')] * num_vertices
    min_cost[0] = 0
    used = [False] * num_vertices
    priority_queue = [(0, 0)]
    total_cost = 0

    while priority_queue:
        cost, vertex = heappop(priority_queue)
        if cost > min_cost[vertex] or used[vertex]:
            continue
        used[vertex] = True
        total_cost += cost

        for neighbor in adj[vertex]:
            cost_v_to_n = w[(vertex, neighbor)]
            if min_cost[neighbor] > cost_v_to_n:
                min_cost[neighbor] = cost_v_to_n
                heappush(priority_queue, (cost_v_to_n, neighbor))

    return total_cost


N = int(fin())
coords = [[int(elem) for elem in fin().split()] + [i] for i in range(N)]

adj = [set() for _ in range(N)]
w = {}

# sort coords in increasing order of x
# coords.sort(key=lambda x: x[0])
coords.sort(key=itemgetter(0))
for i, (x, _, vertex) in enumerate(coords[:-1]):
    next_x, _, next_vertex = coords[i + 1]
    adj[vertex].add(next_vertex)
    adj[next_vertex].add(vertex)
    weight = next_x - x
    if (vertex, next_vertex) not in w or w[(vertex, next_vertex)] > weight:
        w[(vertex, next_vertex)] = weight
    if (next_vertex, vertex) not in w or w[(next_vertex, vertex)] > weight:
        w[(next_vertex, vertex)] = weight

# sort coods in increasing order of y
# coords.sort(key=lambda x: x[1])
coords.sort(key=itemgetter(1))
for i, (_, y, vertex) in enumerate(coords[:-1]):
    _, next_y, next_vertex = coords[i + 1]
    adj[vertex].add(next_vertex)
    adj[next_vertex].add(vertex)
    weight = next_y - y
    if (vertex, next_vertex) not in w or w[(vertex, next_vertex)] > weight:
        w[(vertex, next_vertex)] = weight
    if (next_vertex, vertex) not in w or w[(next_vertex, vertex)] > weight:
        w[(next_vertex, vertex)] = weight

print(prim(adj, w))

Submission status: Accepted

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


# assuming that the vertices are 0, 1, ..., N - 1
# if V^2 >> E, use a hashmap representation of w
# time complexity: O(ElgE)
# space complexity: O(E)
def prim(adj, w):
    num_vertices = len(adj)
    # initialize
    min_cost = [float('inf')] * num_vertices
    min_cost[0] = 0
    used = [False] * num_vertices
    priority_queue = [(0, 0)]
    total_cost = 0

    while priority_queue:
        cost, vertex = heappop(priority_queue)
        if cost > min_cost[vertex] or used[vertex]:
            continue
        used[vertex] = True
        total_cost += cost

        for neighbor in adj[vertex]:
            cost_v_to_n = w[(vertex, neighbor)]
            if min_cost[neighbor] > cost_v_to_n:
                min_cost[neighbor] = cost_v_to_n
                heappush(priority_queue, (cost_v_to_n, neighbor))

    return total_cost


N = int(fin())
coords = [[int(elem) for elem in fin().split()] + [i] for i in range(N)]

adj = [set() for _ in range(N)]
w = {}

# sort coords in increasing order of x
coords.sort(key=lambda x: x[0])
for i, (x, _, vertex) in enumerate(coords[:-1]):
    next_x, _, next_vertex = coords[i + 1]
    adj[vertex].add(next_vertex)
    adj[next_vertex].add(vertex)
    weight = next_x - x
    if (vertex, next_vertex) not in w or w[(vertex, next_vertex)] > weight:
        w[(vertex, next_vertex)] = weight
    if (next_vertex, vertex) not in w or w[(next_vertex, vertex)] > weight:
        w[(next_vertex, vertex)] = weight

# sort coods in increasing order of y
coords.sort(key=lambda x: x[1])
for i, (_, y, vertex) in enumerate(coords[:-1]):
    _, next_y, next_vertex = coords[i + 1]
    adj[vertex].add(next_vertex)
    adj[next_vertex].add(vertex)
    weight = next_y - y
    if (vertex, next_vertex) not in w or w[(vertex, next_vertex)] > weight:
        w[(vertex, next_vertex)] = weight
    if (next_vertex, vertex) not in w or w[(next_vertex, vertex)] > weight:
        w[(next_vertex, vertex)] = weight


print(prim(adj, w))

Submission status: Accepted

Solution code:
from heapq import *
def find(A,x) -> int:
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a

def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

N = int( input())
X = [(0,0)]*N
Y = [(0,0)]*N
E = [(0,0)]*N
for i in range(N):
    x, y = map( int, input().split())
    X[i] = (x,i)
    Y[i] = (y,i)
    E[i] = (x,y)
X.sort()
Y.sort()
H = []
heapify(H)
for i in range(N-1):
    x1, j1 = X[i]
    x2, j2 = X[i+1]
    y1, k1 = Y[i]
    y2, k2 = Y[i+1]
    heappush(H,(x2-x1, j1, j2))
    heappush(H, (y2-y1, k1, k2))
ans = 0
V = [ i for i in range(N)]
while H:
    w,s,t = heappop(H)
    if find(V,s) != find(V,t):
        union(V,s,t)
        ans += w
print(ans)

Submission status: Accepted

Solution code:
from heapq import *
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a

def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

N = int( input())
X = [(0,0)]*N
Y = [(0,0)]*N
E = [(0,0)]*N
for i in range(N):
    x, y = map( int, input().split())
    X[i] = (x,i)
    Y[i] = (y,i)
    E[i] = (x,y)
X.sort()
Y.sort()
H = []
heapify(H)
for i in range(N-1):
    x1, j1 = X[i]
    x2, j2 = X[i+1]
    y1, k1 = Y[i]
    y2, k2 = Y[i+1]
    heappush(H,(x2-x1, j1, j2))
    heappush(H, (y2-y1, k1, k2))
ans = 0
V = [ i for i in range(N)]
while H:
    w,s,t = heappop(H)
    if find(V,s) != find(V,t):
        union(V,s,t)
        ans += w
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
z = [tuple(map(int,input().split())) for i in range(N)]
z.sort()
y = [(z[i][1],i) for i in range(N)]
y.sort()
cost = [[] for i in range(N)]
for i in range(N-1):
    j = y[i][1]
    cost[i].append((i-1,min(abs(z[i][0]-z[i-1][0]),abs(z[i][1]-z[i-1][1]))))
    j_ = y[i-1][1]
    cost[j].append((j_,min(abs(y[i][0]-y[i-1][0]),abs(z[j][0]-z[j_][0]))))
    cost[i].append((i+1,min(abs(z[i+1][0]-z[i][0]),abs(z[i+1][1]-z[i][1]))))
    j_ = y[i+1][1]
    cost[j].append((j_,min(abs(y[i+1][0]-y[i][0]),abs(z[j_][1]-z[j][1]))))

i = N-1
j = y[i][1]
cost[i].append((i-1,min(abs(z[i][0]-z[i-1][0]),abs(z[i][1]-z[i-1][1]))))
j_ = y[i-1][1]
cost[j].append((j_,min(abs(y[i][0]-y[i-1][0]),abs(z[j][0]-z[j_][0]))))


import heapq

def prim(cost):
    V = len(cost)
    res = 0
    mincost = [float('inf')]*V
    used = [False]*V
    hq = []
    mincost[0] = 0
    heapq.heappush(hq,(0,0))
    while hq:
        weight,u = heapq.heappop(hq)
        if not used[u]:
            used[u] = True
            res += weight
            mincost[u] = weight
            for v, v_cost in cost[u]:
                if not used[v]:
                    heapq.heappush(hq,(v_cost,v))
    return res

print(prim(cost))

Submission status: Accepted

Solution code:
N = int(input())
z = [tuple(map(int,input().split())) for i in range(N)]
z.sort()
y = [(z[i][1],i) for i in range(N)]
y.sort()
cost = [[] for i in range(N)]
for i in range(N-1):
    j = y[i][1]
    cost[i].append((i-1,min(abs(z[i][0]-z[i-1][0]),abs(z[i][1]-z[i-1][1]))))
    j_ = y[i-1][1]
    cost[j].append((j_,min(abs(y[i][0]-y[i-1][0]),abs(z[j][0]-z[j_][0]))))
    cost[i].append((i+1,min(abs(z[i+1][0]-z[i][0]),abs(z[i+1][1]-z[i][1]))))
    j_ = y[i+1][1]
    cost[j].append((j_,min(abs(y[i+1][0]-y[i][0]),abs(z[j_][1]-z[j][1]))))

i = N-1
j = y[i][1]
cost[i].append((i-1,min(abs(z[i][0]-z[i-1][0]),abs(z[i][1]-z[i-1][1]))))
j_ = y[i-1][1]
cost[j].append((j_,min(abs(y[i][0]-y[i-1][0]),abs(z[j][0]-z[j_][0]))))


import heapq

def prim(cost):
    V = len(cost)
    res = 0
    mincost = [float('inf')]*V
    used = [False]*V
    hq = []
    mincost[0] = 0
    heapq.heappush(hq,(0,0))
    done = 0
    while hq:
        weight,u = heapq.heappop(hq)
        if not used[u]:
            used[u] = True
            done += 1
            res += weight
            mincost[u] = weight
            for v, v_cost in cost[u]:
                if not used[v]:
                    heapq.heappush(hq,(v_cost,v))
            if done == V:
                break
    return res

print(prim(cost))

Submission status: Accepted

Solution code:
import heapq
import sys

sys.setrecursionlimit(10**5)

def add(i,pj,T):
    if T[i]!=i:
        add(T[i],pj,T)
    T[i]=pj
    
def parent(i,T):
    if T[i]!=i:
        T[i]= parent(T[i],T)
        return T[i]
    else:
        return i

N=int(input())
town=[]
for i in range(N):
    x,y=list(map(int,input().split()))
    town.append([i,x,y])
townX=sorted(town,key=lambda x:x[1])
townY=sorted(town,key=lambda x:x[2])
road=[]
for i in range(1,N):
    heapq.heappush(road,[townX[i][1]-townX[i-1][1],townX[i-1][0],townX[i][0]])
for i in range(1,N):
    heapq.heappush(road,[townY[i][2]-townY[i-1][2],townY[i-1][0],townY[i][0]])

vi=0
ans=0
tree=[i for i in range(N)]
rank=[0 for i in range(N)]
while vi<N-1:
    d,u,v = heapq.heappop(road)
    pu=parent(u,tree)
    pv=parent(v,tree)
    ru=rank[pu]
    rv=rank[pv]
    if pu == pv:
        continue
    elif ru<rv:
        add(u,pv,tree)
    elif ru==rv:
        add(u,pv,tree)
        rank[pu]+=1
    else:
        add(v,pu,tree)
    vi+=1
    ans+=d
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq
import sys
input = sys.stdin.readline

n = int(input())
a = [[] for _ in range(n)]
b = [[] for _ in range(n)]
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a[i]=[xy[0],i]
    b[i]=[xy[1],i]

a.sort()
b.sort()
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
#d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
totalcost = 0 
while h:
    cost, node = heapq.heappop(h)
    #if visited[node] != True and cost < d[node]:
    if visited[node] != True:        
        #d[node] = cost
        visited[node] = True
        totalcost += cost
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]]:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(totalcost)

Submission status: Accepted

Solution code:
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N)]

xs = []
ys = []
for i,(x,y) in enumerate(src):
    xs.append((x,i))
    ys.append((y,i))
xs.sort()
ys.sort()

es = []
for (x1,i1),(x2,i2) in zip(xs,xs[1:]):
    es.append((x2-x1, i1, i2))
for (y1,i1),(y2,i2) in zip(ys,ys[1:]):
    es.append((y2-y1, i1, i2))
es.sort()

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

ans = 0
uf = UnionFind(N)
for d,a,b in es:
    if uf.is_same(a,b): continue
    uf.unite(a,b)
    ans += d
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

class UnionFind:
    def __init__(self, node:int) -> None:
        self.n = node
        self.par = [i for i in range(self.n)]
        self.rank = [0 for i in range(self.n)]
        
    def find(self, x:int) -> int:
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def unite(self, x:int, y:int) -> bool:
        if self.isSame(x,y):
            #print("x and y has already united")
            return False
        
        rx = self.find(x)
        ry = self.find(y)
        
        if self.rank[rx] < self.rank[ry]:
            self.par[rx] = self.par[ry]
        else:
            self.par[ry] = self.par[rx]
            
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
                
        return True
                
    
    def isSame(self, x:int, y:int) -> bool:
        return self.find(x) == self.find(y)
    
    
# edgesは(cost, prev_node, nex_node)をE本格納しているリスト
def kruskal(edges: list, node_num: int) -> int:
    edges.sort(key=lambda x:x[0])
    
    uf = UnionFind(node_num)
    rem = node_num-1
    ans = 0
    
    for cost, prev, nex in edges:
        if uf.find(prev) != uf.find(nex):
            uf.unite(prev, nex)
            ans += cost
            rem -= 1
            
        if rem == 0:
            break
        
    return ans

n = ni()
city = []

for i in range(n):
    city.append([i] + list(li()))

# x,y順にソートして2(N-1)本の辺の候補を出す (cost, from, to)
edges = []

city.sort(key=lambda x:x[1])
for i in range(n-1):
    edges.append((city[i+1][1] - city[i][1], city[i][0], city[i+1][0]))

city.sort(key=lambda x:x[2])
for i in range(n-1):
    edges.append((city[i+1][2] - city[i][2], city[i][0], city[i+1][0]))

# クラスカル法
ans = kruskal(edges, n)

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        #親要素のノード番号を格納。par[x] == xのときそのノードはroot
        self.par = [i for i in range(n)]
        #木の高さ（初期状態では0）
        self.rank = [0] * 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 same(self, x, y):
        # xとyが同じ集合に属するかを判定
        return self.find(x) == self.find(y)

    def union(self, x, y):
        #併合する
        #まず根を探す
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
N = int(input())
towns = [[i] + list(map(int, input().split())) for i in range(N)]
roads = []
towns.sort(key = lambda x: x[1])
for i in range(N - 1):
    num1, x1, y1 = towns[i]
    num2, x2, y2 = towns[i + 1]
    dist = min(abs(x1 - x2), abs(y1 - y2))
    roads.append([dist, num1, num2])
towns.sort(key = lambda x: x[2])
for i in range(N - 1):
    num1, x1, y1 = towns[i]
    num2, x2, y2 = towns[i + 1]
    dist = min(abs(x1 - x2), abs(y1 - y2))
    roads.append([dist, num1, num2])
roads.sort()
ans = 0
tree = UnionFind(N)
for road in roads:
    d, s, t = road
    if not tree.same(s, t):
        ans += d
        tree.union(s, t)

print(ans)

Submission status: Accepted

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

recx = sorted(rec, key=lambda s: s[1])
recy = sorted(rec, key=lambda s: s[2])

G = []
for i in range(1, N):
    costx = min(abs(recx[i][1] - recx[i - 1][1]), abs(recx[i][2] - recx[i - 1][2]))
    costy = min(abs(recy[i][1] - recy[i - 1][1]), abs(recy[i][2] - recy[i - 1][2]))
    G.append((recx[i][0], recx[i - 1][0], costx))
    G.append((recy[i][0], recy[i - 1][0], costy))

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


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


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if rank[x] > rank[y]:
        par[y] = x
    else:
        par[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1


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


G = sorted(G, key=lambda s: s[2])
num = 0
for e in G:
    if not same(e[0], e[1]):
        unite(e[0], e[1])
        num += e[2]

print(num)