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
sys.setrecursionlimit(10**7)
from collections import defaultdict

def init(n):
    return list(range(n+1))

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

def sameset(lis, x, y):
    return find(lis, x) == find(lis, y)

def union(lis, x, y):
    x = find(lis, x)
    y = find(lis, y)
    if x != y:
        lis[x] = y

N = int(input())
union_find_tree = init(N)

town = []

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

x_sorted_town = sorted(town, key=lambda x: x[1])
y_sorted_town = sorted(town, key=lambda x: x[2])

graph = []

pre_tx = x_sorted_town[0]
pre_ty = y_sorted_town[0]
pre_nx = town[pre_tx[0]]
pre_ny = town[pre_ty[0]]
for tx, ty in zip(x_sorted_town[1:], y_sorted_town[1:]):
    nx = town[tx[0]]
    ny = town[ty[0]]
    wx = min(abs(tx[1] - pre_tx[1]), abs(nx[2] - pre_nx[2]))
    wy = min(abs(ty[2] - pre_ty[2]), abs(ny[1] - pre_ny[1]))
    graph.append((nx[0], pre_nx[0], wx))
    graph.append((ny[0], pre_ny[0], wy))
    pre_tx = tx
    pre_ty = ty
    pre_nx = nx
    pre_ny = ny

cost = 0
for (s,t,w) in sorted(graph, key=lambda x: x[2]):
    if not sameset(union_find_tree,s,t):
        union(union_find_tree,s,t)
        cost += w
print(cost)

Submission status: Accepted

Solution code:
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
def examD():
    N = I()
    x = [[] for _ in range(N)]; y = [[] for _ in range(N)]
    for i in range(N):
        a, b = LI()
        x[i] = (a-1,i)
        y[i] = (b-1,i)
    v = [ i for i in range(N)]
    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
#    print(H)
#    print(v)
    while H:
        w, s, t = heappop(H)
        if find(v, s) != find(v, t):
            union(v, s, t)
            ans += w
    print(ans)

import sys
import copy
import bisect
from heapq import *
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
n=int(input())
xy=[]
yx=[]
for i in range(n):
    x,y=map(int,input().split())
    xy.append([x,y,i])
    yx.append([y,x,i])
xy.sort()
yx.sort()
data=[[0,0] for i in range(n)]
for i in range(n):
    x,y,a=xy[i]
    data[a][0]=i
    y,x,a=yx[i]
    data[a][1]=i
ans=0
que=[[0,0]]
flag=[0]*n
count=0
while count<=n:
    l,a=heappop(que)
    if flag[a]==1:
        continue
    ans+=l
    flag[a]=1
    count+=1
    if count==n:
        break
    b,c=data[a]
    xb=xy[b][0]
    yc=yx[c][0]
    if 1<=b<=n-2:
        xd,yd,d=xy[b-1]
        xe,ye,e=xy[b+1]
        if flag[d]==0:
            heappush(que,[abs(xd-xb),d])
        if flag[e]==0:
            heappush(que,[abs(xe-xb),e])
    elif b==0:
        xe,ye,e=xy[1]
        if flag[e]==0:
            heappush(que,[abs(xb-xe),e])
    else:
        xd,yd,d=xy[n-2]
        if flag[d]==0:
            heappush(que,[abs(xb-xd),d])
    if 1<=c<=n-2:
        yg,xg,g=yx[c+1]
        yf,xf,f=yx[c-1]
        if flag[f]==0:
            heappush(que,[abs(yf-yc),f])
        if flag[g]==0:
            heappush(que,[abs(yg-yc),g])
    elif c==0:
        yg,xg,g=yx[1]
        if flag[g]==0:
            heappush(que,[abs(yg-yc),g])
    else:
        yf,xf,f=yx[n-2]
        if flag[f]==0:
            heappush(que,[abs(yf-yc),f])
print(ans)

Submission status: Accepted

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

B = [[j for j in i] for i in A]

A.sort()
B.sort(key=lambda x:x[1])

