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 UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

import sys

input=sys.stdin.readline

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

X.sort()
Y.sort()

edge=[]

for i in range(N-1):
    x1,y1,x2,y2=X[i][0],X[i][1],X[i+1][0],X[i+1][1]
    if min(abs(x1-x2),abs(y1-y2))==abs(x1-x2):
        edge.append((abs(x1-x2),X[i][2],X[i+1][2]))

for i in range(N-1):
    x1,y1,x2,y2=Y[i][0],Y[i][1],Y[i+1][0],Y[i+1][1]
    if min(abs(x1-x2),abs(y1-y2))==abs(x1-x2):
        edge.append((abs(x1-x2),Y[i][2],Y[i+1][2]))

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

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
from heapq import heappush, heappop, heapify

N = int(input())
xy = sorted([list(map(int, input().split())) + [i] for i in range(N)])
G = [[] for i in range(N)]
for i in range(N-1):
  a,b = xy[i][2], xy[i+1][2]
  c = xy[i+1][0]-xy[i][0]
  G[a].append((b,c))
  G[b].append((a,c))
xy.sort(key = itemgetter(1))
for i in range(N-1):
  a,b = xy[i][2], xy[i+1][2]
  c = xy[i+1][1]-xy[i][1]
  G[a].append((b,c))
  G[b].append((a,c))

used = [0]*N
que = [(c, w) for w, c in G[0]]
used[0] = 1
heapify(que)

ans = 0
while que:
    cv, v = heappop(que)
    if used[v]:
        continue
    used[v] = 1
    ans += cv
    for w, c in G[v]:
        if used[w]:
            continue
        heappush(que, (c, w))
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
        else:
            self.parents[xRoot] = yRoot
            if self.size[xRoot] == self.size[yRoot]:
                self.size[yRoot]+=1
N = int(input())
tree = UnionFind(N)
nodes = []
for i in range(1,N+1):
    x,y = map(int,input().split())
    nodes.append((i,x,y))
edges = []
nodes.sort(key=lambda x: x[1])
for i in range(1,N):
    edges.append((nodes[i][1]-nodes[i-1][1],nodes[i][0],nodes[i-1][0]))
nodes.sort(key=lambda x: x[2])
for i in range(1,N):
    edges.append((nodes[i][2]-nodes[i-1][2],nodes[i][0],nodes[i-1][0]))
edges.sort()
cost = 0
for w,s,t in edges:
    if tree.find(s)!=tree.find(t):
        tree.unite(s,t)
        cost += w
print(cost)

Submission status: Accepted

Solution code:
'''
クラスカル法
辺をコストの小さい順に見ていき、閉路ができなければ追加する。
追加前にuとvが同じ連結成分に属していなければ、eを追加しても閉路はできない。
したがってuとvが同じ連結成分に属しているか否かを判定するためにUnionFindを利用する。
辺をソートするためO(ElogV)
'''

class Kruskal_UnionFind():
    def __init__(self, N):
        """
        Parameters
        ----------
        n:int
            the number of nodes
        """
        self.edges = []
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

    def add(self, u, v, d):
        """
        Parameters
        ----------
        u:int
            from node (0-index)
        v:int
            to node (0-index)
        d:int
            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
        ----------
        res:int
            sum of cost
        """
        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

'''
ABC065-D
平面上にN個の街がある。
i番目の街は座標(x_i,y_i)にあり、重複することもある。
座標(a,b)と座標(c,d)の間に橋をかけるにはmin(|a-c|,|b-d|)円かかる。
任意の2つの街を道を何本か通ることで行き来できるようにするためには、
最低何円必要でしょうか。

term:
2<=N<=10**5
0<=x_i,y_i<=10**9

input:
3
1 5
3 9
7 8

output:
    3
'''

