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


class UnionFindTree():
    def __init__(self, N):
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def __root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.__root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.__root(a)
        r2 = self.__root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

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

    def size(self, a):
        return self.__size[self.__root(a)]

    def groups(self):
        groups = {}
        for k in self.__parent_of.keys():
            r = self.__root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N = int(input())
    X = [None] * N
    Y = [None] * N
    for i in range(N):
        x, y = map(int, input().split())
        X[i] = (x, i)
        Y[i] = (y, i)
    X.sort(key=itemgetter(0))
    Y.sort(key=itemgetter(0))
    adj = [None] * (2*N - 2)
    for i in range(N-1):
        adj[2*i] = (X[i+1][0] - X[i][0], X[i][1], X[i+1][1])
        adj[2*i+1] = (Y[i+1][0] - Y[i][0], Y[i][1], Y[i+1][1])
    adj.sort(key=itemgetter(0))
    uft = UnionFindTree(N)
    ans = 0
    for pair in adj:
        cost, a, b = pair
        if not uft.is_same(a, b):
            uft.unite(a, b)
            ans += cost
        if uft.size(a) == N:
            break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import*
from collections import*

input=sys.stdin.readline


p=defaultdict(lambda: -1)
class UNION_FIND(object):
    def __init__(self,n):
        
        self.parent=defaultdict(lambda: -1)

    def root(self,x):
        if type(self.parent[x])!=tuple:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])
            return self.parent[x]
 
    def size(self,x):
        return -self.parent[self.root(x)]
    def union(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]
        self.parent[y]=x
        return True
def compute_mst_kruskal(max_v, edges, flip):
    edges.sort(key=lambda x: x[2],reverse=flip)
    #print(edges)
    uf = UNION_FIND(max_v)
    mst = []
    for (a,b,c) in edges:
        if uf.root(a)!= uf.root(b):
            uf.union(a,b)
            mst.append(c)
    return mst


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

x=sorted(points,key=lambda x:x[0])
y=sorted(points,key=lambda x:x[1])
#print(x,y)


edges = []
for i in range(1,n):
    (a,b),(c,d)=x[i-1],x[i]
    (e,f),(g,h)=y[i-1],y[i]
    heappush(edges,((a,b),(c,d),abs(a-c)))
    heappush(edges,((e,f),(g,h),abs(f-h)))
#print(edges)
mst = compute_mst_kruskal(n, edges , 0) #0が最小化
print(sum(mst))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
N=int(input())
xy=[list(map(int,input().split()))+[i] for i in range(N)]
xy.sort()
path = []

def get_par(n):
    if par[n] is None:return n
    par[n] = get_par(par[n])
    return par[n]

def same(i,j):
    return get_par(i) == get_par(j)

def unite(i,j):
    j = get_par(j)
    par[j] = get_par(i)
    return

for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    path.append((abs(x-x2),i,j))
xy.sort(key=lambda x:x[1])
for k in range(N-1):
    x,y,i = xy[k]
    x2,y2,j = xy[k+1]
    path.append((abs(y-y2),i,j))
path.sort(key = lambda x:x[0],reverse=True)
par = [None]*N
cnt = 0
ans = 0
while cnt < N-1:
    c,i,j = path.pop()
    if same(i,j):continue
    unite(i,j)
    ans += c
    cnt += 1
print(ans)

Submission status: Accepted

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

xy.sort(key=lambda x:x[1])
edge  = []
for i in range(n-1):
    i1,x1,y1 = xy[i]
    i2,x2,y2 = xy[i+1]
    edge.append((x2-x1,i1,i2))

xy.sort(key=lambda x:x[2])
for i in range(n-1):
    i1,x1,y1 = xy[i]
    i2,x2,y2 = xy[i+1]
    edge.append((y2-y1,i1,i2))
class UnionFind():
    def __init__(self, N):
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

    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)

#クラスカル法
uf = UnionFind(n)
edge.sort()
ans = 0
edge_cnt = 0
i = 0
while edge_cnt < n-1:
    cost,i1,i2 = edge[i]
    if not uf.same(i1,i2):
        ans += cost
        uf.unite(i1,i2)
        edge_cnt += 1
    i += 1
print(ans)

