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

ixy.sort(key=lambda x:x[1])
for j in range(N-1):
  costs[ixy[j][0]] += [(ixy[j+1][0],abs(ixy[j][1]-ixy[j+1][1]))]
  costs[ixy[j+1][0]] += [(ixy[j][0],abs(ixy[j][1]-ixy[j+1][1]))]
ixy.sort(key=lambda y:y[2])
for j in range(N-1):
  costs[ixy[j][0]] += [(ixy[j+1][0],abs(ixy[j][2]-ixy[j+1][2]))]
  costs[ixy[j+1][0]] += [(ixy[j][0],abs(ixy[j][2]-ixy[j+1][2]))]

import heapq
pq = []
heapq.heappush(pq, (0,0))

visited = [0]*N
ans = 0
while pq:
  cost, v = heapq.heappop(pq)

  if visited[v]: continue
  
  ans += cost
  visited[v]=1
  
  for u,c in costs[v]:
    if not visited[u]:
      heapq.heappush(pq, (c,u))

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq
import sys
sys.setrecursionlimit(10**6)
N = input()
a = []
for i in range(N):
	x,y=map(int,raw_input().split())
	a.append((i,x,y))

#a => point,x,y
a1=sorted(a, key=lambda x: x[1])
a2=sorted(a, key=lambda x: x[2])


#Union Find
#初めは各頂点が根
par=[ i for i in range(N) ]
#木の根を求める
def root(x):
	if par[x]==x:
		return x
	else:
		r=root(par[x])
		#経路圧縮
		par[x]=r
		return r
#xとyが同じ集合に属するか
def same(x,y):
	return root(x)==root(y)

#xとyが同じ根に所属していた場合、連結
def unite(x,y):
	x=root(x)
	y=root(y)
	if x==y:
		return
	else:
		par[x]=y


b=[]
for i in range(N-1):
	# len_x,x,y
	heapq.heappush( b, ( abs(a1[i+1][1]-a1[i][1]),a1[i][0],a1[i+1][0],  ))

for i in range(N-1):
	# len_y,x,y
	heapq.heappush( b, ( abs(a2[i+1][2]-a2[i][2]),a2[i][0],a2[i+1][0],  ))

#print "# b"
#print b


ans=0
cnt=0
for i in range(len(b)):
	if cnt==N-1:
		break
	val=heapq.heappop(b)
	#２点が同じ根でない場合は、木を結合する
	if not same(val[1],val[2]):
		unite(val[1],val[2])
		ans+=val[0]
		cnt+=1

print ans

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())

P = [n for n in range(N)]
points = []

def root(a):
  if P[a] == a:
    return a
  P[a] = root(P[a])
  return P[a]

def is_same_set(a, b):
  return root(a) == root(b)

def unite(a, b):
  P[root(a)] = root(b)


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

xs = sorted([(x, i) for i, x, y in points], key=lambda p: p[0])
xedges = [(xs[n][1], xs[n+1][1], xs[n+1][0]-xs[n][0] ) for n in range(N-1)]
ys = sorted([(y, i) for i, x, y in points], key=lambda p:p[0])
yedges = [(ys[n][1], ys[n+1][1], ys[n+1][0]-ys[n][0]) for n in range(N-1)]

edges = xedges + yedges
edges.sort(key=lambda x: x[2])
res = 0
for edge in edges:
  i, j, cost = edge
  if not is_same_set(i, j):
    unite(i, j)
    res += cost