N = int(input())
XY = [[i] + list(map(int, input().split())) for i in range(N)] # [[idx, x_i, y_i],...]
graph = Kruskal_UnionFind(N)
XY = sorted(XY, key=lambda x: x[1]) # x_iについてsort
X_costs = [[XY[i - 1][0], XY[i][0], abs(XY[i - 1][1] - XY[i][1])] for i in range(1, N)]
# X_costs = [[from_idx, to_idx, x_cost],...] x_costについてsortされている
XY = sorted(XY, key=lambda x: x[2]) # y_iについてsort
Y_costs = [[XY[i - 1][0], XY[i][0], abs(XY[i - 1][2] - XY[i][2])] for i in range(1, N)]
# Y_costs = [[from_idx, to_idx, x_cost],...] y_costについてsortされている

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


'''
この問題ではnodeに番号がないため、idxをつけることでnodeに番号を振っている。
また、x,yのうち最小をとるという条件から、二重辺と見てもどうせコストの大きい方は捨てられるので題意に沿う。

今回は頂点のみが与えられており、メッシュ状に張るとそれだけで|E|=V(V-1)になって間に合わない。
そこで、辺のとり方を工夫する必要があるが、コストを最小にするためにはxの距離が最小またはyの距離が最小である必要がある。
したがってxでsortしたときの隣同士とyでsortしたときの隣同士のみをとればよい。

もし与えられている辺があった場合でO(ElogV)に間に合うのであればすべてgraph.addすればいい。
'''

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
#input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

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



def main():
	n=II()
	X=[]
	Y=[]
	for i in range(n):
		x,y=MI()
		X.append((x,i))
		Y.append((y,i))
	X.sort()
	Y.sort()
	#print(X,Y)

	li=[]
	for i in range(n-1):
		li.append((X[i+1][0]-X[i][0],X[i+1][1],X[i][1]))
		li.append((Y[i+1][0]-Y[i][0],Y[i+1][1],Y[i][1]))
	li.sort()
	#rint(li)

	UF=UnionFind(n)
	k=0
	ans=0
	for d,s,t in li:
		if k==n-1:
			break
		if UF.same(s,t):
			continue
		else:
			ans+=d
			UF.union(s,t)
			k+=1
	print(ans)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(2000000)
    input = sys.stdin.readline

    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
            else:
                self.parents[xRoot] = yRoot
                if self.size[xRoot] == self.size[yRoot]:
                    self.size[yRoot]+=1

    N = int(input())
    nodesX = []
    nodesY = []
    for i in range(1,N+1):
        x,y = map(int,input().split())
        nodesX.append((x,i))
        nodesY.append((y,i))
    nodesX.sort()
    nodesY.sort()
    edges = []
    for i in range(1,N):
        edges.append((nodesX[i][0]-nodesX[i-1][0],nodesX[i][1],nodesX[i-1][1]))
        edges.append((nodesY[i][0]-nodesY[i-1][0],nodesY[i][1],nodesY[i-1][1]))
    edges.sort()
    tree = UnionFind(N)
    cost = 0
    for w,s,t in edges:
        if tree.find(s)!= tree.find(t):
            tree.unite(s,t)
            cost += w
    print(cost)

main()

Submission status: Accepted

Solution code:
from heapq import *

def main():
    def find(x):
        parent = data[x]
        if parent < 0: return x
        root = find(parent)
        data[x] = root
        return root

    def union(x, y):
        root, second = find(x), find(y)
        if root == second: return False
        if height[root] < data[second]:
            second, root = root, second
        data[root] += data[second]
        height[root] = max(height[root], height[second]+1)
        data[second] = root
        return True

    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 = []

    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
    data = [-1] * (N+1)  # 1-indexed rootには-sizeが入る
    height = [0] * (N+1)

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

    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import *

def find(x):
    parent = data[x]
    if parent < 0: return x
    root = find(parent)
    data[x] = root
    return root

def union(x, y):
    root, second = find(x), find(y)
    if root == second: return False
    if height[root] < data[second]:
        second, root = root, second
    data[root] += data[second]
    height[root] = max(height[root], height[second]+1)
    data[second] = root
    return True

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)

X.sort()
Y.sort()
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
data = [-1] * (N+1)  # 1-indexed rootには-sizeが入る
height = [0] * (N+1)

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

print(answer)

Submission status: Accepted