M = []
for i in range(n-1):
    M.append([A[i][2], A[i+1][2], A[i+1][0]-A[i][0]])
    M.append([B[i][2], B[i+1][2], B[i+1][1]-B[i][1]])

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 size(self, x):
        if self.parents[x] < 0:
            return -self.parents[x]
        else:
            self.parents[x] = self.size(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
# print(M)

M.sort(key=lambda x:x[2])
ans = 0
U = UnionFind(n+1)
e = 0
for i in range(len(M)):
    if e == n-1:
        break
    if U.find(M[i][0]) != U.find(M[i][1]):
        U.union(M[i][0], M[i][1])
        ans += M[i][2]
        e += 1
        # print(M[i])

print(ans)

Submission status: Accepted

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

B = [[j for j in i] for i in A]

A.sort()
B.sort(key=lambda x:x[1])

M = []
for i in range(n-1):
    M.append([A[i][2], A[i+1][2], A[i+1][0]-A[i][0]])
    M.append([B[i][2], B[i+1][2], B[i+1][1]-B[i][1]])

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 size(self, x):
        if self.parents[x] < 0:
            return -self.parents[x]
        else:
            self.parents[x] = self.size(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
# print(M)

M.sort(key=lambda x:x[2])
ans = 0
U = UnionFind(n+1)
for i in range(len(M)):
    if U.find(M[i][0]) != U.find(M[i][1]):
        U.union(M[i][0], M[i][1])
        ans += M[i][2]
        # print(M[i])

print(ans)

Submission status: Accepted

Solution code:
import heapq

class UnionFind:
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rnk = [0]*(n+1)
		self.Maxroot = -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 
		elif self.rnk[x] > self.rnk[y]:
			self.root[x] += self.root[y]
			if self.root[x] < self.Maxroot:
				self.Maxroot = self.root[x]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			if self.root[y] < self.Maxroot:
				self.Maxroot = self.root[y]
			self.root[x] = y
			if self.rnk[x] == self.rnk[y]:
				self.rnk[y] += 1

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

	def Count(self, x):
		return self.root[self.Find_Root(x)] * (-1)

N = int(input())
P = [list(map(int, input().split()))+[i] for i in range(N)]
Px = sorted(P)
Py = sorted(P, key = lambda x: x[1])

q = []
for i in range(N-1):
	x1, dumy1, p1 = Px[i]
	x2, dumy2, p2 = Px[i+1]

	heapq.heappush(q, [x2-x1, p1, p2])

for i in range(N-1):
	dumy1, y1, p1 = Py[i]
	dumy2, y2, p2 = Py[i+1]

	heapq.heappush(q, [y2-y1, p1, p2])

solve = UnionFind(N)

ans = 0
while not (solve.Maxroot == N * (-1)):
	d, p1, p2 = heapq.heappop(q)
	if not solve.isSameGroup(p1, p2):
		solve.Unite(p1, p2)
		ans += d

print(ans)

Submission status: Accepted

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

n = int(input())
x_list, y_list = [], []
for i in range(n):
    a, b = [ int(v) for v in input().split() ]
    x_list.append((a,b))
    y_list.append((b,a))
x_list.sort()
y_list.sort()

def swap(i):
    return (i[1],i[0])

def simplehash(i, r = 0):
    if r == 1:
        a, b = swap(i)
    else:
        a, b = i
    return a*10**10+b

x_node = [ ( (x_list[i+1][0] - x_list[i][0]), simplehash(x_list[i]), simplehash(x_list[i+1]) ) for i in range(n-1) ]
y_node = [ ( (y_list[i+1][0] - y_list[i][0]), simplehash(y_list[i],1), simplehash(y_list[i+1],1) ) for i in range(n-1) ]
node_set = set([])
for i in x_node:
    node_set.add(i[1])
    node_set.add(i[2])
node = list(sorted(node_set))
node_dic = { v : i for i, v in enumerate(node) }

x_list = [ (i[0], node_dic[i[1]], node_dic[i[2]] ) for i in x_node ]
y_list = [ (i[0], node_dic[i[1]], node_dic[i[2]] ) for i in y_node ]

connect_list = [ set([]) for i in range(n) ]
for i in x_list + y_list:
    c, a, b = i
    connect_list[a].add((c,b))
    connect_list[b].add((c,a))

def prim(in_connect_list,p,m):
    total_cost = 0
    connected_node = [ 0 for i in range(m) ]
    connected_node[p] = 1
    search_list = [p]
    search_heap = []
    while search_list != []:
        new_search_list = []
        for i in search_list:
            for c, k in connect_list[i]:
                if connected_node[k] == 0:
                    heapq.heappush(search_heap,(c,k))
          
        while search_heap != []:
            c, k = heapq.heappop(search_heap)
            if connected_node[k] == 0:
                new_search_list = [k]
                connected_node[k] = 1
                total_cost += c
                break
        search_list = new_search_list
    return total_cost

print(prim(connect_list,0,n))

Submission status: Accepted

Solution code:
#クラスカル法(最小全域木)　計算量O(|E|log|V|)
#V:頂点の集合 E:辺の集合

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

graph=Kruskal_UnionFind(n)

XY=sorted(XY,key=lambda x: x[1])
# [[1, 4, 9], [5, 7, 6], [0, 8, 3], [2, 12, 19], [4, 13, 5], [3, 18, 1]]
X_costs=[[XY[i-1][0],XY[i][0],abs(XY[i-1][1]-XY[i][1])] for i in range(1,n)]
#[[1, 5, 3], [5, 0, 1], [0, 2, 4], [2, 4, 1], [4, 3, 5]]
XY=sorted(XY,key=lambda x: x[2])
Y_costs=[[XY[i-1][0],XY[i][0],abs(XY[i-1][2]-XY[i][2])] for i in range(1,n)]

for i in range(n-1):
    x0,x1,d=X_costs[i]
    graph.add(x0,x1,d)
    y0,y1,d=Y_costs[i]
    graph.add(y0,y1,d)
print(graph.Kruskal())

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def init(n):
  for i in range(N):
    par[i]=i
    rnk[i]=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 x==y:
    return
  if (rnk[x]<rnk[y]):
    par[x]=y
  else:
    par[y]=x
    if(rnk[x]==rnk[y]):
      rnk[x]+=1
def same(x,y):
    return find(x)==find(y)

N = I()
xlist = []
ylist = []

par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
init(N)

for i in range(N):
  x, y = IL()
  xlist.append([x, i])
  ylist.append([y, i])
xlist.sort(key=itemgetter(0))
ylist.sort(key=itemgetter(0))

node = []
for i in range(N-1):
  x, xID = xlist[i]
  nextx, nextxID = xlist[i + 1]
  y, yID = ylist[i]
  nexty, nextyID = ylist[i + 1]
  
  node.append([nextx - x, xID, nextxID])
  node.append([nexty - y, yID, nextyID])
node.sort(key=itemgetter(0), reverse=True)

ans = 0
while node:
  val, i, j = node.pop()
  if same(i, j):
    continue
  else:
    unite(i, j)
    ans += val
print(ans)

Submission status: Accepted

Solution code:
def union(parent,size,a,b):
    x=find(parent,a)
    y=find(parent,b)
    if x!=y:
        if size[x]<size[y]:
            parent[x]=y 
            size[y]=size[x]+size[y]
        else:
            parent[y]=x 
            size[x]=size[x]+size[y]
    return parent,size 
def find(parent, a):
    while a != parent[a]:
            parent[a]=parent[parent[a]]
            a=parent[a]
    return a
n=int(input())
l=[]
for i in range(n):
    a,b=map(int,input().split())
    l.append([a,b,i])
l.sort(key=lambda x:x[0])
edges=[]
for i in range(1,n):
    edges.append([l[i][2],l[i-1][2],min(abs(l[i][0]-l[i-1][0]),abs(l[i][1]-l[i-1][1]))])
l.sort(key=lambda x:x[1])
for i in range(1,n):
    edges.append([l[i][2],l[i-1][2],min(abs(l[i][0]-l[i-1][0]),abs(l[i][1]-l[i-1][1]))])


parent=[i for i in range(n)]
size=[1]*n

edges.sort(key=lambda x:x[2])
cnt=0 
sm=0
for i in range(len(edges)):
    a=edges[i][0]
    b=edges[i][1]
    if find(parent,a)==find(parent,b):
        pass 
    else:
        parent,size=union(parent,size,a,b)
        sm+=edges[i][2]
        cnt+=1 
        if cnt==n-1:
            break 
print(sm)
parent=[i for i in range(n)]
size=[1]*n

Submission status: Accepted

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

N = int(input())
cityx = [[0,i]for i in range(N)]
cityy = [[0,i]for i in range(N)]
for i in range(N):
    x,y = map(int,input().split())
    cityx[i][0] = x
    cityy[i][0] = y

cityx.sort()
cityy.sort()
side = []
for i in range(N-1):
    side.append([cityx[i+1][0]-cityx[i][0], cityx[i+1][1], cityx[i][1]])
    side.append([cityy[i+1][0]-cityy[i][0], cityy[i+1][1], cityy[i][1]])
side.sort()
ans = 0
per = [i for i in range(N)]
rank = [0]*N
def find(x):
    if per[x] == x:
        return x
    else:
        per[x] = find(per[x])
        return per[x]

ans = 0

for cost,x,y in side:
    x = find(x)
    y = find(y)
    if x != y:
        ans += cost
        if rank[x] < rank[y]:
            per[x] = y
        else:
            per[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)
        # あるノードを根とする集合に属するノード数
        self.size = [1] * (n+1)
        # あるノードを根とする集合が木かどうか
        self.tree = [True] * (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:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            # 木の高さが同じなら片方を1増やす
            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 is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

    def len(self):
        """ 集合の数 """
        res = set()
        for i in range(self.n+1):
            res.add(self.find(i))
        # グループ0の分を引いて返却
        return len(res) - 1

N = INT()
XY = []
for i in range(N):
    x, y = MAP()
    XY.append((i, x, y))

edges = []
XY.sort(key=itemgetter(1))
for i in range(N-1):
    i1, x1, _ = XY[i]
    i2, x2, _ = XY[i+1]
    cost = x2 - x1
    edges.append((i1, i2, cost))
XY.sort(key=itemgetter(2))
for i in range(N-1):
    i1, _, y1 = XY[i]
    i2, _, y2 = XY[i+1]
    cost = y2 - y1
    edges.append((i1, i2, cost))

uf = UnionFind(N)
ans = 0
edges.sort(key=itemgetter(2))
for a, b, cost in edges:
    if not uf.same(a, b):
        uf.union(a, b)
        ans += cost
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
N = int(input())
cities = []

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


edge = []
for k in (itemgetter(1), itemgetter(2)):
    cities.sort(key=k)
    for j in range(N-1):
        d = min(abs(cities[j+1][1]-cities[j][1]),
                abs(cities[j+1][2]-cities[j][2]))
        edge.append((cities[j][0], cities[j+1][0], d))
edge.sort(key=itemgetter(2))


class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断

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

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


uf = UnionFind(N)

ans = 0
for e in edge:
    if not uf.isSameGroup(e[0], e[1]):
        ans += e[2]
        uf.Unite(e[0], e[1])
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, x), find(A, y)
    else:
        bx, by = find(A, y), find(A, x)
    A[by] = bx

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

V = [i for i in range(N)]
answer = 0
while H:
    w, s, t = heappop(H)
    if find(V, s) != find(V, t):
        union(V, s, t)
        answer += w
print(answer)

Submission status: Accepted

Solution code:
# D - Built?
from heapq import *

# Aでxの根を求める
def find(A, x):
    p = A[x]
    if p == x:
        return x
    a = find(A, p)
    A[x] = a
    return a

# Aでxとyの属する集合の併合
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)
    # 根をbx(値の小さい方)に統一 
    A[by] = bx

N = int(input())
X = [(0,0)] * N
Y = [(0,0)] * N

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

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]
    # ヒープ構造を用いて常にHの先頭に最小値を持ってくる
    # X座標とY座標でそれぞれHに追加
    heappush(H, (x2 - x1, j1, j2))
    heappush(H, (y2 - y1, k1, k2))

