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:
import sys
input = sys.stdin.readline

def same_tree(node_a, node_b):
    if node_a.root() == node_b.root():
        return True

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        node = self
        while not node.is_root:
            node = node.parent
        return node

def main():
    N = int(input())
    
    nodes = [Node() for i in range(N)]

    # 各町の座標をタプル(i, x, y)に入れて配列に格納
    xy = []
    for i in range(N):
        x, y = map(int, input().split())
        xy.append((i, x, y))
    
    # 使う可能性のある辺のみを取り出す
    edges = []
    xy = sorted(xy, key=lambda x: x[1])# x座標昇順
    # print("x:", xy)
    for i in range(1, N):
        edges.append((xy[i][1] - xy[i-1][1], xy[i-1][0], xy[i][0]))
    xy = sorted(xy, key=lambda x: x[2])# y座標昇順
    # print("y:", xy)
    for i in range(1, N):
        edges.append((xy[i][2] - xy[i-1][2], xy[i-1][0], xy[i][0]))
    
    ans = 0
    edges = sorted(edges)
    # print(edges)
    for (cost, a, b) in edges:
        if not same_tree(nodes[a], nodes[b]):
            unite(nodes[a], nodes[b])
            ans += cost
    print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    class UnionFind(object):
        """
        query: O(Ack^-1(n,n)) (amortize)
        """
        def __init__(self,n):
            """
            param n: number of nodes
            """
            self.__par=list(range(n))
            self.__rank=[0]*n
            self.__size=[1]*n

        def __root(self,k):
            if self.__par[k]==k: return k
            else:
                self.__par[k]=self.__root(self.__par[k])
                return self.__par[k]

        def is_same(self,i,j):
            return self.__root(i)==self.__root(j)

        def unite(self,i,j):
            i=self.__root(i)
            j=self.__root(j)
            if i==j: return
            if self.__rank[i]>self.__rank[j]:
                self.__par[j]=i
            else:
                self.__par[i]=j
                if self.__rank[i]==self.__rank[j]: self.__rank[j]+=1

    # Kruskal's algorithm
    from operator import itemgetter
    n=int(input())
    P=[0]*n
    edges=[0]*(2*n-2)
    for i in range(n):
        x,y=map(int,input().split())
        P[i]=(x,y,i)
    # xでsort
    P.sort(key=itemgetter(0))
    for k in range(n-1):
        x0,y0,i=P[k]
        x1,y1,j=P[k+1]
        edges[k]=(i,j,min(abs(x0-x1),abs(y0-y1)))
    # yでsort
    P.sort(key=itemgetter(1))
    for k in range(n-1):
        x0,y0,i=P[k]
        x1,y1,j=P[k+1]
        edges[k+n-1]=(i,j,min(abs(x0-x1),abs(y0-y1)))
    # edgesをcostでsort
    edges.sort(key=itemgetter(2))
    # union findに突っ込んでいく
    tree=UnionFind(n)
    ans=0
    for i,j,cost in edges:
        if tree.is_same(i,j): continue
        tree.unite(i,j)
        ans+=cost
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# input=lambda :sys.stdin.readline().rstrip()
def resolve():
    class UnionFind(object):
        """
        query: O(Ack^-1(n,n)) (amortize)
        """
        def __init__(self,n):
            """
            param n: number of nodes
            """
            self.__par=list(range(n))
            self.__rank=[0]*n
            self.__size=[1]*n

        def __root(self,k):
            if self.__par[k]==k: return k
            else:
                self.__par[k]=self.__root(self.__par[k])
                return self.__par[k]

        def is_same(self,i,j):
            return self.__root(i)==self.__root(j)

        def unite(self,i,j):
            i=self.__root(i)
            j=self.__root(j)
            if i==j: return
            if self.__rank[i]>self.__rank[j]:
                self.__par[j]=i
            else:
                self.__par[i]=j
                if self.__rank[i]==self.__rank[j]: self.__rank[j]+=1

    # 候補となるedgesは2N-2個しかないため、全列挙
    # Kruskal's algorithmでuniteしていく
    from operator import itemgetter
    n=int(input())
    P=[0]*n
    edges=[0]*(2*n-2)
    for i in range(n):
        x,y=map(int,input().split())
        P[i]=(x,y,i)
    # xでsort
    P.sort(key=itemgetter(0))
    for k in range(n-1):
        x0,y0,i=P[k]
        x1,y1,j=P[k+1]
        edges[k]=(i,j,min(abs(x0-x1),abs(y0-y1)))
    # yでsort
    P.sort(key=itemgetter(1))
    for k in range(n-1):
        x0,y0,i=P[k]
        x1,y1,j=P[k+1]
        edges[k+n-1]=(i,j,min(abs(x0-x1),abs(y0-y1)))
    # edgesをcostでsort
    edges.sort(key=itemgetter(2))
    # union findに突っ込んでいく
    tree=UnionFind(n)
    ans=0
    for i,j,cost in edges:
        if tree.is_same(i,j): continue
        tree.unite(i,j)
        ans+=cost
    print(ans)

