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())
a = [list(map(int, input().split())) for _ in range(n)]
a = sorted(a)
gra = []
for i in range(n):
  a[i].append(i)
for i in range(n-1):
  gra.append([a[i][2],a[i+1][2],a[i+1][0]-a[i][0]])
a = sorted(a,key= lambda x:x[1])
for i in range(n-1):
  gra.append([a[i][2],a[i+1][2],a[i+1][1]-a[i][1]])
union = [0] *  n
uc = 0
ans = 0
gra = sorted(gra, key = lambda x: x[2])
class UnionFind():
    #負の値はルートで集合の個数
    #正の値は次の要素を返す
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]

    #集合の代表を求める
    def find(self,x):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

    #併合
    def union(self,x,y):
        s1 = self.find(x)#根のindex,table[s1]がグラフの高さ
        s2 = self.find(y)
        if s1 != s2:#根が異なる場合
            if self.table[s1] != self.table[s2]:#グラフの高さが異なる場合
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                #グラフの長さが同じ場合,どちらを根にしても変わらない
                #その際,グラフが1長くなることを考慮する
                self.table[s1] += -1
                self.table[s2] = s1
        return
uni = UnionFind(n)
for i in range(len(gra)):
  hen = gra[i]
  if (uni.find(hen[0]) != uni.find(hen[1])):
    ans += hen[2]
    uni.union(hen[0],hen[1])
    uc += 1
  if uc == n-1:
    break
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
# from typing import List, Tuple, Dict
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


class UnionFind:
    def __init__(self, N):
        # type: (int) -> None
        self.N = N
        self.parent = list(range(N))  # type: List[int]

    def root(self, x):
        # type: (int) -> int
        path_to_root = []
        while self.parent[x] != x:
            path_to_root.append(x)
            x = self.parent[x]
        for node in path_to_root:
            self.parent[node] = x  # パス圧縮
        return x

    def same(self, x, y):
        # type: (int, int) -> bool
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        # type: (int, int) -> None
        self.parent[self.root(x)] = self.root(y)

    def __str__(self):
        # type: () -> str
        groups = {}  # type: Dict[int, List[int]]
        for x in range(self.N):
            root = self.root(x)
            if root in groups.keys():
                groups[root].append(x)
            else:
                groups[root] = [x]
        result = ""
        for root in groups.keys():
            result += str(groups[root]) + "\n"
        return result


def kruskal(num_vertices, edges):
    # type: (int, List[Tuple[int, int, int]]) -> int
    """Kruscal法: 最小全域木を求める
    edgesについて破壊的なことに注意
    """
    total_weight = 0
    edges.sort(key=lambda e: e[2])
    u = UnionFind(num_vertices)
    for e in edges:
        x = e[0]
        y = e[1]
        weight = e[2]
        if u.same(x, y):
            continue
        u.unite(x, y)
        total_weight += weight
    return total_weight


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

edges = []
sorted_x = sorted(l, key=lambda c: c[1])
sorted_y = sorted(l, key=lambda c: c[2])

for e in range(N-1):
    i0, x0, y0 = sorted_x[e]
    i1, x1, y1 = sorted_x[e+1]
    edges.append((i0, i1, x1-x0))

    i0, x0, y0 = sorted_y[e]
    i1, x1, y1 = sorted_y[e+1]
    edges.append((i0, i1, y1-y0))

print(kruskal(N, edges))

Submission status: Accepted

Solution code:
import numpy as np

def ii():
    return int(input())


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


def lvi(N):
    l = []
    for _ in range(N):
        l.append(ii())
    return l


def lv(N):
    l = []
    for _ in range(N):
        l.append(input())
    return l


def next_pair(lst):
    n = len(lst)
    for i in range(n-1):
        yield lst[i], lst[i+1]


class UnionFind(object):

    def __init__(self, n):
        # 親のnodeを表す
        self.par = [i for i in range(n)]

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            # 経路圧縮
            self.par[x] = self.root(self.par[x])
            return self.par[x]

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

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

        self.par[x] = y


class UnionFindRank(UnionFind):

    def __init__(self, n):
        UnionFind.__init__(self, n)

        self.rank = [0 for _ in range(n)]

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

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


class UnionFindRankCount(UnionFind):

    def __init__(self, n):
        UnionFind.__init__(self, n)

        self.rank = [0 for _ in range(n)]
        self.count = [1 for _ in range(n)]

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

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