Submission status: Accepted

Solution code:
class Kruskal_UnionFind():
    def __init__(self, N):
        self.edges = []
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * N

    def add(self, u, v, d):
        """
        :param u: 始点
        :param v: 終点
        :param d: コスト
        """
        self.edges.append([u, v, d])

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

    def Kruskal(self):
        """
        :return: 最小全域木のコストの和
        """
        edges = sorted(self.edges, key=lambda x: x[2])  # costでself.edgesをソートする
        res = 0
        for e in edges:
            if not self.same(e[0], e[1]):
                self.unite(e[0], e[1])
                res += e[2]
        return res


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

graph = Kruskal_UnionFind(N)
XY = sorted(XY, key=lambda x: x[1])
X_costs = [[XY[i-1][0], XY[i][0], abs(XY[i-1][1] - XY[i][1])] for i in range(1, N)]
XY = sorted(XY, key=lambda x: x[2])
Y_costs = [[XY[i-1][0], XY[i][0], abs(XY[i-1][2] - XY[i][2])] for i in range(1, N)]

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

print(graph.Kruskal())

Submission status: Accepted

Solution code:
class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.size_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.size_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        parent = self.root()
        return parent.group_id_

    def size(self):
        parent = self.root()
        return parent.size_

    def unite(self, unite_node):
        parent = self.root()
        unite_parent = unite_node.root()

        if parent.group_id_ != unite_parent.group_id_:
            if parent.size() > unite_parent.size():
                unite_parent.parent_ = parent
                parent.size_ = parent.size_ + unite_parent.size_
            else:
                parent.parent_ = unite_parent
                unite_parent.size_ = parent.size_ + unite_parent.size_
    def is_group(self,other):#selfとotherが同じグループに属するか
        return self.root()==other.root()

N = int(input())
P = [[i, list(map(int, input().split()))] for i in range(N)]

X = sorted([[i, xy[0]] for i, xy in P], key=lambda x: x[1])
Y = sorted([[i, xy[1]] for i, xy in P], key=lambda y: y[1])

Xe = [[X[i][0], X[i+1][0], abs(X[i][1]-X[i+1][1])] for i in range(N-1)]
Ye = [[Y[i][0], Y[i+1][0], abs(Y[i][1]-Y[i+1][1])] for i in range(N-1)]
E = sorted(Xe + Ye, key=lambda e: e[2])