resolve()

Submission status: Accepted

Solution code:

class uf_tree():

    def __init__(self,n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

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

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

def kruscal(n,edge_arr):
    edge_arr.sort(key=lambda x:x[2])
    ans = []
    tree = uf_tree(n)
    for e in edge_arr:
        s = e[0]-1
        g = e[1]-1
        if tree.same(s,g):
            continue
        else:
            ans.append(e)
            tree.unite(s,g)
    return ans

p = []
edge = []
n = int(input())
for i in range(n):
    x,y = map(int,input().split())
    p.append([x,y,i+1])

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

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

ans = kruscal(n,edge)
tot = 0
for e in ans:
    tot += e[2]
print(tot)

Submission status: Accepted

Solution code:

import heapq

def prime_method():
    not_went = [True] * n  # n個の点に行ったかという話
    edges = []
    start = graph[0]
    for e in start:
        heapq.heappush(edges,e)
    not_went[0] = False
    cost = 0
    while len(edges) != 0:
        minedge = heapq.heappop(edges)
        if not not_went[minedge[1]]:
            continue
        v = minedge[1]
        gv = graph[v]
        not_went[v] = False
        for temp in gv:
            if not_went[temp[1]]:  # その頂点に行ってなければ
                heapq.heappush(edges, temp)
        cost += minedge[0]
    return cost
    # a[1] = [[2,3],[5,11]] → 点1からコスト2で頂点3に行ける辺、点1からコスト5で頂点11に行ける辺がある


n = int(input())
graph = [[] for i in  range(n)]
cities = []
for i in range(n):
    cities.append(tuple(map(int,input().split()))+tuple([i]))


citiesX=sorted(cities,key=lambda x:x[0])
citiesY=sorted(cities,key=lambda x:x[1])

for i in range(n-1):
    graph[citiesX[i][2]].append(((citiesX[i+1][0] - citiesX[i][0]),citiesX[i+1][2]))
    graph[citiesX[i+1][2]].append(((citiesX[i+1][0] - citiesX[i][0]),citiesX[i][2]))
    graph[citiesY[i][2]].append(((citiesY[i+1][1] - citiesY[i][1]),citiesY[i+1][2]))
    graph[citiesY[i+1][2]].append(((citiesY[i+1][1] - citiesY[i][1]),citiesY[i][2]))
print(prime_method())

Submission status: Accepted

Solution code:
from heapq import *

def prim(V, E):
    '''
    Input:
        V = list(range(N))
        E = {i: defaultdict(int) for i in range(N)}
    Output:
        the edges of the minimum weight tree and its weight
    '''
    N = len(V)
    weight = 0; edges = [];
    used = [False]*N; used[0] = True; n_used = 1;
    heap = [(c, 0, v) for v, c in E[0].items()]; heapify(heap)
    while heap and n_used < N:
        c, u, v = heappop(heap)
        if used[v]: continue
        used[v] = True; n_used += 1; edges.append((u, v))
        weight += c
        for w, d in E[v].items():
            if not used[w]: heappush(heap, (d, v, w))
    return edges, weight

N = int(input())
cities = [(a, b, i) for i, (a, b) in enumerate([tuple(map(int, input().split())) for _ in range(N)])]
sorted_x, sorted_y = sorted(cities, key=lambda x:x[0]), sorted(cities, key=lambda x:x[1])
E = {i: {} for i in range(N)}
for i in range(N-1):
    (a1, _, u), (a2, _, v) = sorted_x[i], sorted_x[i+1]
    E[u][v] = min(a2 - a1, E[u][v]) if E[u].get(v) is not None else a2 - a1
    E[v][u] = E[u][v]
    (_, b1, u), (_, b2, v) = sorted_y[i], sorted_y[i+1]
    E[u][v] = min(b2 - b1, E[u][v]) if E[u].get(v) is not None else b2 - b1
    E[v][u] = E[u][v]
V = list(range(N))
_, ans = prim(V, E)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]


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


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

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

    def same(self, x, y):
        return self.find(x) == self.find(y)
