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: Time Limit Exceeded

Solution code:
import bisect
import sys
import heapq
N = int(input())
city_ls = list()
for i in range(N):
    city_ls.append([int(i) for i in sys.stdin.readline().split()])
sort_by_x = sorted([[i, j] for i,j in city_ls], key=lambda x:x[0])
sort_by_y = sorted([[j, i] for i,j in city_ls], key=lambda x:x[0])
G = []
id2pos = {i : tuple(j) for i, j in enumerate(city_ls)}
pos2id = {j : i for i, j in id2pos.items()}
for i in range(len(sort_by_x)):
    if i > 0:
        before_by_x = sort_by_x[i - 1]
        before_by_y = sort_by_y[i - 1].copy()
        before_by_y.reverse()
    current_by_x = sort_by_x[i]
    current_by_y = sort_by_y[i].copy()
    current_by_y.reverse()
    if i < len(sort_by_x) - 1:
        next_by_x = sort_by_x[i + 1]
        next_by_y = sort_by_y[i + 1].copy()
        next_by_y.reverse()
    """
    if G.get(pos2id[current_by_x]) is None:
        G[pos2id[current_by_x]] = []
    if G.get(pos2id[current_by_y.reverse()]) is None:
        G[pos2id[current_by_y.reverse()]] = []
    """
    if i < len(sort_by_x) - 1:
        G.append((abs(current_by_x[0] - next_by_x[0]),current_by_x, next_by_x))
        G.append((abs(current_by_y[1] - next_by_y[1]), current_by_y, next_by_y))
    if i > 0:
        G.append((abs(current_by_x[0] - before_by_x[0]), current_by_x, before_by_x))
        G.append((abs(current_by_y[1] - before_by_y[1]), current_by_y, before_by_y))
G.sort(key=lambda x:x[0])
sum_cost = 0
par = [i for i in range(N)]
rank = [1 for i in range(N)]
def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
import heapq
N = int(input())
city_ls = list()
for i in range(N):
    city_ls.append([int(i) for i in sys.stdin.readline().split()])
sort_by_x = sorted([[i, j] for i,j in city_ls], key=lambda x:x[0])
sort_by_y = sorted([[j, i] for i,j in city_ls], key=lambda x:x[0])
G = []
id2pos = {i : tuple(j) for i, j in enumerate(city_ls)}
pos2id = {j : i for i, j in id2pos.items()}
for i in range(len(sort_by_x)):
    if i > 0:
        before_by_x = sort_by_x[i - 1]
        before_by_y = sort_by_y[i - 1].copy()
        before_by_y.reverse()
    current_by_x = sort_by_x[i]
    current_by_y = sort_by_y[i].copy()
    current_by_y.reverse()
    if i < len(sort_by_x) - 1:
        next_by_x = sort_by_x[i + 1]
        next_by_y = sort_by_y[i + 1].copy()
        next_by_y.reverse()
    """
    if G.get(pos2id[current_by_x]) is None:
        G[pos2id[current_by_x]] = []
    if G.get(pos2id[current_by_y.reverse()]) is None:
        G[pos2id[current_by_y.reverse()]] = []
    """
    if i < len(sort_by_x) - 1:
        G.append((abs(current_by_x[0] - next_by_x[0]),current_by_x, next_by_x))
        G.append((abs(current_by_y[1] - next_by_y[1]), current_by_y, next_by_y))
    if i > 0:
        G.append((abs(current_by_x[0] - before_by_x[0]), current_by_x, before_by_x))
        G.append((abs(current_by_y[1] - before_by_y[1]), current_by_y, before_by_y))
heapq.heapify(G)

sum_cost = 0
par = [i for i in range(N)]
rank = [1 for i in range(N)]
def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

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

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

while len(G) > 0:
    (cost, _from, _to) = heapq.heappop(G)
    _from = pos2id[tuple(_from)]
    _to = pos2id[tuple(_to)]
    if is_same(_from, _to):
        continue
    unite(_from, _to)
    sum_cost += cost
print(sum_cost)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import heapq
N = int(input())
city_ls = list()
for i in range(N):
    city_ls.append([int(i) for i in input().split()])
sort_by_x = sorted(city_ls, key=lambda x:x[0])
sort_by_y = sorted([[j,i] for i,j in city_ls], key=lambda x:x[0])
yet_ls = city_ls
cost = 0
current = city_ls[0]
yet_ls.remove(current)
candidate_set = set()
candidate_que = list()
while len(yet_ls) > 0:
    sort_by_x.remove(current)
    sort_by_y.remove([current[1], current[0]])
    point_by_x = bisect.bisect_left(sort_by_x, current)
    point_by_y = bisect.bisect_left(sort_by_y, [current[1], current[0]])
    if point_by_x == 0:
        x_candi = [sort_by_x[0]]
    elif point_by_x == len(sort_by_x):
        x_candi = [sort_by_x[-1]]
    else:
        x_candi = [sort_by_x[point_by_x - 1], sort_by_x[point_by_x]]
    if point_by_y == 0:
        y_candi = [sort_by_y[0]]
    elif point_by_y == len(sort_by_y):
        y_candi = [sort_by_y[-1]]
    else:
        y_candi = [sort_by_y[point_by_y - 1], sort_by_y[point_by_y]]
    y_candi = [[j,i] for i,j in y_candi]
    for candi in x_candi + y_candi:
        if candi not in yet_ls:
            continue
        hoge = [abs(current[0] - candi[0]), abs(current[1] - candi[1])]
        dis = min(hoge)
        heapq.heappush(candidate_que, [dis] + candi)
        candidate_set.add(tuple(candi))
    while True:
        best = heapq.heappop(candidate_que)
        if best[1:] in yet_ls:
            break
        if len(candidate_que) == 0:
            print("error")
            break
    candidate_set.remove(tuple(best[1:]))
    cost += best[0]
    current = best[1:]
    yet_ls.remove(current)