U=[UnionFindNode(i) for i in range(N)]
i=0
ans=0
count=1
while(count<N):
    v1,v2,cost=E[i]
    if not U[v1].is_group(U[v2]):
        U[v1].unite(U[v2])
        ans+=cost
        count+=1
    i+=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

        if x == y:
            return

        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 same_check(self, x, y):
        return self.find(x) == self.find(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()
E=[]
ans=0
count=1
for i in range(N-1):
    a=X[i]
    b=X[i+1]
    c=Y[i]
    d=Y[i+1]
    E.extend([(b[0]-a[0],X[i][1],X[i+1][1]),(d[0]-c[0],Y[i][1],Y[i+1][1])])
E.sort()
"""
N = int(input())
P = [[i, list(map(int, input().split()))] for i in range(N)]

X = sorted([[i, xy[0]] for i, xy in P], key=lambda x: x[1])
Y = sorted([[i, xy[1]] for i, xy in P], key=lambda y: y[1])

Xe = [[X[i][0], X[i+1][0], abs(X[i][1]-X[i+1][1])] for i in range(N-1)]
Ye = [[Y[i][0], Y[i+1][0], abs(Y[i][1]-Y[i+1][1])] for i in range(N-1)]
E = sorted(Xe + Ye, key=lambda e: e[2])
U=UnionFind(N)
i=0
ans=0
count=1
while(count<N):
    v1,v2,cost=E[i]
    if not U.same_check(v1,v2):
        U.union(v1,v2)
        ans+=cost
        count+=1
    i+=1
print(ans)

Submission status: Accepted

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


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

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

        if x == y:
            return

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

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


E = []
# xについてソート
Towns.sort(key=lambda t: t[1])
for i in range(1, N):
    t_prev, t_now = Towns[i - 1], Towns[i]
    E.append([t_prev[0], t_now[0], t_now[1] - t_prev[1]])
# yについてソート
Towns.sort(key=lambda t: t[2])
for i in range(1, N):
    t_prev, t_now = Towns[i - 1], Towns[i]
    E.append([t_prev[0], t_now[0], t_now[2] - t_prev[2]])

E.sort(reverse=True, key=lambda e: e[2])
UF = UnionFind(N)

MST_cost = 0
i = 0
# 辺のコストが小さいものから、閉路を作らないように、木を構成する
# 最小全域木の必要辺は(頂点数-1)本
while i != N - 1:
    x, y, cost = E.pop()
    # 同じ辺集合に属していないならば（閉路が生まれないならば）
    if not UF.same(x, y):
        MST_cost += cost
        UF.union(x, y)
        i += 1

print(MST_cost)

Submission status: Accepted

Solution code:
n = int(input())
xy = [[int(item) for item in input().split()] + [i] for i in range(n)]
xsort = sorted(xy, key=lambda x : x[0])
ysort = sorted(xy, key=lambda x : x[1])

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1] * (n)
        self.rank = [0] * (n)

    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 same_check(self, x, y):
        return self.find(x) == self.find(y)

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

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

        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

edge = []
for i in range(1, n):
    xdif = abs(xsort[i-1][0] - xsort[i][0])
    ydif = abs(ysort[i-1][1] - ysort[i][1])
    edge.append([xsort[i-1][2], xsort[i][2], xdif])
    edge.append([ysort[i-1][2], ysort[i][2], ydif])
edge.sort(key=lambda x : x[2])

UF = UnionFind(n)
cost = 0
for e in edge:
    if not UF.same_check(e[0], e[1]):
        UF.union(e[0], e[1])
        cost += e[2]

print(cost)

Submission status: Accepted

Solution code:
import heapq
def prim_heap():
    used = [True] * n
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res
n, *t = map(int, open(0).read().split())
x = sorted((x, i) for i, (x, y) in enumerate(zip(t[::2], t[1::2])))
y = sorted((y, i) for i, (x, y) in enumerate(zip(t[::2], t[1::2])))
edge = [[] for _ in range(n)]
for i, j in zip(x, x[1:]):
    a, b, c = i[1], j[1], j[0] - i[0]
    edge[a].append((c, b))
    edge[b].append((c, a))
for i, j in zip(y, y[1:]):
    a, b, c = i[1], j[1], j[0] - i[0]
    edge[a].append((c, b))
    edge[b].append((c, a))
print(prim_heap())

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)  # The number of nodes under the target node.
        self.weight = [0] * (n+1)  # Distance from the root

    def find(self, x):
        if self.root[x] == x:
            return x
        else:
            y = self.find(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            self.root[x] = y
            return self.root[x]

    def unite(self, x, y, w=0):
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.root[rx] = ry
            self.size[ry] += self.size[rx]
            self.weight[rx] = w - self.weight[x] + self.weight[y]
        else:
            self.root[ry] = rx
            self.size[rx] += self.size[ry]
            self.weight[ry] = -w - self.weight[y] + self.weight[x]
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    def diff(self, x, y):
        return self.weight[y] - self.weight[x]


def kruskal(D, n):
    G = []
    UF = UnionFind(n)
    while len(D) > 0:
        cost, n1, n2 = heappop(D)

        if UF.is_same(n1, n2):
            continue
        else:
            G.append((cost, n1, n2))
            UF.unite(n1, n2)

    return G

def main():
    input = sys.stdin.readline
    N = int(input())
    C = []
    for i in range(N):
        x, y = map(int, input().split())
        C.append((i, x, y))

    X = sorted(C, key=lambda x: x[1])
    Y = sorted(C, key=lambda x: x[2])

    D = []
    for i in range(N-1):
        a, xa, _ = X[i]
        b, xb, _ = X[i+1]

        c, _, yc = Y[i]
        d, _, yd = Y[i+1]


        heappush(D, (xb - xa, a, b))
        heappush(D, (yd - yc, c, d))

    G = kruskal(D, N)
    ans = 0
    for g in G:
        ans += g[0]

    return ans


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

Submission status: Accepted

Solution code:
import sys
from heapq import heappush, heappop

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

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

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

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

def kruskal(D, n):
    G = []
    UF = UnionFind(n)
    while len(D) > 0:
        cost, n1, n2 = heappop(D)

        if UF.is_same(n1, n2):
            continue
        else:
            G.append((cost, n1, n2))
            UF.unite(n1, n2)

    return G

def main():
    input = sys.stdin.readline
    N = int(input())
    C = []
    for i in range(N):
        x, y = map(int, input().split())
        C.append((i, x, y))

    X = sorted(C, key=lambda x: x[1])
    Y = sorted(C, key=lambda x: x[2])

    D = []
    for i in range(N-1):
        a, xa, _ = X[i]
        b, xb, _ = X[i+1]

        c, _, yc = Y[i]
        d, _, yd = Y[i+1]


        heappush(D, (xb - xa, a, b))
        heappush(D, (yd - yc, c, d))

    G = kruskal(D, N)
    ans = 0
    for g in G:
        ans += g[0]

    return ans


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

Submission status: Accepted

Solution code:
import heapq


class UnionFind:
    def __init__(self, size: int):
        self.__size = size
        self.__root = [-1] * size

    def find(self, x: int)->int:
        if self.__root[x] < 0:
            return x

        root = self.find(self.__root[x])
        self.__root[x] = root

        return root

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

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

        if rx == ry:
            return

        if self.__root[ry] < self.__root[rx]:
            rx, ry = ry, rx

        self.__root[rx] += self.__root[ry]
        self.__root[ry] = rx


class PriorityQueue:
    def __init__(self):
        self.__heap = []
        self.__count = 0

    def empty(self) -> bool:
        return self.__count == 0

    def dequeue(self):
        if self.empty():
            raise Exception('empty')
        self.__count -= 1
        return heapq.heappop(self.__heap)

    def enqueue(self, v):
        self.__count += 1
        heapq.heappush(self.__heap, v)

    def __len__(self):
        return self.__count


def kruskal(edges: list, size: int)->list:
    q = PriorityQueue()
    for c, u, v in edges:
        q.enqueue((c, u, v))
    uf = UnionFind(size)

    min_tree = []
    while not q.empty():
        c, u, v = q.dequeue()

        if not uf.same(u, v):
            uf.union(u, v)
            min_tree.append((c, u, v))

    return min_tree


def built(N: int, points: list)->int:
    edges = []
    points = [(i, x, y) for i, (x, y) in enumerate(points)]
    sorted_x = sorted(points, key=lambda p: p[1])
    sorted_y = sorted(points, key=lambda p: p[2])

    for i in range(N-1):
        u, ux, _ = sorted_x[i]
        v, vx, _ = sorted_x[i+1]
        edges.append((vx-ux, u, v))

        u, _, uy = sorted_y[i]
        v, _, vy = sorted_y[i+1]
        edges.append((vy-uy, u, v))

    tree = kruskal(edges, 2*(N-1))

    return sum(c for c, _, _ in tree)


if __name__ == "__main__":
    N = int(input())
    points = [tuple(map(int, input().split())) for _ in range(N)]
    ans = built(N, points)
    print(ans)

Submission status: Accepted

Solution code:

def kruskal(v_count: int, edges: list) -> int:
    """
    :param v_count: 頂点数
    :param edges: [(weight, from, to), ... ]
    """
    from itertools import islice
    tree = [-1]*v_count

    def get_root(x) -> int:
        if tree[x] < 0:
            return x
        tree[x] = get_root(tree[x])
        return tree[x]

    def unite(a) -> bool:
        x, y = get_root(a[1]), get_root(a[2])
        if x != y:
            big, small = (x, y) if tree[x] < tree[y] else (y, x)
            tree[big] += tree[small]
            tree[small] = big
        return x != y

    cost = 0
    for w, _s, _t in islice(filter(unite, sorted(edges)), v_count-1):
        cost += w
    return cost

import sys
from operator import itemgetter
N = int(input())
#a = [[i]+list(map(int, l.split())) for i, l in enumerate(sys.stdin)]
a = []
for i in range(N):
  ta,tb =map(int,input().split())
  a.append([i,ta,tb])

x_sorted, y_sorted = sorted(a, key=itemgetter(1)), sorted(a, key=itemgetter(2))
edges = []
append = edges.append
for (i, x1, y1), (j, x2, y2) in zip(x_sorted, x_sorted[1:]):
    append((x2-x1, i, j))
for (i, x1, y1), (j, x2, y2) in zip(y_sorted, y_sorted[1:]):
    append((y2-y1, i, j))
#print(edges)
print(kruskal(N, edges))

Submission status: Accepted

Solution code:
def d_built(N, P):
    class UnionFind(object):
        def __init__(self, n):
            self.p = list(range(n))  # i番の頂点の親(parent)はi番とする
            self.rank = [0] * n  # 全頂点はランク0(繋がりなし)とする
            self.size = [1] * n  # 全頂点の連結成分の大きさ1とする

        def union(self, x, y):  # x,yを同じ連結成分に属させる
            u = self.find(x)
            v = self.find(y)
            if u == v:  # x,yは既に同じ連結成分に属していた
                return
            if self.rank[u] < self.rank[v]:
                self.p[u] = v  # ランクの大きな方につなげる
                self.size[v] += self.size[u]  # つながっている要素数だけ足す
                self.size[u] = 0  # ランクが小さかった連結成分は「解散」
            else:
                # 上と同様にやる
                self.p[v] = u
                self.size[u] += self.size[v]
                self.size[v] = 0
                if self.rank[u] == self.rank[v]:
                    # 根の分だけ1個「ずれる」
                    self.rank[u] += 1
            # 経路圧縮を行い、連結成分の代表を更新
            self.find(x)
            self.find(y)
            return None

        def find(self, x):  # 頂点xが属する連結成分の代表(根の番号)を求める
            if self.p[x] != x:  # 頂点xの代表は他の頂点だった
                self.p[x] = self.find(self.p[x])  # 経路圧縮(xを代表につなぐ)
            return self.p[x]

        def is_same(self, x, y):  # 頂点x,yは同じ連結成分に属するか？
            return self.find(x) == self.find(y)

    xs, ys = [], []
    for i, (x, y) in enumerate(P):
        xs.append((x, i))
        ys.append((y, i))
    xs.sort()
    ys.sort()

    # 頂点をつなぐ辺の候補を得る
    x_edge, y_edge = [], []
    for i in range(N - 1):
        # x座標、y座標でソートしたもので隣り合った2点を結ぶ
        x_edge.append((xs[i][1], xs[i + 1][1], xs[i + 1][0] - xs[i][0]))
        y_edge.append((ys[i][1], ys[i + 1][1], ys[i + 1][0] - ys[i][0]))
    x_edge.extend(y_edge)  # 頂点a-b間を結ぶ辺のコスト
    x_edge.sort(key=lambda x: x[2])  # コストの小さいものから並べる(クラスカル法のため)

    # クラスカル法による
    uf = UnionFind(N)
    edges = []  # 辺の情報を格納
    for x1, x2, cost in x_edge:
        if not uf.is_same(x1, x2):
            # x1, x2が同じ木に属していた場合、注目した辺を加えると閉路ができる
            uf.union(x1, x2)
            edges.append(cost)
        if len(edges) == N - 1:
            break
    return sum(edges)

N = int(input())
P = [[int(i) for i in input().split()] for j in range(N)]
print(d_built(N, P))

Submission status: Accepted

Solution code:
N=int(input())
city=[]
for i in range(N):
    x,y=map(int,input().split())
    city.append((i,x,y))
city.sort(key=lambda x:x[1])
data=[]
for i in range(N-1):
    data.append((city[i][0],city[i+1][0],city[i+1][1]-city[i][1]))
city.sort(key=lambda y:y[2])
for i in range(N-1):
    data.append((city[i][0],city[i+1][0],city[i+1][2]-city[i][2]))
data.sort(key=lambda d:d[2])
idx=[-1]*N
def find(idx,x):
    if idx[x]<0:
        return x
    elif idx[x]>=0:
        idx[x]=find(idx,idx[x])
        return idx[x]
ans=0
for q in range(len(data)):
    i,j,d=data[q]
    iidx=find(idx,i)
    jidx=find(idx,j)
    if iidx==jidx:
        continue
    elif idx[iidx]<=idx[jidx]:
        idx[iidx]+=idx[jidx]
        idx[jidx]=iidx
        ans+=d
    elif idx[iidx]>idx[jidx]:
        idx[jidx]+=idx[iidx]
        idx[iidx]=jidx
        ans+=d
print(ans)

Submission status: Accepted

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

data=[]
city.sort(key=lambda x:x[1])
for i in range(N-1):
    data.append((city[i][0],city[i+1][0],city[i+1][1]-city[i][1]))
city.sort(key=lambda y:y[2])
for i in range(N-1):
    data.append((city[i][0],city[i+1][0],city[i+1][2]-city[i][2]))
data.sort(key=lambda d:d[2])

idx=[-1]*N
def find(idx,x):
    if idx[x]<0:
        return x
    elif idx[x]>=0:
        idx[x]=find(idx,idx[x])
        return idx[x]

ans=0
for q in range(len(data)):
    i,j,d=data[q]
    iidx=find(idx,i)
    jidx=find(idx,j)
    if iidx==jidx:
        continue
    elif idx[iidx]<=idx[jidx]:
        idx[iidx]+=idx[jidx]
        idx[jidx]=iidx
        ans+=d
    elif idx[iidx]>idx[jidx]:
        idx[jidx]+=idx[iidx]
        idx[iidx]=jidx
        ans+=d
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
unil = [i for i in range(n)]
unih = [0 for _ in range(n)]

def root(p):
  if unil[p] == p:
    return p
  else:
    unil[p] = root(unil[p])
    return unil[p]

def union(p, q):
  pp, qp = root(p), root(q)
  if pp == qp:
    return
  else:
    if unih[pp] > unih[qp]:
      unil[qp] = pp
    elif unih[pp] < unih[qp]:
      unil[pp] = qp
    else:
      unil[max(pp, qp)] = min(pp, qp)
      unih[min(pp, qp)] += 1

xlist, ylist = [], []
for _ in range(n):
  x, y = map(int, input().split())
  xlist.append(x)
  ylist.append(y)

xsort = list(sorted(enumerate(xlist), key=lambda x: x[1]))
xd = [(i, j, x - prevx) for (i, prevx), (j, x) in zip(xsort, xsort[1:])]
ysort = list(sorted(enumerate(ylist), key=lambda x: x[1]))
yd = [(i, j, y - prevy) for (i, prevy), (j, y) in zip(ysort, ysort[1:])]
xyd = sorted(xd + yd, key=lambda x: x[2])

ans = 0
for i, j, d in xyd:
  if root(i) == root(j):
    continue
  else:
    ans += d
    union(i, j)
print(ans)

Submission status: Accepted

Solution code:
import sys
N = int(input())
city_ls = list()
for i in range(N):
    city_ls.append([int(i) for i in sys.stdin.readline().split()])
sort_by_x = sorted([[i, j] for i,j in city_ls], key=lambda x:x[0])
G = []
pos2id = {tuple(j) : i for i, j in enumerate(city_ls)}
for i in range(len(sort_by_x)-1):
    current_by_x = sort_by_x[i]
    next_by_x = sort_by_x[i + 1]
    G.append((abs(current_by_x[0] - next_by_x[0]),current_by_x, next_by_x))
sort_by_x.sort(key=lambda x:x[1])
for i in range(len(sort_by_x) - 1):
    current_by_x = sort_by_x[i]
    next_by_x = sort_by_x[i + 1]
    G.append((abs(current_by_x[1] - next_by_x[1]), current_by_x, next_by_x))
G.sort(key=lambda x:x[0])
sum_cost = 0
par = [i for i in range(N)]
rank = [1 for i in range(N)]
def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        pass
    else:
        if rank[x] > rank[y]:
            par[y] = x
            rank[x] += rank[y]
        else:
            par[x] = par[y]
            rank[y] += rank[x]

def is_same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False

for i in G:
    (cost, _from, _to) = i
    _from = pos2id[tuple(_from)]
    _to = pos2id[tuple(_to)]
    if is_same(_from, _to):
        continue
    unite(_from, _to)
    sum_cost += cost
print(sum_cost)