def kruskal(n, edges):
    """
    :param n: int node数
    :param edges: list(tuple(int)) edge
        ex.) edges = [(0, 1, 10), (1, 0, 50), (2, 0, 30)]  (from, to, weight)
    :return: 最小全域木に含まれるエッジ（edgesの部分集合）
    """
    edges = sorted(edges, key=lambda x: x[2])
    u = UnionFindRankCount(n)

    k = []
    cnt = 0
    for e in edges:
        i, j, w = e
        if not u.same(i, j):
            u.union(i, j)
            k.append(e)
            cnt += 1

        if cnt == n-1: break

    return k



def main():
    N = ii()
    coord = []
    for n in range(N):
        x, y = lii()
        coord.append((x, y, n))

    c_sortx = sorted(coord, key=lambda x: x[0])
    c_sorty = sorted(coord, key=lambda x: x[1])

    edges = []
    for p1, p2 in next_pair(c_sortx):
        w = min(abs(p1[0] - p2[0]), abs(p1[1] - p2[1]))
        edges.append([p1[2], p2[2], w])

    for p1, p2 in next_pair(c_sorty):
        w = min(abs(p1[0] - p2[0]), abs(p1[1] - p2[1]))
        edges.append([p1[2], p2[2], w])

    min_tree = kruskal(N, edges)
    return sum(map(lambda x: x[2], min_tree))


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

uf = UnionFind(N)
es = []
pre_x = pre_i = None
for x,idxs in sorted(xd.items()):
    if len(idxs) >= 2:
        for i1,i2 in zip(idxs,idxs[1:]):
            if uf.is_same(i1,i2): continue
            uf.unite(i1,i2)
    if pre_x is not None:
        dx = x - pre_x
        es.append((dx,pre_i,idxs[0]))
    pre_x = x
    pre_i = idxs[0]
pre_y = pre_i = None
for y,idxs in sorted(yd.items()):
    if len(idxs) >= 2:
        for i1,i2 in zip(idxs,idxs[1:]):
            if uf.is_same(i1,i2): continue
            uf.unite(i1,i2)
    if pre_y is not None:
        dy = y - pre_y
        es.append((dy,pre_i,idxs[0]))
    pre_y = y
    pre_i = idxs[0]

if uf.count == N-1:
    print(0)
    exit()
ans = 0
for cost,a,b in sorted(es):
    if uf.is_same(a,b): continue
    uf.unite(a,b)
    ans += cost
    if uf.count == N-1:
        break
print(ans)

Submission status: Accepted

Solution code:
class UnionFind(object):
  def __init__(self,n):
    self.table=[-1]*n
 
  def find(self,x):
    parent=self.table[x]
    if parent<0:
      return x
    else:
      root=self.find(parent)
      self.table[x]=root
      return root
 
  def union(self,a,b):
    root1=self.find(a)
    root2=self.find(b)
    if root1 != root2:
      if self.table[root1] != self.table[root2]:
        if self.table[root1] < self.table[root2]:
          self.table[root2]=root1
        else:
          self.table[root1]=root2
      else:
        self.table[root1]+=(-1)
        self.table[root2]=root1

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

x=sorted(x,key=lambda x:x[1])
y=sorted(y,key=lambda y:y[1])

for i in range(N-1):
  a,b=x[i]
  c,d=y[i]
  e,f=x[i+1]
  g,h=y[i+1]
  M.append((f-b,a,e))
  M.append((h-d,c,g))
  
uf=UnionFind(N)
ans=0

for v,s,t in sorted(M,key=lambda x:x[0]):
  if uf.find(s)!=uf.find(t):
    uf.union(s,t)
    ans+=v

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xs = []
ys = []

for i in range(n):
    x, y = map(int, input().split())
    xs.append((x, i))
    ys.append((y, i))


xs.sort()
ys.sort()

es = []

for i in range(n-1):
    es.append((xs[i+1][0] - xs[i][0], xs[i][1], xs[i+1][1]))
    es.append((ys[i+1][0] - ys[i][0], ys[i][1], ys[i+1][1]))

es.sort()

