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:
class UnionFind:
    def __init__(self, n):
        self.v = [-1] * n

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

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

        if x == y:
            return False
        else:
            if self.v[x] > self.v[y]:
                x, y = y, x
            self.v[x] += self.v[y]
            self.v[y] = x
            return True

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

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


def main():
    from operator import itemgetter
    import sys
    input = sys.stdin.readline

    N = int(input())

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

    xs = tuple(sorted(xs))
    ys = tuple(sorted(ys))

    dx = {e: i for i, e in enumerate(xs)}
    dy = {e: i for i, e in enumerate(ys)}

    uf = UnionFind(N * 2)
    for x, y in ps:
        uf.unite(dx[x], dy[y] + N)

    def make_edges(xs, start):
        xes = []
        for i, (x0, x1) in enumerate(zip(xs, xs[1:]), start=start):
            xes.append((abs(x1 - x0), i, i + 1))
        return xes

    xes = make_edges(xs, start=0)
    yes = make_edges(ys, start=N)

    # Kruskal
    # 最小コストの辺から順に使用する
    # 同じ連結成分に属していればつながない(閉路を作らない)
    # コスト昇順ソート済みの辺リストを使用する
    ret = 0
    for cost, a, b in sorted(xes + yes, key=itemgetter(0)):
        if uf.same(a, b): continue
        uf.unite(a, b)
        ret += cost
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

        if x == y:
            return False
        else:
            if self.v[x] > self.v[y]:
                x, y = y, x
            self.v[x] += self.v[y]
            self.v[y] = x
            return True

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

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


def main():
    from operator import itemgetter
    import sys
    input = sys.stdin.readline

    N = int(input())

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

    xs = tuple(sorted(xs))
    ys = tuple(sorted(ys))

    dx = {e: i for i, e in enumerate(xs)}
    dy = {e: i for i, e in enumerate(ys)}

    uf = UnionFind(N * 2)
    for x, y in ps:
        uf.unite(dx[x], dy[y] + N)

    def make_edges(xs, d, *, add_val=0):
        xes = []
        for x0, x1 in zip(xs, xs[1:]):
            xes.append((abs(x1 - x0), d[x0] + add_val, d[x1] + add_val))
        return xes

    xes = make_edges(xs, dx)
    yes = make_edges(ys, dy, add_val=N)

    # Kruskal
    # 最小コストの辺から順に使用する
    # 同じ連結成分に属していればつながない(閉路を作らない)
    # コスト昇順ソート済みの辺リストを使用する
    ret = 0
    # joined = set()
    for cost, a, b in sorted(xes + yes, key=itemgetter(0)):
        # if (a in joined) or (b in joined): continue
        if uf.same(a, b): continue
        uf.unite(a, b)
        ret += cost
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

        if x == y:
            return False
        else:
            if self.v[x] > self.v[y]:
                x, y = y, x
            self.v[x] += self.v[y]
            self.v[y] = x
            return True

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

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


def main():
    from operator import itemgetter
    import sys
    input = sys.stdin.readline

    N = int(input())

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

    xs = tuple(sorted(xs))
    ys = tuple(sorted(ys))

    dx = {e: i for i, e in enumerate(xs)}
    dy = {e: i for i, e in enumerate(ys)}

    uf = UnionFind(N * 2)
    for x, y in ps:
        uf.unite(dx[x], dy[y] + N)

    def make_edges(xs, d, *, add_val=0):
        xes = []
        for x0, x1 in zip(xs, xs[1:]):
            xes.append((abs(x1 - x0), d[x0] + add_val, d[x1] + add_val))
        return xes

    xes = make_edges(xs, dx)
    yes = make_edges(ys, dy, add_val=N)

    # Kruskal
    # 最小コストの辺から順に使用する
    # 同じ連結成分に属していればつながない(閉路を作らない)
    # コスト昇順ソート済みの辺リストを使用する
    ret = 0
    joined = set()
    for cost, a, b in sorted(xes + yes, key=itemgetter(0)):
        if (a in joined) or (b in joined): continue
        if uf.same(a, b): continue
        uf.unite(a, b)
        ret += cost
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
class UnionFind:
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
    self.siz=n
  def find_root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.find_root(self.n[x])
      return self.n[x]
  def unite(self,x,y):
    x=self.find_root(x)
    y=self.find_root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:
      self.n[x]+=self.n[y]
      self.n[y]=x
    else:
      self.n[y]+=self.n[x]
      self.n[x]=y
      if self.r[x]==self.r[y]:
        self.r[y]+=1
    self.siz-=1
  def root_same(self,x,y):
    return self.find_root(x)==self.find_root(y)
  def count(self,x):
    return -self.n[self.find_root(x)]
  def size(self):
    return self.siz

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