answer = 0
V = [i for i in range(N)]

while H:
    w, s, t = heappop(H)
    # sとtの集合が異なっていた時、道を作る
    if find(V, s) != find(V, t):
        union(V, s, t)
        answer += w

print(answer)

Submission status: Accepted

Solution code:
from heapq import *

# Aの中でxの根を求める
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a

# Aのリストでxとyの属する集合の併合
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)
    # 根を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]
    # ヒープ構造を用いて常にHの最初に最小値を持ってくる
    # X座標とY座標でそれぞれHに追加
    heappush(H, (x2 - x1, j1, j2))
    heappush(H, (y2 - y1, k1, k2))

answer = 0
V = [i for i in range(N)]

while H:
    w, s, t = heappop(H)
    # sとtの集合が異なっていた時、道を作る
    if find(V, s) != find(V, t):
        union(V, s, t)
        answer += w

print(answer)

Submission status: Accepted

Solution code:
from heapq import *

# Aの中でxの根を求める
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a

# Aのリストでxとyの属する集合の併合
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)
    # 根をbxに統一
    A[bx] = 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]
    # ヒープ構造を用いて常にHの最初に最小値を持ってくる
    # X座標とY座標でそれぞれHに追加
    heappush(H, (x2 - x1, j1, j2))
    heappush(H, (y2 - y1, k1, k2))