class UF:
    def __init__(self):
        self.p = {}
    def find(self, x):
        if x not in self.p:
            self.p[x] = x
        if x == self.p[x]:
            return x
        self.p[x] = self.find(self.p[x])
        return self.p[x]
    def merge(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.p[x] = y


uf = UF()
ans = 0
try:
    for d, i0, i1 in es:
        c0 = uf.find(i0)
        c1 = uf.find(i1)
        if c0 == c1:
            continue
        ans += d
        uf.merge(i0, i1)
    print(ans)
except:
    print(0)

Submission status: Accepted

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


N = int(input())

Xs = []
Ys = []

V = [] #辺を格納

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

Xs.sort()
Ys.sort()
# print(Xs)
# print(Ys)
Xedges = []
Yedges = []
for i in range(N-1):
    Xedges.append((Xs[i+1][0]-Xs[i][0],Xs[i][1],Xs[i+1][1]))
    Yedges.append((Ys[i+1][0]-Ys[i][0],Ys[i][1],Ys[i+1][1]))
Xedges.extend(Yedges)
Xedges.sort()

# print(Xedges)
# print(Yedges)


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 subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

uf = UnionFind(N)

# クラスカルのアルゴリズムを用いる
# 閉路を作らないように値が小さい辺から順々に足していく
i = 0
while len(V) != N-1:
    v, x1, x2 = Xedges[i]
    if uf.find(x1) != uf.find(x2):
        uf.union(x1, x2)
        V.append(v)
        # print(v, x1, x2)
    i += 1
# print(V)
print(sum(V))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))

n = int(input())
X = []
Y = []
for i in range(n):
    x, y = inpl()
    X.append((x, i))
    Y.append((y, i))

X = sorted(X, key = lambda x: x[0])
Y = sorted(Y, key = lambda y: y[0])

G = [[] for _ in range(n)]
edges = []
for i in range(n-1):
    edges.append((X[i][1], X[i+1][1], abs(X[i][0] - X[i+1][0])))
    edges.append((Y[i][1], Y[i+1][1], abs(Y[i][0] - Y[i+1][0])))

edges = sorted(edges, key = lambda e: e[2])

tree = [[-1, 1] for _ in range(n)]

def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0])    
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px

res = 0

for s, t, w in edges:
    if find(s) != find(t):
        unite(s, t)
        res += w
print(res)

Submission status: Accepted

Solution code:
class UnionFind(object):

    def __init__(self, n):
        self.n = n
        self.par = list(range(n))
        self.rank = [1] * n

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.par[y] = x
        elif self.rank[x]  < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            self.rank[x] += 1


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 = sorted(X)
Y = sorted(Y)
graph = []
for i in range(N - 1):
    graph.append((X[i + 1][0] - X[i][0], X[i][1], X[i + 1][1]))
    graph.append((Y[i + 1][0] - Y[i][0], Y[i][1], Y[i + 1][1]))

graph.sort()
uf = UnionFind(N)

total_cost = 0
for cost, a, b in graph:
    if not uf.is_same(a, b):
        uf.unite(a, b)
        total_cost += cost

print(total_cost)

Submission status: Accepted

Solution code:
N = int(input())


class DisjointSet:
  def __init__(self, size):
    self.parent = list(range(size))
    self.rank = [0]*size
  
  def find(self, x):
    if self.parent[x] == x:
      return x
    else:
      self.parent[x] = self.find(self.parent[x])
      return self.parent[x]

  def union(self, x, y):
    xr = self.find(x)
    yr = self.find(y)
    if self.rank[xr] > self.rank[yr]:
      self.parent[yr] = xr
    elif self.rank[xr] < self.rank[yr]:
      self.parent[xr] = yr
    elif xr != yr:
      self.parent[yr] = xr
      self.rank[xr] += 1


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

def convert_to_dists(L):
  it = iter(L)
  it2 = iter(L)
  next(it2)

  D = []

  for a,b in zip(it, it2):
    ax, ai = a
    bx, bi = b
    d = abs(ax-bx)
    D.append((d,ai,bi))
  return D

dX = convert_to_dists(X)
dY = convert_to_dists(Y)

D = dX+dY
D.sort()

cost = 0
S = DisjointSet(N)
edge_count = 1

for d,i,j in D:
  if S.find(i) != S.find(j):
    S.union(i,j)
    cost += d
    edge_count += 1
    if edge_count >= N:
      break

print(cost)

Submission status: Accepted

Solution code:
class Edge:
    def __init__(self, u, v, cost):
        self.u = u
        self.v = v
        self.cost = cost
        # self.n = n


class Coordinate:
    def __init__(self, x, y, n):
        self.x = x
        self.y = y
        self.n = n

    def __repr__(self):
        return repr((self.x, self.y))