# MSTを求める
xy.sort()
for j in range(1,n):
  sx,sy,si=xy[j-1]
  tx,ty,ti=xy[j]
  G.append((min(abs(sx-tx),abs(sy-ty)),si,ti))

xy.sort(key=lambda x:x[1])
for j in range(1,n):
  sx,sy,si=xy[j-1]
  tx,ty,ti=xy[j]
  G.append((min(abs(sx-tx),abs(sy-ty)),si,ti))

# Kruskal 法
u=UnionFind(n)
ans=0
G.sort()
for c,x,y in G:
  if u.root_same(x,y):continue
  u.unite(x,y)
  ans+=c
print(ans)

Submission status: Accepted

Solution code:
"""Minimum spanning tree with Kruskal's algorithm"""
import sys


class UnionFind:
    def __init__(self, n):
        # total number of nodes.
        self.n = n
        # node id -> root node id
        self._root_table = list(range(n))
        # root node id -> group size
        self._size_table = [1] * n

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            # Update the cache on query.
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        # Ensure that x is the larger (or equal) group.
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

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

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

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

    def roots(self):
        return [i for i, x in enumerate(self._root_table) if x == i]

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

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

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


input = sys.stdin.readline


def main():
    N = int(input())
    cities, xs, ys = [], [], []
    for i in range(N):
        x, y = map(int, input().split())
        cities.append((x, y))
        xs.append((x, i))
        ys.append((y, i))
    xs.sort()
    ys.sort()
    xd, yd = [], []
    for i in range(1, N):
        x1, c1 = xs[i - 1]
        x2, c2 = xs[i]
        if x2 - x1 <= abs(cities[c1][1] - cities[c2][1]):
            xd.append((x2 - x1, c1, c2))
        y1, c1 = ys[i - 1]
        y2, c2 = ys[i]
        if y2 - y1 < abs(cities[c1][0] - cities[c2][0]):
            xd.append((y2 - y1, c1, c2))
    xd.sort()

    uf = UnionFind(N)
    cost = 0
    merged_cnt = 0
    for d1, c1, c2 in xd:
        if not uf.same(c1, c2):
            uf.union(c1, c2)
            cost += d1
            merged_cnt += 1
            if merged_cnt == N - 1:
                break
    print(cost)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


# Union Find（経路圧縮有）
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 親が同じか判別
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 根を繋ぎ直す
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    # 親が同じか判別
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 連結成分の大きさを返す
    def size(self, x):
        return -self.parents[self.find(x)]


def kruskal(max_node, edge):
    """
    :param max_node: UnionFind木に渡す頂点数です
    :param edge: edge = [(コスト, 頂点1, 頂点2),...]の形で重み付き隣接リストを渡して下さい
    :return: 最小全域木のコストの和
    """
    edge.sort()
    uf = UnionFind(max_node)
    cost_sum = 0
    for cost, node1, node2 in edge:
        if not uf.same(node1, node2):
            cost_sum += cost
            uf.union(node1, node2)
    return cost_sum