def compute_mst_kruskal(N, edges):#N = 頂点数、edges 0-indexed
    edges = sorted(edges, key = lambda x:x[2])
    UF = UnionFind(N)
    cost = 0
    for edge in edges:
        x, y, w = edge
        if not UF.same(x, y):
            UF.unite(x, y)
            cost+=w
    return cost
N = int(input())
ixy = []
for i in range(N):
    x, y = map(int, input().split())
    ixy.append((i, x, y))
xy_x = sorted(ixy, key = lambda x:x[1])
xy_y = sorted(ixy, key = lambda x:x[2])
edges = []
for i in range(N-1):
    i1, x1, y1 = xy_x[i]
    i2, x2, y2 = xy_x[i+1]
    edges.append([i1, i2, x2-x1])
    i1, x1, y1 = xy_y[i]
    i2, x2, y2 = xy_y[i+1]
    edges.append([i1, i2, y2-y1])
ans = compute_mst_kruskal(N, edges)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]


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


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

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

    def same(self, x, y):
        return self.find(x) == self.find(y)
def compute_mst_kruskal(N, edges):#N = 頂点数、edges 0-indexed
    edges = sorted(edges, key = lambda x:x[2])
    UF = UnionFind(N)
    cost = 0
    for edge in edges:
        x, y, w = edge
        if not UF.same(x, y):
            UF.unite(x, y)
            cost+=w
    return cost
N = int(input())
ixy = []
for i in range(N):
    x, y = map(int, input().split())
    ixy.append((i, x, y))
xy_x = sorted(ixy, key = lambda x:x[1])
xy_y = sorted(ixy, key = lambda x:x[2])
edges = []
for i in range(N-1):
    i1, x1, y1 = xy_x[i]
    i2, x2, y2 = xy_x[i+1]
    edges.append((i1, i2, x2-x1))
    i1, x1, y1 = xy_y[i]
    i2, x2, y2 = xy_y[i+1]
    edges.append((i1, i2, y2-y1))
ans = compute_mst_kruskal(N, edges)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]


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


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

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

    def same(self, x, y):
        return self.find(x) == self.find(y)
def compute_mst_kruskal(N, edges):#N = 頂点数、edges 0-indexed
    edges = sorted(edges, key = lambda x:x[2])
    UF = UnionFind(N)
    cost = 0
    for edge in edges:
        x, y, w = edge
        if not UF.same(x, y):
            UF.unite(x, y)
            cost+=w
    return cost
N = int(input())
ixy = []
for i in range(N):
    x, y = map(int, input().split())
    ixy.append((i, x, y))
xy_x = sorted(ixy, key = lambda x:x[1])
xy_y = sorted(ixy, key = lambda x:x[2])
edges = []
for i in range(N-1):
    i1, x1, y1 = xy_x[i]
    i2, x2, y2 = xy_x[i+1]
    edges.append((i1, i2, x2-x1))
    i1, x1, y1 = xy_y[i]
    i2, x2, y2 = xy_y[i+1]
    edges.append((i1, i2, y2-y1))
ans = compute_mst_kruskal(N, edges)
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
P=[tuple(map(int,input().split())) for i in range(N)]
X=[(i,P[i][0]) for i in range(N)]
Y=[(i,P[i][1]) for i in range(N)]
X.sort(key=lambda x:x[1])
Y.sort(key=lambda x:x[1])
Z=[(X[i][0],X[i+1][0],X[i+1][1]-X[i][1]) for i in range(N-1)]+[(Y[i][0],Y[i+1][0],Y[i+1][1]-Y[i][1]) for i in range(N-1)]
Z.sort(key=lambda x:x[2])
root=[-1]*N
def search(i):
    global root
    if root[i]>=0:
        root[i]=search(root[i])
        return root[i]
    return i