# union find。初期化
def init(_n):
    for i in range(0, _n):
        par[i] = i
        rank[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 rank[_x] < rank[_y]:
        par[_x] = _y
    else:
        par[_y] = _x
        if rank[_x] == rank[_y]:
            rank[_x] += 1


# 同じ集合かどうか
def same(_x, _y):
    return find(_x) == find(_y)


def comp(edge1, edge2):
    return edge1.cost < edge2.cost


def kruskal():
    sorted_edges = sorted(Edges, key=lambda edges: edges.cost)
    init(V)
    res = 0
    # for i in range(E):
    # # print("u" + str(sorted_edges[i].u) + "v" + str(sorted_edges[i].v) + "cost" + str(sorted_edges[i].cost))

    for i in range(0, E):
        tmp_edge = sorted_edges[i]
        if not same(tmp_edge.u, tmp_edge.v):
            unite(tmp_edge.u, tmp_edge.v)
            # print("tmp_edge.cost" + str(tmp_edge.cost))
            res += tmp_edge.cost

    return res


if __name__ == '__main__':
    N = int(input())
    x = []
    y = []
    Coordinates = []
    for i in range(0, N):
        tmp_x, tmp_y = list(map(int, input().split()))
        # x.append(tmp_x)
        # y.append(tmp_y)
        Coordinates.append(Coordinate(tmp_x, tmp_y, i))

    sorted_by_x = sorted(Coordinates, key=lambda coordinate: coordinate.x)
    sorted_by_y = sorted(Coordinates, key=lambda coordinate: coordinate.y)

    Edges = []
    for i in range(0, N - 1):
        cost_x = min(abs(sorted_by_x[i].x - sorted_by_x[i + 1].x), abs(sorted_by_x[i].y - sorted_by_x[i + 1].y))
        Edges.append(Edge(sorted_by_x[i].n, sorted_by_x[i + 1].n, cost_x))
        # Edges.append(Edge(sorted_by_x[i + 1].n, sorted_by_x[i].n, cost_x))
        cost_y = min(abs(sorted_by_y[i].x - sorted_by_y[i + 1].x), abs(sorted_by_y[i].y - sorted_by_y[i + 1].y))
        Edges.append(Edge(sorted_by_y[i].n, sorted_by_y[i + 1].n, cost_y))
        # Edges.append(Edge(sorted_by_y[i + 1].n, sorted_by_y[i].n, cost_y))

    par = [0 for i in range(N)]
    rank = [0 for i in range(N)]
    V = N
    E = 2 * (N - 1)

    print(kruskal())

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
 
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7
 
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
 
 
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 subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a
 
def main():
    N = I()
    a = []
    b = []
    for i in range(N):
        x,y = LI()
        a.append((x,i))
        b.append((y,i))
    a.sort()
    b.sort()
    t = []
    for i in range(1,N):
        t.append((a[i][0]-a[i-1][0], a[i][1], a[i-1][1]))
        t.append((b[i][0]-b[i-1][0], b[i][1], b[i-1][1]))
    t.sort()
    r = 0
    uf = UnionFind(N)
    for c,d,e in t:
        if uf.union(d,e):
            r += c
 
    return r
 
print(main())

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

n = int(input())
x_loc, y_loc = [], []
for i in range(n):
    x, y = map(int, input().split())
    x_loc.append((x, i))
    y_loc.append((y, i))
x_loc.sort()
y_loc.sort()
links = [set() for _ in range(n)]
for (x1, i1), (x2, i2) in zip(x_loc, x_loc[1:]):
    dist = abs(x1 - x2)
    links[i1].add((dist, i2))
    links[i2].add((dist, i1))
for (y1, i1), (y2, i2) in zip(y_loc, y_loc[1:]):
    dist = abs(y1 - y2)
    links[i1].add((dist, i2))
    links[i2].add((dist, i1))

visited = {0}
queue = list(links[0])
heapify(queue)
total = 0
while True:
    cost, i = heappop(queue)
    if i in visited:
        continue
    visited.add(i)
    total += cost
    if len(visited) == n:
        break
    for cost2, j in links[i]:
        if j in visited:
            continue
        heappush(queue, (cost2, j))
print(total)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.parents = list(range(size))

    def find(self, i):
        ret = i
        path = []
        while self.parents[ret]!=ret:
            path.append(ret)
            ret = self.parents[ret]
        for p in path:
            self.parents[p] = ret
        return ret

    def union(self, i, j):
        self.parents[self.find(i)] = j

n = int(input())
xys = [(tuple(map(int, input().split())), i) for i in range(n)]

sortx = sorted(xys, key=lambda xy: xy[0][0])
roadsx = [(sortx[i][0][0]-sortx[i-1][0][0], sortx[i][1], sortx[i-1][1]) for i in range(1, n)]
sorty = sorted(xys, key=lambda xy: xy[0][1])
roadsy = [(sorty[i][0][1]-sorty[i-1][0][1], sorty[i][1], sorty[i-1][1]) for i in range(1, n)]
roads = roadsx + roadsy
roads.sort(key=lambda x:x[0])

ctr = 1
ans = 0
uf = UnionFind(n)
for road in roads:
    if ctr >= n:
        break
    cost, i1, i2 = road
    if uf.find(i1) != uf.find(i2):
        ans += cost
        ctr += 1
        uf.union(i1, i2)

print(ans)

Submission status: Accepted

Solution code:
A=range(input())
P=[map(int,raw_input().split())+[i]for i in A]
o=sorted
def r(x):
 if A[x]<x:A[x]=x=r(A[x])
 return x
def u((w,X)):x,y=o(map(r,X));A[y]=x;return(x<y)*w
def s(i):P.sort(key=lambda x:x[i]);return[(q[i]-p[i],(q[2],p[2]))for p,q in zip(P,P[1:])]
print sum(map(u,o(s(0)+s(1))))

Submission status: Accepted

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

a = range(n)
def root(x):
    if x != a[x]:a[x]=x=root(a[x])
    return x
def unite(x, y):
    x=root(x);y=root(y)
    a[max(x,y)]=min(x,y)
Q=[]
def s(i):
    P.sort(key=lambda x:x[i])
    for j in R[:-1]:
        Q.append((P[j+1][i] - P[j][i], P[j][2], P[j+1][2]))
s(0);s(1);Q.sort()
ans = 0
for w,x,y in Q:
    if root(x)!=root(y):
        ans += w
        unite(x, y)
print ans

Submission status: Accepted

Solution code:
# D
import numpy as np
N = int(input())
X = []
Y = []

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

# edges
X_s = np.argsort(np.array(X))
Y_s = np.argsort(np.array(Y))

edge_list = []
edge_weight = []
for i in range(N-1):
    edge_list.append([X_s[i], X_s[i+1]])
    edge_weight.append(X[X_s[i+1]] - X[X_s[i]])
    edge_list.append([Y_s[i], Y_s[i+1]])
    edge_weight.append(Y[Y_s[i+1]] - Y[Y_s[i]])
    
# sort edges
sel = np.argsort(np.array(edge_weight))

# union find tree
uf = np.arange(N)


res = 0
flg = np.zeros(N)

for s in sel:
    m, n = edge_list[s]
    # find union
    gr_m = m
    gr_m_list = []
    gr_n = n
    gr_n_list = []
    while gr_m != uf[gr_m]:
        gr_m_list.append(gr_m)
        gr_m = uf[gr_m]
    for m_ in gr_m_list:
        uf[m_] = gr_m
        
    while gr_n != uf[gr_n]:
        gr_n_list.append(gr_n)
        gr_n = uf[gr_n]
    for n_ in gr_n_list:
        uf[n_] = gr_n
        
    if gr_m == gr_n:
        pass
    else:
        res += edge_weight[s]
        uf[gr_n] = gr_m
print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3

import array
import collections
import heapq
import itertools


AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
Town = collections.namedtuple("Town", "idx x y")
INF = 2 ** 31 - 1
NO_VERTEX = -1


# Prim法で頂点0からの最小全域木を求める
def compute_mst_prim(max_v, adj_list):
    # pred[u]は頂点uの「ひとつ前」の頂点を表す
    pred = [NO_VERTEX for _ in range(max_v)]
    # uとpred[u]を結ぶ辺の重みがkey[u]に入る
    key = [INF for _ in range(max_v)]
    key[0] = 0
    # 二分ヒープを優先度付きキューとして用いる
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    # 優先度付きキューに頂点が入っているかを示す配列
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)