Solution code:
n,*xy=map(int,open(0).read().split())
x=[[xx,i] for i,xx in enumerate(xy[::2])]
y=[[yy,i] for i,yy in enumerate(xy[1::2])]
x.sort()
y.sort()
px=[[x1-x0,i0,i1] for (x0,i0),(x1,i1) in zip(x,x[1:])]
py=[[y1-y0,i0,i1] for (y0,i0),(y1,i1) in zip(y,y[1:])]
p=px+py
x=[]
y=[]
px=[]
py=[]
p.sort()
r=[i for i in range(n)]
rank=[1 for i in range(n)]
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
def union(path):
  rx=root(path[1])
  ry=root(path[2])
  if rx==ry:
    return 0
  else:
    if rank[rx]>rank[ry]:
      r[rx]=ry
      rank[rx]+=rank[ry]
    else:
      r[ry]=rx
      rank[ry]+=rank[rx]
    return path[0]
ans=0
for i in range(len(p)):
  ans+=union(p[i])
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
x=[]
y=[]
for i in range(n):
  xx,yy=map(int,input().split())
  x.append([xx,i])
  y.append([yy,i])
x.sort()
y.sort()
px=[[x1-x0,i0,i1] for (x0,i0),(x1,i1) in zip(x,x[1:])]
py=[[y1-y0,i0,i1] for (y0,i0),(y1,i1) in zip(y,y[1:])]
p=px+py
x=[]
y=[]
px=[]
py=[]
p.sort()
r=[i for i in range(n)]
rank=[1 for i in range(n)]
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
def union(path):
  rx=root(path[1])
  ry=root(path[2])
  if rx==ry:
    return 0
  else:
    if rank[rx]>rank[ry]:
      r[rx]=ry
      rank[rx]+=rank[ry]
    else:
      r[ry]=rx
      rank[ry]+=rank[rx]
    return path[0]
ans=0
for i in range(len(p)):
  ans+=union(p[i])
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
x=[]
y=[]
for i in range(n):
  xx,yy=map(int,input().split())
  x.append([xx,i])
  y.append([yy,i])
x.sort()
y.sort()
px=[]
py=[]
for i in range(n-1):
  px.append([x[i+1][0]-x[i][0],x[i][1],x[i+1][1]])
  py.append([y[i+1][0]-y[i][0],y[i][1],y[i+1][1]])
p=px+py
x=[]
y=[]
px=[]
py=[]
p.sort()
r=[i for i in range(n)]
rank=[1 for i in range(n)]
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
def union(path):
  rx=root(path[1])
  ry=root(path[2])
  if rx==ry:
    return 0
  else:
    if rank[rx]>rank[ry]:
      r[rx]=ry
      rank[rx]+=rank[ry]
    else:
      r[ry]=rx
      rank[ry]+=rank[rx]
    return path[0]
ans=0
for i in range(len(p)):
  ans+=union(p[i])
print(ans)

Submission status: Accepted

Solution code:
import heapq
def set_heapq(que, edge, used, v, add_dist=0):
    '''
    確定地点vからつながる辺を全てqueに設定し、返却する

    Parameters
    que : heapque(touple or list)
        辺を管理するキュー (距離、次の行き先)のtopuleまたはlistにて管理
    edge : list
        全ての辺を格納する二次元のリスト edge[0]にてノード0から伸びる辺であることを表し、
        edge[0] → [距離、次の行き先] を表すlistが格納されている
    v : int
        グラフ上のノード ダイクストラでは確定したノードがvにあたる
    add_dist : int
        確定した地点に足し合わせる距離 スタート地点以外では何かしらの値が追加されることになる

    Returns
    que : heapque(touple or list)
        引数queにvからつながる辺を追加したキュー
    '''
    for a,b in edge[v]:
        if used[b]:
            heapq.heappush(que,(a+add_dist,b))
    return que

