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

Solution (Python):
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 = int(input())
zahyo = []
for i in range(n):
    x,y = map(int,input().split())
    zahyo.append((x,y,i))
xza = sorted(zahyo)
yza = sorted(zahyo,key=lambda x: x[1])
edge = [[] for i in range(n)]

for i in range(n-1):
    c = abs(xza[i][0]-xza[i+1][0])
    edge[xza[i][2]].append((c,xza[i+1][2]))
    edge[xza[i+1][2]].append((c,xza[i][2]))
for i in range(n-1):
    c = abs(yza[i][1]-yza[i+1][1])
    edge[yza[i][2]].append((c,yza[i+1][2]))
    edge[yza[i+1][2]].append((c,yza[i][2]))
print(prim_heap())

Solution (Python):
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())


N = int(input())
xy = []
uf = UnionFind(N)
d = {}
j = 0
for i in range(N):
    x, y = map(int, input().split())
    if not (x,y) in d:
        d[(x,y)] = j
        xy.append((x,y))
        j += 1
N = len(xy)

xy = sorted(xy, key = lambda x:x[0])

root = []
for i in range(N-1):
    before_x, before_y = xy[i]
    x, y = xy[i+1]
    root.append((d[xy[i]],d[xy[i+1]],x - before_x))

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

for i in range(N-1):
    before_x, before_y = xy[i]
    x, y = xy[i+1]
    root.append((d[xy[i]],d[xy[i+1]],y - before_y))

root = sorted(root, key = lambda x:x[2])

ans = 0
for s,g,c in root:
    if uf.same(s,g):
        continue
    else:
        uf.union(s,g)
        ans += c

print(ans)

Solution (Python):
n = int(input())
path = []

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]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            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)

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

x_li = sorted(path)
y_li = sorted(path,key=lambda x:(x[1]))

edge = []

for i in range(1,n):
    edge.append((x_li[i][2],x_li[i-1][2],x_li[i][0]-x_li[i-1][0]))
    edge.append((y_li[i][2],y_li[i-1][2],y_li[i][1]-y_li[i-1][1]))

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

uf = UnionFind(n)
cost = 0

for i,j,k in edge:
    if not uf.same(i,j):
        uf.union(i,j)
        cost += k

print(cost)

Solution (Python):

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)


def size(x):
    return -par[find(x)]
n = int(input())


par = [-1]*n

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

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

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

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

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

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

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

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


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

    N = int(input())

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

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

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

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

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

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

    
    
    
    
    ret = 0
    for cost, a, b in sorted(xes + yes, key=itemgetter(0)):
        if uf.same(a, b): continue
        uf.unite(a, b)
        ret += cost
    print(ret)


if __name__ == '__main__':
    main()

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

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

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

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

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

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


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

    N = int(input())

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

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

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

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

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

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

    
    
    
    
    ret = 0
    
    for cost, a, b in sorted(xes + yes, key=itemgetter(0)):
        
        if uf.same(a, b): continue
        uf.unite(a, b)
        ret += cost
    print(ret)


if __name__ == '__main__':
    main()

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

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

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

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

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

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


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

    N = int(input())

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

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

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

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

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

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

    
    
    
    
    ret = 0
    joined = set()
    for cost, a, b in sorted(xes + yes, key=itemgetter(0)):
        if (a in joined) or (b in joined): continue
        if uf.same(a, b): continue
        uf.unite(a, b)
        ret += cost
    print(ret)


if __name__ == '__main__':
    main()

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

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


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

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


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

Solution (Python):
"""Minimum spanning tree with Kruskal's algorithm"""
import sys


class UnionFind:
    def __init__(self, n):
        
        self.n = n
        
        self._root_table = list(range(n))
        
        self._size_table = [1] * n

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

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

        if x == y:
            return

        
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

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

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

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

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

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

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

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

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


input = sys.stdin.readline


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

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys

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



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

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

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

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

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


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


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

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

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


if __name__ == '__main__':
    resolve()

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

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

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

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

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

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


class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)  
        self.rank = [0] * (n + 1)

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

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

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

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


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

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

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

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

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

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

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

print(cost)

Solution (Python):
class UnionFind:
    def __init__(self, n=1):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.parent[y] = x
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

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

X.sort()
Y.sort()
road = []

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

add_cand(X); add_cand(Y)

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

print(ans)

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

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

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

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

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

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

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys

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



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

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

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

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

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


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


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

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

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


if __name__ == '__main__':
    resolve()

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

Solution (Python):



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

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

edge = []



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

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

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



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

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

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


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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

edge.sort()

def kruskal():
    res = 0
    G = UnionFind(N)
    for cost, p, q, in edge:
        if not G.same(p, q):
            G.union(p, q)
            res += cost
    return res


ans = kruskal()

print(ans)

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


def find(x):
    global par
    if par[x]<0:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
        
def unite(x,y):
    x,y=find(x),find(y)
    global par
    if x==y:return False
    else:
        if par[x]>par[y]:x,y=y,x
        par[x]+=par[y]
        par[y]=x
        return True

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

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

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

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

print(ans)

Solution (Python):


import heapq
N = int(input())
townX = []
townY = []
for i in range(N):
    x,y = map(int,input().split())
    townX.append((x-1, i))
    townY.append((y-1, i))
townX.sort()
townY.sort()
edge = [[] for i in range(N)]
for i in range(N-1):
    x, nowTown = townX[i]
    xx, nextTown = townX[i+1]
    edge[nowTown].append((xx-x, nextTown))
    edge[nextTown].append((xx-x, nowTown))
for i in range(N-1):
    y, nowTown = townY[i]
    yy, nextTown = townY[i+1]
    edge[nowTown].append((yy-y, nextTown))
    edge[nextTown].append((yy-y, nowTown))
q = []
used = [0]*N
used[0] = 1
ans = 0


for i in edge[0]:
    heapq.heappush(q, i)
while len(q)>0:
    price, nowTown = heapq.heappop(q)
    if used[nowTown] == 0:
        used[nowTown] = 1
        ans += price
        for p,j in edge[nowTown]:
            if used[j] == 0:
                heapq.heappush(q, (p, j))
print(ans)

Solution (Python):
from heapq import heappush, heappop


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

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

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

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

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

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

heappush(q, (abs(x[N-1][0]-x[0][0]), x[N-1][1], x[0][1]))
heappush(q, (abs(y[N-1][0]-y[0][0]), y[N-1][1], y[0][1]))

while len(q) > 0:
    d, a, b = heappop(q)
    if S.find(a) != S.find(b):
        ans += d
        S.union(a, b)
print(ans)