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


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

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

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

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

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

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

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

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

    
    G = []
    for i in range(1, N):
        a, x1 = X[i - 1]
        b, x2 = X[i]
        G.append((a,b,x2-x1))
        a, y1 = Y[i - 1]
        b, y2 = Y[i]
        G.append((a, b, y2 - y1))

    
    ans = 0
    uf = UnionFind(N)
    G.sort(key=lambda x: x[2])
    for a, b, w in G:
        if not uf.is_same(a, b):
            uf.union(a, b)
            ans += w
    print(ans)

if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

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 kruskal(es, V):
    es.sort(key=lambda x:x[2])
    uf = UnionFind(V)
    res = 0
    for e in es:
        if not uf.same(e[0], e[1]):
            uf.union(e[0], e[1])
            res += e[2]
    return res

def resolve():
    N = I()
    xy = [LI() for _ in range(N)]

    
    xy_x_asc = sorted(enumerate(xy), key=lambda x: x[1][0])
    xy_y_asc = sorted(enumerate(xy), key=lambda x: x[1][1])
    edge = []
    for i in range(N-1):
        xc = xy_x_asc[i][1][0]
        yc = xy_x_asc[i][1][1]
        xyc_num = xy_x_asc[i][0]
        xn = xy_x_asc[i+1][1][0]
        yn = xy_x_asc[i+1][1][1]
        xyn_num = xy_x_asc[i+1][0]
        edge.append([xyc_num, xyn_num, abs(xn-xc)])
    for i in range(N-1):
        xc = xy_y_asc[i][1][0]
        yc = xy_y_asc[i][1][1]
        xyc_num = xy_y_asc[i][0]
        xn = xy_y_asc[i+1][1][0]
        yn = xy_y_asc[i+1][1][1]
        xyn_num = xy_y_asc[i+1][0]
        edge.append([xyc_num, xyn_num, abs(yn-yc)])

    
    mst_cost = kruskal(edge, N)
    print(mst_cost)

if __name__ == '__main__':
    resolve()

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

lx = sorted(l)
ly = sorted(l, key=lambda x: x[1])

e = []
for i in range(n-1):
    e.append([lx[i+1][0]-lx[i][0],lx[i+1][2],lx[i][2]])
    e.append([ly[i+1][1]-ly[i][1],ly[i+1][2],ly[i][2]])


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

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

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

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

    def size(self,x):
        x = self.find(x)
        return -self.uf[x]
s = set()
u = Unionfind(n)
count = 0
e.sort()
for i in e:
    if not u.same(i[1],i[2]):
        u.union(i[1],i[2])
        s.add(i[1])
        s.add(i[2])
        count += i[0]
print(count)

Solution (Python):
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        
        self._parent = [n for n in range(0, N)]
        
        self._size = [1] * N

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

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

        
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

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

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

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

import sys

input=sys.stdin.readline

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

X.sort()
Y.sort()

edge=[]

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

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

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

print(ans)

Solution (Python):
from operator import itemgetter
from heapq import heappush, heappop, heapify

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

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

ans = 0
while que:
    cv, v = heappop(que)
    if used[v]:
        continue
    used[v] = 1
    ans += cv
    for w, c in G[v]:
        if used[w]:
            continue
        heappush(que, (c, w))
print(ans)

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

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

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

    def add(self, u, v, d):
        """
        Parameters
        ----------
        u:int
            from node (0-index)
        v:int
            to node (0-index)
        d:int
            cost
        """
        self.edges.append([u, v, d])

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

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

    def _size(self, x):
        x = self._find(x)
        return self.counter[x]

    def _same(self, x, y):
        return self._find(x) == self._find(y)

    def Kruskal(self):
        """
        Return
        ----------
        res:int
            sum of cost
        """
        edges = sorted(self.edges, key=lambda x: x[2])  
        res = 0
        for e in edges:
            if not self._same(e[0], e[1]):
                self._unite(e[0], e[1])
                res += e[2]
        return res

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

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

input:
3
1 5
3 9
7 8

output:
    3