ans=0
for i,j,k in Z:
    ri=search(i)
    rj=search(j)
    if ri==rj:
        continue
    elif root[ri]<=root[rj]:
        root[ri]+=root[rj]
        root[rj]=ri
        ans+=k
    else:
        root[rj]+=root[ri]
        root[ri]=rj
        ans+=k
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
city=[0]*N
for i in range(N):
    x,y=map(int,input().split())
    city[i]=(i,x,y)
city.sort(key=lambda x:x[1])
data=[(city[i][0],city[i+1][0],city[i+1][1]-city[i][1]) for i in range(N-1)]
city.sort(key=lambda x:x[2])
data+=[(city[i][0],city[i+1][0],city[i+1][2]-city[i][2]) for i in range(N-1)]
data.sort(key=lambda x:x[2])
root=[-1]*N
def search(i):
    global root
    if root[i]>=0:
        root[i]=search(root[i])
        return root[i]
    return i
cost=0
for i,j,k in data:
    ri=search(i)
    rj=search(j)
    if ri==rj:
        continue
    elif root[ri]<=root[rj]:
        cost+=k
        root[ri]+=root[rj]
        root[rj]=ri
    elif root[ri]>root[rj]:
        cost+=k
        root[rj]+=root[ri]
        root[ri]=rj
print(cost)

Submission status: Accepted

Solution code:
class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[i for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)

N=int(input())
edge=[]
points=[]
for i in range(N):
    x,y=map(int,input().split())
    points.append((i,x,y))
points.sort(key=lambda x:x[1])
for i in range(N-1):
    i1,x1,y1=points[i]
    i2,x2,y2=points[i+1]
    wt=min(abs(x1-x2),abs(y1-y2))
    edge.append((wt,i1,i2))
points.sort(key=lambda x:x[2])
for i in range(N-1):
    i1,x1,y1=points[i]
    i2,x2,y2=points[i+1]
    wt=min(abs(x1-x2),abs(y1-y2))
    edge.append((wt,i1,i2))
edge.sort()
G=UnionFind(N)
ans=0
for e in edge:
    w,i,j=e
    if not(G.same(i,j)):
        G.unite(i,j)
        ans+=w
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


# 入力
N = int(input())
x, y = (
    zip(*(map(int, input().split()) for _ in range(N))) if N else
    ((), ())
)

# x座標およびy座標について街をソートし、ソート後に隣り合う街を辺で結んだ重み付きグラフを作成する
# 作成したグラフに対してプリム法により解を求める
ts = list(zip(range(1, N + 1), x, y))
ts_x = sorted(ts, key=lambda t: t[1])
ts_y = sorted(ts, key=lambda t: t[2])
G = [{} for _ in range(N + 1)]
for ((i, a, b), (j, c, d)) in zip(ts_x[1:], ts_x):
    G[i][j] = min(abs(c - a), abs(d - b))
    G[j][i] = G[i][j]
for ((i, a, b), (j, c, d)) in zip(ts_y[1:], ts_y):
    G[i][j] = min(abs(c - a), abs(d - b))
    G[j][i] = G[i][j]


def prim(G):
    used = [False for _ in range(len(G))]
    res = 0
    q = []
    used[1] = True
    for j, w in G[1].items():
        heappush(q, (w, j))
    while q:
        w, j = heappop(q)
        if not used[j]:
            used[j] = True
            res += w
            for j2, w2 in G[j].items():
                heappush(q, (w2, j2))
    return res