print(cost)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from collections import defaultdict


class UnionFindTree():
    def __init__(self):
        self.__parent_of = defaultdict(lambda: None)
        self.__rank_of = defaultdict(lambda: 0)
        self.__size = defaultdict(lambda: 1)

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

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

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

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


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


class UnionFindTree():
    def __init__(self, values=[]):
        self.__parent_of = {}
        self.__rank_of = {}
        self.__size = {}
        for value in values:
            self.add(value)

    def add(self, value):
        if value in self.__parent_of:
            raise RuntimeError("Dupulicated Value Added")
        self.__parent_of[value] = None
        self.__rank_of[value] = 0
        self.__size[value] = 1

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

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

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

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

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


def main():
    N = int(input())
    X = [None] * N
    Y = [None] * N
    for i in range(N):
        x, y = map(int, input().split())
        X[i] = (x, i)
        Y[i] = (y, i)
    X.sort(key=itemgetter(0))
    Y.sort(key=itemgetter(0))
    adjx = [None] * (N-1)
    adjy = [None] * (N-1)
    for i in range(N-1):
        adjx[i] = (X[i+1][0] - X[i][0], X[i][1], X[i+1][1])
        adjy[i] = (Y[i+1][0] - Y[i][0], Y[i][1], Y[i+1][1])
    adjx.sort(key=itemgetter(0))
    adjy.sort(key=itemgetter(0))
    adjx += [(float("inf"), 0, 0)]
    adjy += [(float("inf"), 0, 0)]
    uft = UnionFindTree(range(N))
    ans = 0
    xi = 0
    yi = 0
    while xi < len(adjx)-1 or yi < len(adjy)-1:
        if adjx[xi][0] <= adjy[yi][0]:
            cost, a, b = adjx[xi]
            xi += 1
        else:
            cost, a, b = adjy[yi]
            yi += 1
        if not uft.is_same(a, b):
            uft.unite(a, b)
            ans += cost
        if uft.size(a) == N:
            break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


class UnionFindTree():
    def __init__(self, values=[]):
        self.__parent_of = {}
        self.__rank_of = {}
        self.__size = {}
        for value in values:
            self.add(value)

    def add(self, value):
        if value in self.__parent_of:
            raise RuntimeError("Dupulicated Value Added")
        self.__parent_of[value] = None
        self.__rank_of[value] = 0
        self.__size[value] = 1

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

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

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

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

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


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFindTree():
    def __init__(self, values=[]):
        self.__parent_of = {}
        self.__rank_of = {}
        self.__size = {}
        for value in values:
            self.add(value)

    def add(self, value):
        if value in self.__parent_of:
            raise RuntimeError("Dupulicated Value Added")
        self.__parent_of[value] = None
        self.__rank_of[value] = 0
        self.__size[value] = 1

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

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

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

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

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


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFindTree():
    def __init__(self, values=[]):
        self.__parent_of = {}
        self.__rank_of = {}
        self.__size = {}
        for value in values:
            self.add(value)

    def add(self, value):
        if value in self.__parent_of:
            raise RuntimeError("Dupulicated Value Added")
        self.__parent_of[value] = None
        self.__rank_of[value] = 0
        self.__size[value] = 1

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

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

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

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

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