'''

N = int(input())
XY = [[i] + list(map(int, input().split())) for i in range(N)] 
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())


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

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

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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



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

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

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

if __name__ == "__main__":
	main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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



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

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

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

if __name__ == "__main__":
	main()

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

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

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

main()

Solution (Python):
from heapq import *

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

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

    N = int(input())
    X = [(0,0)] * N
    Y = [(0,0)] * N

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

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

    for i in range(N - 1):
        x1, j1 = X[i]
        x2, j2 = X[i + 1]
        y1, k1 = Y[i]
        y2, k2 = Y[i + 1]
        
        
        heappush(H, (x2 - x1, j1, j2))
        heappush(H, (y2 - y1, k1, k2))

    answer = 0
    data = [-1] * (N+1)  
    height = [0] * (N+1)

    while H:
        w, s, t = heappop(H)
        
        if union(s, t):
            answer += w

    print(answer)


if __name__ == "__main__":
    main()

Solution (Python):
from heapq import *

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

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

N = int(input())
X = [(0,0)] * N
Y = [(0,0)] * N
E = [(0,0)] * N

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

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

for i in range(N - 1):
    x1, j1 = X[i]
    x2, j2 = X[i + 1]
    y1, k1 = Y[i]
    y2, k2 = Y[i + 1]
    
    
    heappush(H, (x2 - x1, j1, j2))
    heappush(H, (y2 - y1, k1, k2))

answer = 0
data = [-1] * (N+1)  
height = [0] * (N+1)

while H:
    w, s, t = heappop(H)
    
    if union(s, t):
        answer += w

print(answer)

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

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

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

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

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

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

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

    Parameters
    edge : list
        全ての辺を格納する二次元のリスト edge[0]にてノード0から伸びる辺であることを表し、
        edge[0] → [距離、次の行き先] を表すlistが格納されている
    
    Returns
    res : int
        最小全域木の全ての辺のコストの総和
    '''
    used = [True] * n 
    edgelist = []
    edgelist = set_heapq(edgelist, edge, used, 0)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        edgelist = set_heapq(edgelist, edge, used, v)
        res += minedge[0]
    return res

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

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

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

print(prim_heap(edge, N))

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

N=int(input())

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


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

elist.sort(reverse=True)

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

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

Solution (Python):
import heapq
def prim():
    used = [True]*n
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist, e)
        used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not  used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist, e)
        res += minedge[0]
    return res
n = int(input())
P = []
for i in range(n):
    x, y = map(int, input().split())
    P.append((x, y, i))
P.sort()
edge = [[] for _ in range(n)]
for i in range(n-1):
    d = min(abs(P[i+1][0]-P[i][0]), abs(P[i+1][1]-P[i][1]))
    edge[P[i][2]].append((d, P[i+1][2]))
    edge[P[i+1][2]].append((d, P[i][2]))
P.sort(key = lambda x: x[1])
for i in range(n-1):
    d = min(abs(P[i+1][0]-P[i][0]), abs(P[i+1][1]-P[i][1]))
    edge[P[i][2]].append((d, P[i+1][2]))
    edge[P[i+1][2]].append((d, P[i][2]))
print(prim())

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

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

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)

        if x==y:return
        elif self.rank[x]>self.rank[y]:
            self.root[x] +=self.root[y]
            self.root[y]=x
        else:
            self.root[y] +=self.root[x]
            self.root[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y] +=1

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

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

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

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

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

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


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

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

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

    return D


import sys
input=sys.stdin.readline

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

Solution (Python):
from collections import defaultdict
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import minimum_spanning_tree


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


def create_graph(N, points):
    
    costs = defaultdict(int)
    costs_defined = defaultdict(int)
    
    points = sorted(points, key=lambda p: p.x)
    for i in range(N - 1):
        p = points[i]
        next_p = points[i + 1]
        cost = next_p.x - p.x
        min_index, max_index = min([p.index, next_p.index]), max([p.index, next_p.index])
        costs[(min_index, max_index)] = cost
        costs_defined[(min_index, max_index)] = 1
    
    points = sorted(points, key=lambda p: p.y)
    for i in range(N - 1):
        p = points[i]
        next_p = points[i + 1]
        cost = next_p.y - p.y
        min_index, max_index = min([p.index, next_p.index]), max([p.index, next_p.index])
        current_cost = costs[(min_index, max_index)]
        if costs_defined[(min_index, max_index)]:
            new_cost = min([cost, current_cost])
            costs[(min_index, max_index)] = new_cost
        else:
            costs[(min_index, max_index)] = cost
    
    rows = list()
    cols = list()
    data = list()
    for node_pair, cost in costs.items():
        rows.append(node_pair[0])
        cols.append(node_pair[1])
        data.append(cost)
    return csr_matrix((data, (rows, cols)), shape=(N, N))

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

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

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

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

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

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

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