ans = prim(G)
# 出力
print(ans)

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    def __init__(self, size):
        """
        size:頂点の数
        parent[x]->parent of x
        rank[x] -> height of tree of x
        """
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]

    def find(self, x):
        """
        xのrootを返す
        """
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        """
        x,yを同じグループとしてまとめる
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

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

    def same(self, x, y):
        """
        xとyが同じグループならTrue
        """
        return self.find(x) == self.find(y)

    def component(self):
        """
        各連結成分のrootの集合を返す
        len()をとれば連結成分の数が求められる
        return-> set()
        """
        comp = set()
        for i in self.parent:
            p = self.find(i)
            comp.add(p)
        return comp

    def componentNum(self):
        """
        連結成分の数を返す
        """
        return len(self.component())

    def __str__(self):
        """
        for debug
        クラスのlistの情報を出力
        """
        ret = "parents\n"
        ret += " ".join(map(str, self.parent))
        ret += '\n'
        ret += " ".join(map(str, self.rank))
        return ret


N = int(input())
X = []
Y = []
cand = []
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 x: x[1])

for p1, p2 in zip(X, X[1:]):
    i1, x1 = p1
    i2, x2 = p2
    cand.append([i1, i2, x2-x1])

for p1, p2 in zip(Y, Y[1:]):
    i1, y1 = p1
    i2, y2 = p2
    cand.append([i1, i2, y2-y1])

Un = UnionFind(N)
ans = 0

cand = sorted(cand, key=lambda x: x[2])
for s, g, w in cand:
    if Un.same(s, g):
        continue
    else:
        Un.union(s, g)
        ans += w
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    city = []
    for i in range(n):
        x,y = map(int, input().split())
        city.append((x,y,i))
    edges = []
    # x
    city.sort()
    for i in range(n-1):
        dist = city[i+1][0] - city[i][0]
        edges.append((dist, city[i][2], city[i+1][2]))
    # y
    city.sort(key=lambda x:x[1])
    for i in range(n-1):
        dist = city[i+1][1] - city[i][1]
        edges.append((dist, city[i][2], city[i+1][2]))

    edges.sort()
    ans = 0

    uf = [-1]*n
    def root(x):
        if uf[x] < 0:
            return x
        uf[x] = root(uf[x])
        return uf[x]
    def unite(x,y):
        rx, ry = root(x), root(y)
        if rx == ry:
            return False
        if rx > ry:
            rx,ry = ry,rx
        uf[rx] += uf[ry]
        uf[ry] = rx
        return True

    for dist, from_, to in edges:
        if unite(from_, to):
            ans += dist
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
def prim_heap():
    used = [True] * n #True:不使用
    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())

#隣接リストの作成 edge[i]:[コスト,行先]
edge = [[] for i in range(n)]
p=[]
edge=[[] for i in range(n)]
for i in range(n):
    p.append(tuple(map(int,input().split()))+tuple([i]))
x_sorted=sorted(p,key=lambda x:x[0])
y_sorted=sorted(p,key=lambda x:x[1])
for i in range(n-1):
    edge[x_sorted[i][2]].append((x_sorted[i+1][0]-x_sorted[i][0],x_sorted[i+1][2]))
    edge[x_sorted[i+1][2]].append((x_sorted[i+1][0]-x_sorted[i][0],x_sorted[i][2]))
    edge[y_sorted[i][2]].append((y_sorted[i+1][1]-y_sorted[i][1],y_sorted[i+1][2]))
    edge[y_sorted[i+1][2]].append((y_sorted[i+1][1]-y_sorted[i][1],y_sorted[i][2]))

print(prim_heap())

Submission status: Accepted

Solution code:
from heapq import heappush,heappop
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()
inf=float("inf")
G=[[]*N for i in range(N)]
for i in range(N-1):
  G[X[i][1]].append((X[i+1][0]-X[i][0],X[i+1][1]))
  G[X[i+1][1]].append((X[i+1][0]-X[i][0],X[i][1]))
  G[Y[i][1]].append((Y[i+1][0]-Y[i][0],Y[i+1][1]))
  G[Y[i+1][1]].append((Y[i+1][0]-Y[i][0],Y[i][1]))
  
Q=[(0,0)]
ans=0
visited=[False]*N
while Q:
  c,n=heappop(Q)
  if visited[n]:
    continue
  visited[n]=True
  ans+=c
  for c2,n2 in G[n]:
    if visited[n2]:
      continue
    else:
      heappush(Q,(c2,n2))

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import heapq
n=int(input())
p=[]
d=[[] for i in range(n)]
for i in range(n):
    p.append(tuple(map(int,input().split()))+tuple([i]))
x_sorted=sorted(p,key=lambda x:x[0])
y_sorted=sorted(p,key=lambda x:x[1])
for i in range(n-1):
    d[x_sorted[i][2]].append((x_sorted[i+1][0]-x_sorted[i][0],x_sorted[i+1][2]))
    d[x_sorted[i+1][2]].append((x_sorted[i+1][0]-x_sorted[i][0],x_sorted[i][2]))
    d[y_sorted[i][2]].append((y_sorted[i+1][1]-y_sorted[i][1],y_sorted[i+1][2]))
    d[y_sorted[i+1][2]].append((y_sorted[i+1][1]-y_sorted[i][1],y_sorted[i][2]))
h=[]
for q in d[0]:
    heapq.heappush(h,q)
used=[False for i in range(n)]
used[0]=True
cost=0
while len(h):
    q=heapq.heappop(h)
    if used[q[1]]:
        continue
    used[q[1]]=True
    cost+=q[0]
    for r in d[q[1]]:
        heapq.heappush(h,r)
print(cost)

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
            if self.par[rx] > self.par[ry]:
                self.par[rx] = ry
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
        return

N = int(input())
V = [0 for _ in range(N)]
Edge = []
for i in range(N):
    x, y = inpl()
    V[i] = (x, y, i)
V = sorted(V, key = lambda x: x[0])
for i in range(N-1):
    Edge.append((V[i+1][0]-V[i][0],V[i+1][2],V[i][2]))
V = sorted(V, key = lambda x: x[1])
for i in range(N-1):
    Edge.append((V[i+1][1]-V[i][1],V[i+1][2],V[i][2]))

Edge = sorted(Edge, key = lambda x: -x[0])
U = UnionFind(N)
ctr = 0
ans = 0
while ctr != N-1:
    c,i,j = Edge.pop()
    if U.find(i) != U.find(j):
        U.union(i,j)
        ans += c
        ctr += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
ax = []
ay = []
for i in range(n):
    x,y = map(int, input().split())
    ax.append((x,i))
    ay.append((y,i))

ax.sort()
ay.sort()

edge = []
for i in range(n-1):
    v = ax[i][1]
    u = ax[i+1][1]
    c = abs(ax[i][0]-ax[i+1][0])
    edge.append((c,v,u))

    v = ay[i][1]
    u = ay[i+1][1]
    c = abs(ay[i][0]-ay[i+1][0])
    edge.append((c,v,u))

edge.sort()



class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(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:
            return

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

t = UnionFind(n)
res = 0
for e in edge:
    cost = e[0]
    v = e[1]
    u = e[2]

    if not t.same(v,u):
        # print((v,u,cost))
        t.unite(v,u)
        res += cost

print(res)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

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 = x2 - x1
    links[i1].add((dist, i2))
    links[i2].add((dist, i1))
for (y1, i1), (y2, i2) in zip(y_loc, y_loc[1:]):
    dist = y2 - y1
    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:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1 << 30)

class union_find:
  def __init__(self, n): self.par = [-1] * n; self.rank = [0] * n
  def __repr__(self): return "union_find({0})".format([self.root(i) for i in range(n)])
  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[x] = y
    else:
      self.par[y] = x
      if self.rank[x] == self.rank[y]: self.rank[x] += 1
  def root(self, x):
    if self.par[x] == -1: 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)

N = read()
ps = []
for i in range(N):
  x, y = reads()
  ps.append((i, x, y))

edges = []

for q in range(1, 3):
  ps.sort(key=lambda p: p[q])
  for i in range(N-1):
    edges.append((ps[i+1][q] - ps[i][q], ps[i][0], ps[i+1][0]))

edges.sort()

uf = union_find(N)
ans = 0
for c, i, j in edges:
  if not uf.same(i, j):
    ans += c
    uf.unite(i, j)
print(ans)

Submission status: Accepted

Solution code:
import heapq
import sys
sys.setrecursionlimit(10 ** 7)

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]
		self.count = 0

#	def find(self, x):
#		while self.table[x] >= 0:
#			x = self.table[x]
#		return x

	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[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1

			self.count += 1
			return True
		return False

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

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

edges = []
uf = UnionFind(n)

for i in range(n - 1):
	if vx[i][1] == vx[i + 1][1]:
		uf.union(vx[i][0], vx[i + 1][0])
	else:
		heapq.heappush(edges, (vx[i + 1][1] - vx[i][1], vx[i][0], vx[i + 1][0]))

	if vy[i][1] == vy[i + 1][1]:
		uf.union(vy[i][0], vy[i + 1][0])
	else:
		heapq.heappush(edges, (vy[i + 1][1] - vy[i][1], vy[i][0], vy[i + 1][0]))


#edges = sorted(edges, key=lambda x: x[2], reverse=True)
#print(edges)

ans = 0

while edges != []:
	e = heapq.heappop(edges)
	if uf.union(e[1], e[2]):
		ans += e[0]
	if uf.count == n - 1:
		break

print(ans)