def resolve():
    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()
    cost = []
    for i in range(n - 1):
        cost.append([abs(X[i][0] - X[i + 1][0]), X[i][1], X[i + 1][1]])
        cost.append([abs(Y[i][0] - Y[i + 1][0]), Y[i][1], Y[i + 1][1]])

    res = kruskal(n, cost)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
XY = [tuple(map(int,input().split() + [i])) for i in range(N)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * 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._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

uf = UnionFind(N)
sx = sorted(XY, key=lambda x:x[0])
sy = sorted(XY, key=lambda x:x[1])

es = []
for (x1,_,i),(x2,_,j) in zip(sx,sx[1:]):
    es.append((x2-x1, i, j))
for (_,y1,i),(_,y2,j) in zip(sy,sy[1:]):
    es.append((y2-y1, i, j))
es.sort(key=lambda x:x[0])

ans = 0
for d,i,j in es:
    if uf.is_same(i,j): continue
    uf.unite(i,j)
    ans += d
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)  # -1ならそのノードが根,で絶対値が木の要素数
        self.rank = [0] * (n + 1)

    def find(self, x):  # xの根となる要素番号を返す
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

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

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

    def getNodeLen(self, x):
        return -self.root[self.find(x)]


if __name__ == "__main__":
    N = int(input())
    XY = []
    for i in range(N):
        x, y = map(int, input().split())
        XY.append((x, y, i))

    edge = []
    XY.sort()
    for (x1, _, i), (x2, _, j) in zip(XY[:-1], XY[1:]):
        edge.append((x2 - x1, i, j))

    XY.sort(key=itemgetter(1))
    for (_, x1, i), (_, x2, j) in zip(XY[:-1], XY[1:]):
        edge.append((x2 - x1, i, j))

    uf = UF_tree(N + 10)
    edge.sort()
    ans = 0
    for cost, x, y in edge:
        if uf.isSame(x, y):
            continue
        uf.unite(x, y)
        ans += cost
    print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
            self.size[xRoot] += self.size[yRoot]
            self.size[yRoot] = 0
        else:
            self.parents[xRoot] = yRoot
            self.size[yRoot] += self.size[xRoot]
            self.size[xRoot] = 0

N = int(input())
XY = [[i]+list(map(int,input().split())) for i in range(N)]
edges = []
XY.sort(key=lambda x: x[1])
for j in range(1,N):
    edges.append((XY[j-1][0],XY[j][0],XY[j][1]-XY[j-1][1]))
XY.sort(key=lambda x: x[2])
for j in range(1,N):
    edges.append((XY[j-1][0],XY[j][0],XY[j][2]-XY[j-1][2]))

cost = 0
edges.sort(key=lambda x: x[2])
tree = UnionFind(N)
for i,j,c in edges:
    if tree.find(i)!=tree.find(j):
        tree.unite(i,j)
        cost += c

print(cost)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n=1):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    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):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.parent[y] = x
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

N = int(input())
uf = UnionFind(N)
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()
road = []

def add_cand(Z):
  global road
  z1, i1 = Z[0]
  for j in range(1, N):
    z2, i2 = Z[j]
    road.append((z2-z1, i1, i2))
    z1, i1 = z2, i2

add_cand(X); add_cand(Y)

road.sort()
ans = 0
for cost, i, j in road:
  if uf.is_same(i, j):
    continue
  uf.union(i, j)
  ans += cost

print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n
  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.parents[x] > self.parents[y]:
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x
  def same(self, x, y):
    return self.find(x) == self.find(y)

def main():
    N = int(readline())

    X = []
    Y = []
    for i in range(N):
        x, y = map(int, readline().split())
        X.append([i,x])
        Y.append([i,y])
    X.sort(key=lambda x:x[1])
    Y.sort(key=lambda x:x[1])

    L = []
    for i in range(N-1):
        u, x1 = X[i]
        v, x2 = X[i+1]
        L.append([u,v,x2-x1])
        u, y1 = Y[i]
        v, y2 = Y[i+1]
        L.append([u,v,y2-y1])
    L.sort(key=lambda x:x[2])

    uf = UnionFind(N)
    ans = 0
    for i in range(2*(N-1)):
        u,v,w = L[i]
        if not uf.same(u,v):
            uf.union(u,v)
            ans += w

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