def prim_heap(edge, n):
    '''
    プリム法で最小全域木を求める

    Parameters
    edge : list
        全ての辺を格納する二次元のリスト edge[0]にてノード0から伸びる辺であることを表し、
        edge[0] → [距離、次の行き先] を表すlistが格納されている
    
    Returns
    res : int
        最小全域木の全ての辺のコストの総和
    '''
    used = [True] * n #True:不使用
    edgelist = []
    edgelist = set_heapq(edgelist, edge, used, 0)
    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
        edgelist = set_heapq(edgelist, edge, used, v)
        res += minedge[0]
    return res

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

P.sort(key=lambda x:x[1])
for i in range(N-1):
    dist = min(abs(P[i][1]-P[i+1][1]), abs(P[i][2]-P[i+1][2]))
    edge[P[i][0]].append((dist, P[i+1][0]))
    edge[P[i+1][0]].append((dist, P[i][0]))

P.sort(key=lambda x:x[2])
for i in range(N-1):
    dist = min(abs(P[i][1]-P[i+1][1]), abs(P[i][2]-P[i+1][2]))
    edge[P[i][0]].append((dist, P[i+1][0]))
    edge[P[i+1][0]].append((dist, P[i][0]))

print(prim_heap(edge, N))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input=sys.stdin.readline

N=int(input())

xylist,yxlist=[],[]
par_dic={}
for i in range(N):
  x,y=map(int,input().split())
  xylist.append((x,y))
  yxlist.append((y,x))
  par_dic[(x,y)]=(x,y)
xylist.sort()
yxlist.sort()
#print(xylist)

elist=[]
for i in range(1,N):
  x1,y1=xylist[i-1]
  x2,y2=xylist[i]
  elist.append((min(abs(x2-x1),abs(y1-y2)),(x1,y1),(x2,y2)))
  y1,x1=yxlist[i-1]
  y2,x2=yxlist[i]
  elist.append((min(abs(x2-x1),abs(y1-y2)),(x1,y1),(x2,y2)))
#print(hq)
elist.sort(reverse=True)

def get_par(x):
  if x == par_dic[x]:
    return x
  else:
    par_dic[x] = get_par(par_dic[x])
    return par_dic[x]
def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_dic[par_y] = par_x
def is_same(x,y):
  return get_par(x) == get_par(y)

answer=0
while elist:
  d,p1,p2=elist.pop()
  #print(d,p1,p2)
  if not is_same(p1,p2):
    merge(p1,p2)
    answer+=d
  
print(answer)

Submission status: Accepted

Solution code:
import heapq
def prim():
    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
n = int(input())
P = []
for i in range(n):
    x, y = map(int, input().split())
    P.append((x, y, i))
P.sort()
edge = [[] for _ in range(n)]
for i in range(n-1):
    d = min(abs(P[i+1][0]-P[i][0]), abs(P[i+1][1]-P[i][1]))
    edge[P[i][2]].append((d, P[i+1][2]))
    edge[P[i+1][2]].append((d, P[i][2]))
P.sort(key = lambda x: x[1])
for i in range(n-1):
    d = min(abs(P[i+1][0]-P[i][0]), abs(P[i+1][1]-P[i][1]))
    edge[P[i][2]].append((d, P[i+1][2]))
    edge[P[i+1][2]].append((d, P[i][2]))
print(prim())

Submission status: Accepted

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

    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.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y] +=1

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

    def size(self,x):
        return -self.root[self.Find_Root(x)]

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

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

    def group_members(self):
        return {i:self.members(i) for i in self.roots()}

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


def kruskal():
    D,M=[],[]

    A,B=sorted(XY),sorted(XY, key=lambda x: x[1])
    for i in range(n-1):
        M.append([min(abs(A[i][0]-A[i+1][0]),abs(A[i][1]-A[i+1][1])),A[i][2],A[i+1][2]])
        M.append([min(abs(B[i][0]-B[i+1][0]),abs(B[i][1]-B[i+1][1])),B[i][2],B[i+1][2]])

    M.sort()
    for w,s,t in M:
        if UnionFind.isSameGroup(s,t) is False:
            UnionFind.Unite(s,t)
            D.append(w)

    return D


import sys
input=sys.stdin.readline