def main():
    N = int(input())
    X = []
    Y = []
    for i in range(N):
        x, y = map(int, input().split())
        X += [(x, i)]
        Y += [(y, i)]
    X.sort()
    Y.sort()
    adjx = []
    adjy = []
    for i in range(N-1):
        adjx += [(X[i+1][0] - X[i][0], X[i][1], X[i+1][1])]
        adjy += [(Y[i+1][0] - Y[i][0], Y[i][1], Y[i+1][1])]
    adjx.sort()
    adjy.sort()
    adjx += [(float("inf"), 0, 0)]
    adjy += [(float("inf"), 0, 0)]
    uft = UnionFindTree(range(N))
    ans = 0
    xi = 0
    yi = 0
    while xi < len(adjx)-1 or yi < len(adjy)-1:
        if adjx[xi][0] <= adjy[yi][0]:
            cost, a, b = adjx[xi]
            xi += 1
        else:
            cost, a, b = adjy[yi]
            yi += 1
        if not uft.is_same(a, b):
            uft.unite(a, b)
            ans += cost
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFindTree():
    def __init__(self, values=[]):
        self.__parent_of = {}
        self.__rank_of = {}
        self.__size = {}
        for value in values:
            self.add(value)

    def add(self, value):
        if value in self.__parent_of:
            raise RuntimeError("Dupulicated Value Added")
        self.__parent_of[value] = None
        self.__rank_of[value] = 0
        self.__size[value] = 1

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

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

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

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

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


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFindTree():
    def __init__(self, values=[]):
        self.__parent_of = {}
        self.__rank_of = {}
        self.__size = {}
        for value in values:
            self.add(value)

    def add(self, value):
        if value in self.__parent_of:
            raise RuntimeError("Dupulicated Value Added")
        self.__parent_of[value] = None
        self.__rank_of[value] = 0
        self.__size[value] = 1

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

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

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

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

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


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFindTree():
    def __init__(self, values=[]):
        self.__parent_of = {}
        self.__rank_of = {}
        self.__size = {}
        for value in values:
            self.add(value)

    def add(self, value):
        if value in self.__parent_of:
            raise RuntimeError("Dupulicated Value Added")
        self.__parent_of[value] = None
        self.__rank_of[value] = 0
        self.__size[value] = 1

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

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

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

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

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


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C

#D
def root(x):
    if x == par[x]:
        return x
    par[x] = root(par[x])
    return par[x]

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

def unite(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
n = I()
v = LIR(n)
l = []
for i in range(n):
    v[i].append(i)
par = [i for i in range(n)]
rank = [0 for i in range(n)]
v.sort(key = lambda x:x[0])
for i in range(n-1):
    l.append([v[i][2],v[i+1][2],v[i+1][0]-v[i][0]])
v.sort(key = lambda x:x[1])
for i in range(n-1):
    l.append([v[i][2],v[i+1][2],v[i+1][1]-v[i][1]])
l.sort(key = lambda x:x[2])
k = 0
ans = 0
while k != n-1:
    x,y,c = l.pop(0)
    if not same(x,y):
        k += 1
        ans += c
        unite(x,y)
print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Time Limit Exceeded

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

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

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

N = int(input())
# minimum spanning tree
res = 0
pos = []
for i in range(N):
    p = tuple(int(x) for x in input().split())
    p = (p[0], p[1], i)
    pos.append(p)
x_order = sorted(pos)
y_order = sorted(pos, key=lambda x: x[1])

uf = UnionFind(N)
x_i = y_i = 0
num_edge = 0

edge = []
for i in range(len(x_order) - 1):
    v1 = x_order[i+1]
    v2 = x_order[i]
    edge.append((v1[0] - v2[0], v1[2], v2[2]))
    v1 = y_order[i+1]
    v2 = y_order[i]
    edge.append((v1[1] - v2[1], v1[2], v2[2]))

edge.sort()

while num_edge < N-1:
    e = edge.pop(0)
    if uf.same_check(e[1], e[2]):
        continue
    else:
        res += e[0]
        uf.union(e[1], e[2])
        num_edge += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
n = int(input())
x =[]
y =[]
info = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  x.append([i,info[i][0]])
  y.append([i,info[i][1]])

x = sorted(x,key=itemgetter(1))
y = sorted(y,key=itemgetter(1))
tree = []
#for i in range(n):
#  if i==0:
#    tree[x[i][0]].append([x[i+1][0],abs(x[i][1]-x[i+1][1])])
#    tree[y[i][0]].append([y[i+1][0],abs(y[i][1]-y[i+1][1])])
#  elif i==n-1:
#    tree[x[i][0]].append([x[i-1][0],abs(x[i][1]-x[i-1][1])])
#    tree[y[i][0]].append([y[i-1][0],abs(y[i][1]-y[i-1][1])])
#  else:
#    tree[x[i][0]].append([x[i+1][0],abs(x[i][1]-x[i+1][1])])
#    tree[x[i][0]].append([x[i-1][0],abs(x[i][1]-x[i-1][1])])
#    tree[y[i][0]].append([y[i+1][0],abs(y[i][1]-y[i+1][1])])
#    tree[y[i][0]].append([y[i-1][0],abs(y[i][1]-y[i-1][1])])
    
for i in range(n-1):
    tree.append([x[i][0],x[i+1][0],abs(x[i][1]-x[i+1][1])])
    tree.append([y[i][0],y[i+1][0],abs(y[i][1]-y[i+1][1])])

#UnionFindクラス
class UnionFind(object):

  def __init__(self, n=1):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ 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]
  
  # xとyの根を結合させる
  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.par[y] = x
  
  # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
  def is_same(self, x, y):
    return self.find(x) == self.find(y)

uf = UnionFind(len(tree))
tree = sorted(tree,key=itemgetter(2))
ans = 0

for i in range(len(tree)):
  if not uf.is_same(tree[i][0],tree[i][1]):
    uf.union(tree[i][0],tree[i][1])
    ans +=tree[i][2]
print(ans)