def solve(n, towns):
    txs = sorted(towns, key=lambda t: t.x)
    tys = sorted(towns, key=lambda t: t.y)
    adj_list = [set() for _ in range(n)]
    g = itertools.chain(zip(txs[:-1], txs[1:]), zip(tys[:-1], tys[1:]))
    for t1, t2 in g:
        cost = min(abs(t1.x - t2.x), abs(t1.y - t2.y))
        adj_list[t1.idx].add(AdjacentVertex(t2.idx, cost))
        adj_list[t2.idx].add(AdjacentVertex(t1.idx, cost))
    (_, key) = compute_mst_prim(n, adj_list)
    return sum(key)


def main():
    n = int(input())
    towns = [Town(idx, *(int(z) for z in input().split())) for idx in range(n)]
    res = solve(n, towns)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N = II()
    x, y = [], []
    for i in range(N):
        _x, _y = ILI()
        x.append((i, _x))
        y.append((i, _y))
    return N, x, y


class UnionFind(object):
    def __init__(self, number_of_nodes):  # 初期化
        self.par = array.array("L", range(number_of_nodes))
        self.rank = array.array("L", (0 for i in range(number_of_nodes)))

    def root(self, node):  # 根を求める
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r  # 経路圧縮
            return r

    def in_the_same_set(self, node1, node2):  # 同じ集合に属するか
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):  # 属する集合を併合
        x = self.root(node1)
        y = self.root(node2)
        if x == y:
            pass
        elif 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 solve(N, x, y):
    edges = []
    x.sort(key=lambda x: x[1])
    y.sort(key=lambda x: x[1])
    for i in range(N - 1):
        x_s, x_e = x[i], x[i + 1]
        y_s, y_e = y[i], y[i + 1]
        edges.append((x_s[0], x_e[0], x_e[1] - x_s[1]))
        edges.append((y_s[0], y_e[0], y_e[1] - y_s[1]))

    edges.sort(key=lambda x: x[2])
    union_find = UnionFind(N)
    ans = 0
    for edge in edges:
        if not union_find.in_the_same_set(edge[0], edge[1]):
            union_find.unite(edge[0], edge[1])
            ans += edge[2]

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import operator
import sys
import heapq

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


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


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


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