n=int(input())
XY=[list(map(int,input().split()))+[i+1] for i in range(n)]
UnionFind=UnionFind(n+1)
print(sum(kruskal()))

Submission status: Accepted

Solution code:
from collections import defaultdict
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree


class Point:
 
    def __init__(self, index, x, y):
        self.index = index
        self.x = x
        self.y = y


def create_graph(N, points):
    # Caclulate costs
    costs = defaultdict(int)
    costs_defined = defaultdict(int)
    # Sort by `x` and create edges between adjacent nodes
    points = sorted(points, key=lambda p: p.x)
    for i in range(N - 1):
        p = points[i]
        next_p = points[i + 1]
        cost = next_p.x - p.x
        min_index, max_index = min([p.index, next_p.index]), max([p.index, next_p.index])
        costs[(min_index, max_index)] = cost
        costs_defined[(min_index, max_index)] = 1
    # Sort by `y` and create edges between adjacent nodes
    points = sorted(points, key=lambda p: p.y)
    for i in range(N - 1):
        p = points[i]
        next_p = points[i + 1]
        cost = next_p.y - p.y
        min_index, max_index = min([p.index, next_p.index]), max([p.index, next_p.index])
        current_cost = costs[(min_index, max_index)]
        if costs_defined[(min_index, max_index)]:
            new_cost = min([cost, current_cost])
            costs[(min_index, max_index)] = new_cost
        else:
            costs[(min_index, max_index)] = cost
    # Create csgraph
    rows = list()
    cols = list()
    data = list()
    for node_pair, cost in costs.items():
        rows.append(node_pair[0])
        cols.append(node_pair[1])
        data.append(cost)
    return csr_matrix((data, (rows, cols)), shape=(N, N))

 
def main():
    N = int(input())
    points = list()
    for index in range(N):
        x, y = list(map(int, input().split(' ')))
        points.append(Point(index, x, y))
    graph = create_graph(N, points)
    mst = minimum_spanning_tree(graph)
    print(int(mst.sum()))
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class DisjointSets:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.siz = [1]*n

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

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

    def unite(self,x,y): 
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.siz[x] < self.siz[y]:
            x,y = y,x
        self.parent[y] = x
        self.siz[x] += self.siz[y]

    def size(self,x):
        return self.siz[self.root(x)]
        
n = int(input())
X = []
Y = []
for i in range(n):
    x,y = map(int,input().split())
    X.append((i,x))
    Y.append((i,y))
X.sort(key = lambda x:x[1])
Y.sort(key = lambda y:y[1])
edges = []
for i in range(1,n):
    a,x1 = X[i-1]
    b,x2 = X[i]
    edges.append((a,b,x2-x1))
    c,y1 = Y[i-1]
    d,y2 = Y[i]
    edges.append((c,d,y2-y1))
edges.sort(key = lambda y:y[2])

ans = 0
ds = DisjointSets(n)
for i in range(2*n-2):
    u,v,dist = edges[i]
    if ds.same(u,v): continue
    ds.unite(u,v)
    ans += dist
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
hqx=[]
hqy=[]
for i in range(n):
    x,y=map(int,input().split())
    hqx.append((x,i))
    hqy.append((y,i))
hqx.sort()
hqy.sort()
prex,prexi=hqx[0]
prey,preyi=hqy[0]
edges=[]#(cost,v1,v2)
for i in range(1,n):
    x,xi=hqx[i]
    y,yi=hqy[i]
    edges.append((x-prex,prexi,xi))
    edges.append((y-prey,preyi,yi))
    prex,prexi=x,xi
    prey,preyi=y,yi
edges.sort()

frag=list(range(n+1))
fragnum=[0]*(n+1)

def takefrag(p):
    stock=[]
    while frag[frag[p]]!=frag[p]:
        stock.append(p)
        p=frag[p]
    p=frag[p]
    for i in stock:
        frag[i]=p
    return p

count=0
ans=0
for i in range(2*n):
    cost,a,b=edges[i]
    f1,f2 = map(takefrag,(a,b))
    if f1!=f2:
        count+=1
        f1,f2 = min(f1,f2),max(f1,f2)
        frag[f1]=f2
        ans+=cost
    if count==n-1:
        break