answer = 0
V = [i for i in range(N)]

while H:
    w, s, t = heappop(H)
    # sとtの集合が異なっていた時、道を作る
    if find(V, s) != find(V, t):
        union(V, s, t)
        answer += w

print(answer)

Submission status: Accepted

Solution code:
from heapq import *

# Aの中でxの根を求める
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a

# Aのリストでxとyの属する集合の併合
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))

answer = 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)
        answer += w

print(answer)

Submission status: Accepted

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

XY.sort(key=lambda x:(x[0],x[1]))
edges=[]
for i in range(1,n):
  a,b,c,d=XY[i-1][0],XY[i-1][1],XY[i][0],XY[i][1]
  edges.append((abs(a-c),XY[i-1][2],XY[i][2]))
XY.sort(key=lambda x:(x[1],x[0]))
for i in range(1,n):
  a,b,c,d=XY[i-1][0],XY[i-1][1],XY[i][0],XY[i][1]
  edges.append((abs(b-d),XY[i-1][2],XY[i][2]))
  
group=[i for i in range(n)]
def find(x):
  while group[x]!=x:
    x=group[x]
  return x
def union(x,y):
  if find(x)!=find(y):
    group[find(y)]=group[find(x)]=min(find(y),find(x))
    
edges.sort()
ans=0
for c,x,y in edges:
  if find(x)!=find(y):
    union(x,y)
    ans+=c