# Union Find（経路圧縮有）
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 親が同じか判別
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 根を繋ぎ直す
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    # 親が同じか判別
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 連結成分の大きさを返す
    def size(self, x):
        return -self.parents[self.find(x)]


def kruskal(max_node, edge):
    """
    :param max_node: UnionFind木に渡す頂点数です
    :param edge: edge = [(コスト, 頂点1, 頂点2),...]の形で重み付き隣接リストを渡して下さい
    :return: 最小全域木のコストの和
    """
    edge.sort()
    uf = UnionFind(max_node)
    cost_sum = 0
    for cost, node1, node2 in edge:
        if not uf.same(node1, node2):
            cost_sum += cost
            uf.union(node1, node2)
    return cost_sum


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

    def calc(L):
        for i in range(n - 1):
            cost = abs(L[i][1] - L[i + 1][1])
            edge.append((cost, L[i][0], L[i + 1][0]))

    edge = []
    X.sort(key=lambda x: x[1])
    Y.sort(key=lambda x: x[1])
    calc(X)
    calc(Y)
    print(kruskal(n, edge))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def main():
	import sys
	input=sys.stdin.readline
	n=int(input())
	xy=[]
	node=[[]for _ in range(n)]
	for i in range(n):
		x,y=map(int,input().split())
		xy.append((i,x,y))
	xy.sort(key=lambda x:x[1])
	for i in range(len(xy)-1):
		node[xy[i][0]].append((abs(xy[i][1]-xy[i+1][1]),xy[i+1][0]))#dis,num
		node[xy[i+1][0]].append((abs(xy[i][1]-xy[i+1][1]),xy[i][0]))#dis,num
	xy.sort(key=lambda x:x[2])
	for i in range(len(xy)-1):
		node[xy[i][0]].append((abs(xy[i][2]-xy[i+1][2]),xy[i+1][0]))#dis,num
		node[xy[i+1][0]].append((abs(xy[i][2]-xy[i+1][2]),xy[i][0]))#dis,num
	from heapq import heappop,heappush
	visited=[False]*n
	visited[0]=True
	pq=[]
	for x in node[0]:
		heappush(pq,(x[0],x[1]))
	ans=0
	for _ in range(n-1):
		while True:
			u=heappop(pq)
			if visited[u[1]]==False:
				break
		ans+=u[0]
		pre_dis=u[0]
		u_dis=u[0];u_num=u[1]
		ans+=abs(u_dis-pre_dis)
		visited[u_num]=True
		for x in node[u_num]:
			x_dis=x[0];x_num=x[1]
			if visited[x_num]==False:
				heappush(pq,(x_dis,x_num))
	print(ans)
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
# atcoder problem solving

# Built?
import sys
input=sys.stdin.readline
N = int(input())
d = []

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

edge = []

# x座標に関する辺の設定

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

for i in range(N-1):
    a, px, py = d[i]
    b, qx, qy = d[i+1]
    dis = abs(px-qx)

    edge.append((dis, a, b))
    edge.append((dis, b, a))

# y座標に関する辺の設定

d.sort(key=lambda x: x[2])

for i in range(N-1):
    a, px, py = d[i]
    b, qx, qy = d[i+1]
    dis = abs(py-qy)

    edge.append((dis, a, b))
    edge.append((dis, b, a))


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

edge.sort()
# 最小全域木（クラスかるほう）
def kruskal():
    res = 0
    G = UnionFind(N)
    for cost, p, q, in edge:
        if not G.same(p, q):
            G.union(p, q)
            res += cost
    return res


ans = kruskal()

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
par=[-1]*n

# this par & rank are initialized lists
def find(x):
    global par
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
        