print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = list(range(n))
        self.size = [1]*n
        self.cost = 0
        
    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 unit(self,x,y,dist):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.size[x] < self.size[y]:
            x,y = y,x
        self.size[x] += self.size[y]
        self.par[y] = x
        self.cost += dist
        
n,*xy = map(int,open(0).read().split())
x = [(x,i) for i,x in enumerate(xy[::2])]
y = [(y,i) for i,y in enumerate(xy[1::2])]

x.sort()
y.sort()

xdist = [(x2-x1, i1, i2) for (x1,i1),(x2,i2) in zip(x,x[1:])]
ydist = [(y2-y1, i1, i2) for (y1,i1),(y2,i2) in zip(y,y[1:])]

dist_list = sorted(xdist+ydist)

uf = UnionFind(n)
for dist,i1,i2 in  dist_list:
    uf.unit(i1,i2,dist)
print(uf.cost)

Submission status: Accepted

Solution code:
N = int(input())
h = [list(map(int, input().split())) for _ in range(N)]

x = [(val[0],i) for i,val in enumerate(h)]
y = [(val[1],i) for i,val in enumerate(h)]

x.sort()
y.sort()
edge = []
for i in range(1,N):
    # (cost, start, end)
    edge.append((x[i][0]-x[i-1][0], x[i-1][1], x[i][1]))
    edge.append((y[i][0]-y[i-1][0], y[i-1][1], y[i][1]))
edge.sort()
par = list(range(N))
rank = [0]*N

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

def unite(val1, val2):
    val1 = find(val1)
    val2 = find(val2)
    if val1==val2:
        return
    if rank[val1] < rank[val2]:
        par[val1] = val2
    else:
        par[val2] = val1
        if rank[val1] == rank[val2]:
            rank[val1] += 1
def same(val1, val2):
    return find(val1)==find(val2)

res = 0
for e in edge:
    start = e[1]
    end = e[2]
    if same(start, end):
        continue
    res += e[0]
    unite(start, end)
print(res)

Submission status: Accepted

Solution code:
import heapq
N = int(input())
X = []
Y = []
for n in range(N):
    x, y = map(int,input().split())
    X.append((x, n))
    Y.append((y, n))
X.sort()
Y.sort()
adj = [ [] for v in range(N)]
for n in range(N-1):
    cost = X[n+1][0] - X[n][0]
    adj[X[n+1][1]].append((cost, X[n][1]))
    adj[X[n][1]].append((cost, X[n+1][1]))
    cost = Y[n+1][0] - Y[n][0]
    adj[Y[n+1][1]].append((cost, Y[n][1]))
    adj[Y[n][1]].append((cost, Y[n+1][1]))

visited = [0] * N
pq = []
for w, t in adj[0]:
    heapq.heappush(pq, (w, t))
visited[0] = 1

ans = 0
while(pq):
    w, t = heapq.heappop(pq)
    if visited[t]:
        continue
    visited[t] = 1
    ans += w
    for w, s in adj[t]:
        if visited[s]==0:
            heapq.heappush(pq, (w, s))
print (ans)

Submission status: Accepted

Solution code:
## x座標かy座標で隣り合わないものを繋ぐ辺は間に存在する点との接続で事足りるので不要
N = int(input())
city = []
for i in range(N):
    city_i = [i] + list(map(int,input().split()))
    city.append(city_i)
#print(city)

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

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



def find(x):
    if par[x] < 0:
        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 False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

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

par = [-1]*N

ans = 0
for e in edges:
    if same(e[1],e[2]):
        continue
    unite(e[1],e[2])
    ans += e[0]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
city = []
for i in range(N):
    city_i = [i] + list(map(int,input().split()))
    city.append(city_i)
#print(city)

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

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



def find(x):
    if par[x] < 0:
        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 False
    else:
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

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

par = [-1]*N

ans = 0
for e in edges:
    if same(e[1],e[2]):
        continue
    unite(e[1],e[2])
    ans += e[0]
print(ans)