print(ans)

Submission status: Accepted

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

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

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

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

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
 
sys.setrecursionlimit(2000000000)
 
n = int(input())
nodes = []
done = [0 for _ in range(n)]
par = {}
for _ in range(n):
    x, y = map(int,input().split())
    nodes.append((x,y))
    par[(x,y)]=(x,y)
nodesx = sorted(nodes)
nodesy = sorted(nodes,key=lambda z:z[1])
s = []
m = len(set(nodes))
for i in range(n-1):
    xcost =nodesx[i+1][0]-nodesx[i][0]
    ycost =nodesy[i+1][1]-nodesy[i][1]
    s.append((xcost,(nodesx[i+1],nodesx[i])))
    s.append((ycost,(nodesy[i+1],nodesy[i])))
s.sort()
s = deque(s)
def root(node,par):
    if node == par[node]:
        return node
    else:
        par[node] =root(par[node],par)
        return par[node]
def unite(node1,node2,par):
    par[root(node1,par)] = root(node2,par)
ans = 0
count =0
while count < m-1 :
    cost,(node1,node2) = s.popleft()
    root1 =root(node1,par)
    root2 =root(node2,par)
    if root1 != root2:
        unite(node1,node2,par)
        ans +=cost
        count += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

n = INT()
G = [[]for i in range(n)]   
position = [[]for i in range(n)]
for i in range(n):
    a, b= MAP()
    position[i] = (i, a, b)
position_x = sorted(position, key = lambda x:x[1])
position_y = sorted(position, key = lambda x:x[2])

for i in range(1,n):
    G[position_x[i][0]].append((position_x[i][1]-position_x[i-1][1], position_x[i-1][0]))
    G[position_x[i-1][0]].append((position_x[i][1]-position_x[i-1][1], position_x[i][0]))
    G[position_y[i][0]].append((position_y[i][2]-position_y[i-1][2], position_y[i-1][0]))
    G[position_y[i-1][0]].append((position_y[i][2]-position_y[i-1][2], position_y[i][0]))

def prim(G):
    res = 0
    used = [False]*n
    que = []
    heapq.heapify(que)
    used[0] = True
    for Gs in G[0]:
        heapq.heappush(que,Gs)
    while(len(que) > 0):
        cost, vertex = heapq.heappop(que)
        if used[vertex]:continue
        res += cost
        used[vertex] = True
        for Gs in G[vertex]:
            if used[Gs[1]]:continue
            heapq.heappush(que,Gs)
    return res

print(prim(G))

Submission status: Accepted

Solution code:
from operator import itemgetter
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

import sys
input=sys.stdin.readline
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
edge=[[] for i in range(n)]
l.sort()
for i in range(n):
  l[i]=[l[i][0],l[i][1],i]
for i in range(n-1):
  edge[i].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i+1))
  edge[i+1].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i))
l=sorted(l,key=itemgetter(1))
for i in range(n-1):
  edge[l[i][2]].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i+1][2]))
  edge[l[i+1][2]].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i][2]))
print(prim_heap())