def unite(x,y):
    x,y=find(x),find(y)
    global par
    if x==y:return False
    else:
        if par[x]>par[y]:x,y=y,x
        par[x]+=par[y]
        par[y]=x
        return True

def size(x):
    return -par[find(x)]
def same(x,y):
    return find(x)==find(y)

p=[]
edge=[]
for i in range(n):
  x,y=map(int,input().split())
  p.append([x,y,i])
p.sort(key=lambda x:x[0])
for i in range(n-1):
  x0,_,j=p[i]
  x1,_,k=p[i+1]
  edge.append([x1-x0,j,k])

p.sort(key=lambda x:x[1])
for i in range(n-1):
  _,y0,j=p[i]
  _,y1,k=p[i+1]
  edge.append([y1-y0,j,k])

edge.sort()
ans=0
for i in range(len(edge)):
  cost,u,v=edge[i]
  if not same(u,v):
    unite(u,v)
    ans+=cost

print(ans)

Submission status: Accepted

Solution code:
# プリム法
# 愚直にやるとO(N**2)
import heapq
N = int(input())
townX = []
townY = []
for i in range(N):
    x,y = map(int,input().split())
    townX.append((x-1, i))
    townY.append((y-1, i))
townX.sort()
townY.sort()
edge = [[] for i in range(N)]
for i in range(N-1):
    x, nowTown = townX[i]
    xx, nextTown = townX[i+1]
    edge[nowTown].append((xx-x, nextTown))
    edge[nextTown].append((xx-x, nowTown))
for i in range(N-1):
    y, nowTown = townY[i]
    yy, nextTown = townY[i+1]
    edge[nowTown].append((yy-y, nextTown))
    edge[nextTown].append((yy-y, nowTown))
q = []
used = [0]*N
used[0] = 1
ans = 0
# 頂点どれでもいいので根を0とする
# 全ての街に対して道があると考える
for i in edge[0]:
    heapq.heappush(q, i)
while len(q)>0:
    price, nowTown = heapq.heappop(q)
    if used[nowTown] == 0:
        used[nowTown] = 1
        ans += price
        for p,j in edge[nowTown]:
            if used[j] == 0:
                heapq.heappush(q, (p, j))
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            self.parents[y] = x

N = int(input())
q = []
ans = 0
S = UnionFind(N)
x = []
y = []

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

x.sort()
y.sort()
for i in range(N-1):
    x1, i1 = x[i]
    y1, j1 = y[i]
    x2, i2 = x[i+1]
    y2, j2 = y[i+1]
    heappush(q, (abs(x1-x2), i1, i2))
    heappush(q, (abs(y1-y2), j1, j2))

heappush(q, (abs(x[N-1][0]-x[0][0]), x[N-1][1], x[0][1]))
heappush(q, (abs(y[N-1][0]-y[0][0]), y[N-1][1], y[0][1]))
# クラスカル法
while len(q) > 0:
    d, a, b = heappop(q)
    if S.find(a) != S.find(b):
        ans += d
        S.union(a, b)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X,Y=[],[]
for i in range(N):
    x,y=map(int,input().split())
    X.append((y,i))
    Y.append((x,i))
X.sort(key=lambda t:t[0])
Y.sort(key=lambda t:t[0])
edge=[[] for i in range(N)]
for i in range(N-1):
    edge[X[i][1]].append((abs(X[i][0]-X[i+1][0]),X[i+1][1]))
    edge[X[i+1][1]].append((abs(X[i][0]-X[i+1][0]),X[i][1]))
    edge[Y[i][1]].append((abs(Y[i][0]-Y[i+1][0]),Y[i+1][1]))
    edge[Y[i+1][1]].append((abs(Y[i][0]-Y[i+1][0]),Y[i][1]))

def prim(n,edges):
    used=[False]*n
    used[0]=True
    edgelist=[]
    for edge in edges[0]:
        heappush(edgelist,edge)
    cost=0
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,edge)
        cost+=minedge[0]
    return cost

print(prim(N,edge))