print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://abc065.contest.atcoder.jp/tasks/arc076_b
TLE
"""
import sys
from sys import stdin
input = stdin.readline
from collections import namedtuple


class DisjointSet(object):
    def __init__(self, size):
        self.rank = []
        self.p = []
        for i in range(size):
            self.makeSet(i)

    def makeSet(self, x):
        self.p.insert(x, x)
        self.rank.insert(x, 0)

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]


def kruskal(V, E, es):
    es.sort(key=lambda x: x.c)
    uf = DisjointSet(V)
    res = 0

    for i in range(E):
        e = es[i]
        if not uf.same(e.u, e.v):
            uf.unite(e.u, e.v)
            res += e.c
    return res


edge = namedtuple('edge', ['u', 'v', 'c'])
def main(args):
    N = int(input())
    cities = []
    for i in range(1, N+1):
        x, y = map(int, input().split())
        cities.append([x, y, i])

    es = []
    cities.sort(key=lambda x: x[0])
    prev_x, _, prev_i = cities[0]
    for x, y, i in cities[1:]:
        es.append(edge(prev_i, i, x - prev_x))
#        es.append(edge(i, prev_i, x - prev_x))
        prev_x = x
        prev_i = i

    cities.sort(key=lambda x: x[1])
    _, prev_y, prev_i = cities[0]
    for x, y, i in cities[1:]:
        es.append(edge(prev_i, i, y - prev_y))
#        es.append(edge(i, prev_i, y - prev_y))
        prev_y = y
        prev_i = i

    result = kruskal(N+1, len(es), es)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
N = int(input())

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

# x, y座標の値でソートして、隣接する街の間の道を、隣接リストadjに追加する
adj = [[] for i in range(N)]
for xy in [1, 2]:
    towns.sort(key=lambda t: t[xy])
    for i in range(N - 1):
        t1 = towns[i][0]
        t2 = towns[i + 1][0]
        cost = towns[i + 1][xy] - towns[i][xy]
        adj[t1].append((t2, cost))
        adj[t2].append((t1, cost))

# 最小全域木を求める（プリム法）
import heapq
pq = []
heapq.heappush(pq, (0, 0))

done = set()
ans = 0
while pq:
    cost, v_now = heapq.heappop(pq)

    if v_now in done:
        continue

    ans += cost
    done.add(v_now)

    if len(done) == N:
        break

    for v, c in adj[v_now]:
        if v not in done:
            heapq.heappush(pq, (c, v))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

# x, y座標の値でソートして、隣接する街の間の道を、edgesに追加する
edges = []
for xy in [1, 2]:
    towns.sort(key=lambda t: t[xy])
    for i in range(N - 1):
        edges.append((towns[i + 1][xy] - towns[i][xy], towns[i][0], towns[i + 1][0]))

# costでソートする
edges.sort()

# 素集合データ構造
parent = [i for i in range(N)]
rank = [0 for i in range(N)]

def find(v):
    if parent[v] != v:
        parent[v] = find(parent[v])
    return parent[v]

def union(a, b):
    rootA = find(a)
    rootB = find(b)

    if rootA == rootB:
        return
    if rank[rootA] < rank[rootB]:
        parent[rootA] = rootB
    else:
        parent[rootB] = rootA
        if rank[rootA] == rank[rootB]:
            rank[rootA] += 1

# 最小全域木を求める（クラスカル法）
numTree = N
ans = 0
for cost, v1, v2 in edges:

    if find(v1) != find(v2):
        union(v1, v2)
        ans += cost
        numTree -= 1

    if numTree == 1:
        break

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
uni = list(range(n))
cityx = [None] * n
cityy = [None] * n
for i in range(n):
    x, y = map(int, input().split())
    cityx[i] = (x, i)
    cityy[i] = (y, i)

cityx.sort()
cityy.sort()
dcx, dcy = [], []
for i in range(n - 1):
    dcx.append((cityx[i+1][0] - cityx[i][0], (cityx[i][1], cityx[i+1][1])))
    dcy.append((cityy[i+1][0] - cityy[i][0], (cityy[i][1], cityy[i+1][1])))

dqx = deque(sorted(dcx))
dqy = deque(sorted(dcy))

def root(a):
    if(a == uni[a]):
        return a
    uni[a] = root(uni[a])
    return uni[a]

def connect(a, b):
    a = root(a)
    b = root(b)
    uni[b] = a

ans = 0
while dqx or dqy:
    if(dqx and (not dqy or dqx[0] < dqy[0])):
        d, (i, j) = dqx.popleft()
    else:
        d, (i, j) = dqy.popleft()
    if(root(i) != root(j)):
        ans += d
        connect(i, j)

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
from queue import deque

N = int(input())

xin = []
yin = []

for _ in range(N):
    x, y = map(int, input().split())
    xin.append(x)
    yin.append(y)
    
xin = sorted(list(enumerate(xin)), key=itemgetter(1))
yin = sorted(list(enumerate(yin)), key=itemgetter(1))

xd = []
yd = []

for i in range(N-1):
    xd.append((xin[i+1][1] - xin[i][1], (xin[i][0], xin[i+1][0])))
    yd.append((yin[i+1][1] - yin[i][1], (yin[i][0], yin[i+1][0])))
    
xdq = deque(sorted(xd))
ydq = deque(sorted(yd))

par = list(range(N))

def find(x):
    if x == par[x]:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
    
def union(x, y):
    px, py = find(x), find(y)
    if px != py:
        par[py] = px
    
ans = 0

while xdq or ydq:
    if xdq and (not ydq or xdq[0] < ydq[0]):
        d, (i, j) = xdq.popleft()
    else:
        d, (i, j) = ydq.popleft()
        
    if find(i) != find(j):
        ans += d
        union(i, j)
        
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
from collections import deque

N = int(input())

xs, ys = [], []
for _ in range(N):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)
    
xis = sorted(list(enumerate(xs)), key = itemgetter(1))
yis = sorted(list(enumerate(ys)), key = itemgetter(1))

xds, yds = [], []
for i in range(N-1):
    xds.append((xis[i+1][1] - xis[i][1], (xis[i][0], xis[i+1][0])))
    yds.append((yis[i+1][1] - yis[i][1], (yis[i][0], yis[i+1][0])))

xdq, ydq = deque(sorted(xds)), deque(sorted(yds))

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

def union(x,y):
    rx, ry = find(x), find(y)
    par[ry] = rx

ans = 0
while xdq or ydq:
    if xdq and (not ydq or xdq[0] < ydq[0]):
        d, (i,j) = xdq.popleft()
    else:
        d, (i,j) = ydq.popleft()
    if find(i) != find(j): #Kruskal法
        ans += d
        union(i,j)

print(ans)

Submission status: Accepted

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

from operator import itemgetter
xis = sorted(list(enumerate(xs)), key=itemgetter(1))
yis = sorted(list(enumerate(ys)), key=itemgetter(1))

xds, yds = [], []
for i in range(N - 1):
    xds.append((xis[i + 1][1] - xis[i][1], (xis[i][0], xis[i + 1][0])))
    yds.append((yis[i + 1][1] - yis[i][1], (yis[i][0], yis[i + 1][0])))

from collections import deque
xdq, ydq = deque(sorted(xds)), deque(sorted(yds))

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

def union(x, y):
    rx, ry = find(x), find(y)
    par[ry] = rx

ans = 0
while xdq or ydq:
    if xdq and (not ydq or xdq[0] < ydq[0]):
        d, (i, j) = xdq.popleft()
    else:
        d, (i, j) = ydq.popleft()
    if find(i) != find(j):
        ans += d
        union(i, j)

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]
 
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]
 
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False
 
def cal(d,xl):
    N=len(xl)
    for i in range(N-1):
        r1=abs(xl[i+1][0]-xl[i][0])
        try:
            l=d[r1]
            l.append([xl[i+1][1],xl[i][1]])
            d[r1]=l
        except:
            d[r1]=[[xl[i+1][1],xl[i][1]]]
    return d
N=int(input())
x=[[0,0] for _ in range(N)]
y=[[0,0] for _ in range(N)]
for i in range(N):
    x[i][0],y[i][0]=list(map(int,input().split()))
    x[i][1],y[i][1]=i,i
x=sorted(x,key=lambda l: l[0])
y=sorted(y,key=lambda l: l[0])
a=cal(cal({},x),y)
p=UnionFind(N)
c=0
cost=0
edgecount=0
while True:
    if(edgecount==N-1):
        print(cost)
        break
    try:
        l=a[c]
        for item in l:
            if(p.union(item[0],item[1])):
                cost+=c
                edgecount+=1
            
        c+=1
    except:
        c+=1
        continue

Submission status: Accepted

Solution code:
import sys

import numpy as np


class Graph:
    def __init__(self, N):
        self.townarrow = [i for i in range(N)]

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

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

    def link(self, x, y):
        self.townarrow[y] = x


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

useful_road = []

l = sorted(range(N), key=lambda j: x[j])
for i in range(len(l) - 1):
    cost = min(abs(x[l[i]] - x[l[i + 1]]), abs(y[l[i]] - y[l[i + 1]]))
    useful_road.append((cost, l[i], l[i + 1]))

l = sorted(range(N), key=lambda j: y[j])
for i in range(len(l) - 1):
    cost = min(abs(x[l[i]] - x[l[i + 1]]), abs(y[l[i]] - y[l[i + 1]]))
    useful_road.append((cost, l[i], l[i + 1]))


m = 0
cost = 0
towngroup = Graph(N)
for c, i, j in sorted(useful_road):
    if towngroup.find(i) == towngroup.find(j):
        continue
    cost += c
    m += 1

    towngroup.union(i, j)

    if m == N - 1:
        print(cost)
        sys.exit()

Submission status: Accepted

Solution code:
class UnionFind3:
    def __init__(self, size):
        self.table = [-1 for _ in xrange(size)]
 
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]
 
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False
 
uf=UnionFind3(100001)
 
n = input()
cities = [map(int,raw_input().split(" "))+[i] for i in range(n)]
 
cities_x = sorted(cities, key=lambda a:a[0])
cities_y = sorted(cities, key=lambda a:a[1])
 
road = [[cities_x[i+1][0]-cities_x[i][0],cities_x[i][2],cities_x[i+1][2]] for i in range(n-1)]
road +=[[cities_y[i+1][1]-cities_y[i][1],cities_y[i][2],cities_y[i+1][2]] for i in range(n-1)]
 
sum = 0
for (cost,i,j) in sorted(road):
    if(uf.find(i)!=uf.find(j)):
        uf.union(i,j)
        sum += cost
 
print sum

Submission status: Accepted

Solution code:
import sys

# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


p = []
rank = []


def make_set(x):
    p[x] = x
    rank[x] = 0


def _union(x, y):
    link(find_set(x), find_set(y))


def link(x, y):
    if rank[x] > rank[y]:
        p[y] = x
    else:
        p[x] = y
        if rank[x] == rank[y]:
            rank[x] += 1


def find_set(x):
    if x != p[x]:
        p[x] = find_set(p[x])
    return p[x]


def solve():
    n = read_int()
    a = [read_int_list() for i in range(n)]
    global p, rank
    p = [0] * n
    rank = [0] * n

    for x in range(n):
        make_set(x)

    def get_cost(i, j):
        return min(abs(a[i][0] - a[j][0]), abs(a[i][1] - a[j][1]))

    roads = []
    for j in range(2):
        l = sorted(range(n), key=lambda i: a[i][j])
        for i in range(n - 1):
            cost = get_cost(l[i], l[i + 1])
            road = (cost, l[i], l[i + 1])
            roads.append(road)
    roads.sort()

    res = 0
    m = 0
    for road in roads:
        c, u, v = road
        if find_set(u) != find_set(v):
            res += c
            m += 1
            _union(u, v)
        if m == n - 1:
            break
    return res


def main():
    res = solve()
    print(res)


main()

Submission status: Accepted

Solution code:
import operator
import sys

# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


p = []
rank = []


def make_set(x):
    p[x] = x
    rank[x] = 0


def _union(x, y):
    link(find_set(x), find_set(y))


def link(x, y):
    if rank[x] > rank[y]:
        p[y] = x
    else:
        p[x] = y
        if rank[x] == rank[y]:
            rank[x] += 1


def find_set(x):
    if x != p[x]:
        p[x] = find_set(p[x])
    return p[x]


def solve():
    n = read_int()
    a = [read_int_list() for i in range(n)]
    global p, rank
    p = [0] * n
    rank = [0] * n

    for x in range(n):
        make_set(x)

    def get_cost(i, j):
        return min(abs(a[i][0] - a[j][0]), abs(a[i][1] - a[j][1]))

    roads = []
    for j in range(2):
        l = sorted(range(n), key=lambda i: a[i][j])
        for i in range(n - 1):
            cost = get_cost(l[i], l[i + 1])
            road = (cost, l[i], l[i + 1])
            roads.append(road)
    roads.sort()

    res = 0
    for road in roads:
        c, u, v = road
        if find_set(u) != find_set(v):
            res += c
            _union(u, v)
    return res


def main():
    res = solve()
    print(res)


main()

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(int(2e9))

def distance(P, p1, p2):
    return min(abs(P[p1][1]-P[p2][1]), abs(P[p1][2]-P[p2][2]))
def root(CI, p):
    if CI[p] == p:
        return p
    else:
        CI[p] = root(CI, CI[p])
        return CI[p] 

N = int(input())
P = [[j]+[int(i) for i in input().split(' ')] for j in range(N)]
sortX = sorted(P,key=lambda x:x[1])
sortY = sorted(P,key=lambda x:x[2])
EX = [[sortX[i][0], sortX[i+1][0], distance(P,sortX[i][0],sortX[i+1][0])] for i in range(N-1)]
EY = [[sortY[i][0], sortY[i+1][0], distance(P,sortY[i][0],sortY[i+1][0])] for i in range(N-1)]
E = EX + EY
E = sorted(E, key=lambda x:x[2])
CI = [i for i in range(N)]
disSum = 0
for e in E:
    s,l = min(e[0],e[1]),max(e[0],e[1])
#     if CI[s] != CI[l]:
#         CI = list(map(lambda x:CI[s] if x == CI[l] else x, CI))
#         disSum += e[2]
    if root(CI, s) != root(CI, l):
        CI[root(CI, l)] = root(CI, s)
        disSum += e[2]
print(disSum)

Submission status: Accepted

Solution code:
from collections import defaultdict
import operator

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

es = defaultdict(lambda: float('inf'))
for i in range(N-1):
    xd = xs[i+1][0] - xs[i][0]
    i1 = min(xs[i+1][1], xs[i][1])
    i2 = max(xs[i+1][1], xs[i][1])
    es[(i1,i2)] = min(es[(i1,i2)], xd)
    yd = ys[i+1][0] - ys[i][0]
    i3 = min(ys[i+1][1], ys[i][1])
    i4 = max(ys[i+1][1], ys[i][1])
    es[(i3,i4)] = min(es[(i3,i4)], yd)

parent = [i for i in range(N)]
def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]
def is_same(a,b):
    return root(a) == root(b)
def unite(a,b):
    ra = root(a)
    rb = root(b)
    if ra == rb: return
    parent[ra] = rb;

value = 0
for k,v in sorted(es.items(), key=operator.itemgetter(1)):
    a,b = k
    if is_same(a,b): continue
    unite(a,b)
    value += v
print value

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(int(2e9))
class obj:
    def __init__(self, N):
        self.fa = [i for i in range(N)]
    def find(self, x):
        if x == self.fa[x]:
            return x
        else:
            self.fa[x] = self.find(self.fa[x])
            return self.fa[x]

N = int(input())
node = [{"x":0, "y":0, "id":i} for i in range(N)]
edge = [{"u":0, "v":0, "d":0} for i in range(2*(N-1))]
ob = obj(N)
for i in range(N):
    node[i]["x"], node[i]["y"] = map(int, input().split())
    node[i]["id"] = i

xnode = sorted(node, key=lambda x:x["x"])
for i in range(N-1):
    edge[i]["u"] = xnode[i]["id"]
    edge[i]["v"] = xnode[i+1]["id"]
    edge[i]["d"] = xnode[i+1]["x"] - xnode[i]["x"]
ynode = sorted(node, key=lambda x:x["y"])
for i in range(N-1):
    edge[i+N-1]["u"] = ynode[i]["id"]
    edge[i+N-1]["v"] = ynode[i+1]["id"]
    edge[i+N-1]["d"] = ynode[i+1]["y"] - ynode[i]["y"]
dedge = sorted(edge, key=lambda x:x["d"])
ans = 0
for i in range(2*(N-1)):
    if ob.find(dedge[i]["u"]) != ob.find(dedge[i]["v"]):
        ans += dedge[i]["d"]
        ob.fa[ob.fa[dedge[i]["u"]]] = ob.fa[dedge[i]["v"]]
print(ans)

Submission status: Accepted

Solution code:
class UnionFind3:
    def __init__(self, size):
        self.table = [-1 for _ in xrange(size)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

uf=UnionFind3(100001)

n = input()
cities = [map(int,raw_input().split(" "))+[i] for i in range(n)]

cities_x = sorted(cities, key=lambda a:a[0])
cities_y = sorted(cities, key=lambda a:a[1])

road = [[cities_x[i+1][0]-cities_x[i][0],cities_x[i][2],cities_x[i+1][2]] for i in range(n-1)]
road +=[[cities_y[i+1][1]-cities_y[i][1],cities_y[i][2],cities_y[i+1][2]] for i in range(n-1)]

sum = 0
for (cost,i,j) in sorted(road):
    if(uf.find(i)!=uf.find(j)):
        uf.union(i,j)
        sum += cost

print sum

Submission status: Runtime Error

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

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

L=np.zeros((N,N))
for i in range(N):
	for j in range(N):
		p=min(abs(X[i]-X[j]), abs(Y[i]-Y[j]))
		L[i][j]=p
		L[j][i]=p

csr = csr_matrix(L)
mst = minimum_spanning_tree(csr, True).astype(int)

print(mst.sum())

Submission status: Runtime Error

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

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

#L=np.zeros((N,N))
L=list([0]*N for _ in range(N))
for i in range(N):
	for j in range(N):
		p=min(abs(X[i]-X[j]), abs(Y[i]-Y[j]))
		L[i][j]=p
		L[j][i]=p

csr = csr_matrix(L)
mst = minimum_spanning_tree(csr, True).astype(int)

print(mst.sum())

Submission status: Runtime Error

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

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

#L=np.zeros((N,N))
L=list([0]*N for _ in range(N))
for i in range(N):
	for j in range(N):
		p=min(abs(X[i]-X[j]), abs(Y[i]-Y[j]))
		L[i][j]=p
		L[j][i]=p

csr = csr_matrix(L)
mst = minimum_spanning_tree(csr, True).astype(int)

print(mst.sum())

Submission status: Runtime Error

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

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

L=np.zeros((N,N))
for i in range(N):
	for j in range(N):
		p=min(abs(X[i]-X[j]), abs(Y[i]-Y[j]))
		L[i][j]=p
		L[j][i]=p

csr = csr_matrix(L)
mst = minimum_spanning_tree(csr, True)

print(int(mst.sum()))

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.components = n  # 連結成分の数

    def root(self, x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.p[x] = y
            self.components -= 1
    
    def same(self, x,y):
        return (self.root(x) == self.root(y))

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

edges = []
for i in range(N-1):
    edges.append([X[i+1][0]-X[i][0], X[i][1], X[i+1][1]])
    edges.append([Y[i+1][0]-Y[i][0], Y[i][1], Y[i+1][1]])
edges.sort()

UF = UnionFind(N)
ans = 0
for cost, s, t in edges:
    if UF.same(s,t): continue

    UF.unite(s,t)
    ans += cost
print(ans)

Submission status: Runtime Error

Solution code:
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
        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
            self.rank[p_y] = max(self.rank[p_y], self.rank[p_x]+1)
        else:
            self.par[p_y] = p_x
            self.rank[p_x] = max(self.rank[p_x], self.rank[p_y]+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


print(ans)

Submission status: Runtime Error

Solution code:
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
        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
            self.rank[p_y] = max(self.rank[p_y], self.rank[p_x]+1)
        else:
            self.par[p_y] = p_x
            self.rank[p_x] = max(self.rank[p_x], self.rank[p_y]+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


print(ans)

Submission status: Runtime Error

Solution code:
import heapq
n = int(raw_input())
points = [map(int, raw_input().split()) for _ in range(n)]
heap  =[]


parent = range(n)
size = [1] * n
cumul = 0

for i in range(len(points)):
	for j in range(i + 1, len(points)):
		a,b = points[i], points[j]
		if min(abs(a[0]-  b[0]), abs(a[1] - b[1])) == 0:
			pi,pj = get(i, parent), get(j, parent)
			if pi != pj:		
				parent[pi] = pj
				size[pj] += size[pi]
		else:			
			heapq.heappush(heap,(min(abs(a[0]-  b[0]), abs(a[1] - b[1])),i,j))


def get(u, parent):
	if u != parent[u]: parent[u] = get(parent[u], parent)
	return parent[u]
while(heap):
	cost,i,j = heapq.heappop(heap)
	pi,pj = get(i,parent), get(j, parent)
	if pi != pj:
		cumul += cost
		parent[pi] = pj
		size[pj] += size[pi]
		if size[pj] == n:
			break
print cumul

Submission status: Runtime Error

Solution code:
from heapq import heappop,heappush
n=int(input())
pair=[i for i in range(n)]
que=[]
e=[None]*n
for i in range(n):
  x,y=map(int,input().split())
  e[i]=(i,x,y)
ex=sorted(e,key=lambda x:x[1])
ey=sorted(e,key=lambda x:x[2])
for i in range(n-1):
  w=ex[i+1][1]-ex[i][1]
  heappush(que,(w,ex[i][0],ex[i+1][0]))
for i in range(n-1):
  w=ey[i+1][2]-ey[i][2]
  heappush(que,(w,ey[i][0],ey[i+1][0]))
def find(x):
  if x==pair[x]:return x
  else:
    tmp=find(pair[x])
    pair[x]=tmp
    return tmp
q=[]
ans=0
while que:
  w,s,t=heappop(que)
  root_s=find(s)
  root_t=find(t)
  if root_s!=root_t:
    pair[root_s]=root_t
    ans+=w
print(ans)