def read_str():
    return input()


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


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


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


def dist(j, k):
    return min(abs(pairs[j][0] - pairs[k][0]), abs(pairs[j][1] - pairs[k][1]))


n = read_int()
pairs = [read_int_list() for i in range(n)]

p = list(range(n))
rank = [0] * n

edges = []

for pos in range(2):
    indices = list(range(n))
    indices.sort(key=lambda u: pairs[u][pos])
    for i in range(1, n):
        j = indices[i - 1]
        k = indices[i]
        w = dist(j, k)
        heapq.heappush(edges, (w, j, k))

res = 0
while edges:
    edge = heapq.heappop(edges)
    w, j, k = edge
    if find_set(j) != find_set(k):
        res += w
        _union(j, k)

print(res)

Submission status: Accepted

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

    def findset(self,x):
        if self.parent[x]==x:
            return x
        else:
            self.parent[x]=self.findset(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x=self.findset(x)
        y=self.findset(y)
        if x==y:
            return
        if self.rank[x]<self.rank[y]:
            self.parent[x]=y
            self.tree_num-=1
            self.tree_w[y]+=self.tree_w[x]
        else:
            self.parent[y]=x
            self.tree_num-=1
            self.tree_w[x]+=self.tree_w[y]
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

    def same(self,x,y):
        if self.findset(x)==self.findset(y):
            return True
        else:
            return False

    def tree_number(self):
        return self.tree_num

    def tree_weight(self,x):
        return self.tree_w[self.findset(x)]
n=int(raw_input())
xy=[]
yx=[]
for i in xrange(n):
    x, y = map(int,raw_input().split())
    xy.append([x,y,i])
    yx.append([y,x,i])
xy.sort()
yx.sort()
dist=[]
for i in xrange(n-1):
    a,b,idx1=xy[i]
    c,d,idx2=xy[i+1]
    dist.append([min(abs(a-c),abs(b-d)),idx1,idx2])
for i in xrange(n-1):
    a,b,idx1=yx[i]
    c,d,idx2=yx[i+1]
    dist.append([min(abs(a-c),abs(b-d)),idx1,idx2])
dist.sort()
uf=UnionFind(n)
ans=0
for i in xrange(2*(n-1)):
    d,idx1,idx2=dist[i]
    if uf.same(idx1,idx2):continue
    uf.unite(idx1,idx2)
    ans+=d
print ans