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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
 
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7
 
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
 
 
class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]
 
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]
 
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False
 
    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a
 
def main():
    N = I()
    a = []
    b = []
    for i in range(N):
        x,y = LI()
        a.append((x,i))
        b.append((y,i))
    a.sort()
    b.sort()
    t = []
    for i in range(1,N):
        t.append((a[i][0]-a[i-1][0], a[i][1], a[i-1][1]))
        t.append((b[i][0]-b[i-1][0], b[i][1], b[i-1][1]))
    t.sort()
    r = 0
    uf = UnionFind(N)
    for c,d,e in t:
        if uf.union(d,e):
            r += c
 
    return r
 
print(main())

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

n = int(input())
x_loc, y_loc = [], []
for i in range(n):
    x, y = map(int, input().split())
    x_loc.append((x, i))
    y_loc.append((y, i))
x_loc.sort()
y_loc.sort()
links = [set() for _ in range(n)]
for (x1, i1), (x2, i2) in zip(x_loc, x_loc[1:]):
    dist = abs(x1 - x2)
    links[i1].add((dist, i2))
    links[i2].add((dist, i1))
for (y1, i1), (y2, i2) in zip(y_loc, y_loc[1:]):
    dist = abs(y1 - y2)
    links[i1].add((dist, i2))
    links[i2].add((dist, i1))

visited = {0}
queue = list(links[0])
heapify(queue)
total = 0
while True:
    cost, i = heappop(queue)
    if i in visited:
        continue
    visited.add(i)
    total += cost
    if len(visited) == n:
        break
    for cost2, j in links[i]:
        if j in visited:
            continue
        heappush(queue, (cost2, j))
print(total)

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.parents = list(range(size))

    def find(self, i):
        ret = i
        path = []
        while self.parents[ret]!=ret:
            path.append(ret)
            ret = self.parents[ret]
        for p in path:
            self.parents[p] = ret
        return ret

    def union(self, i, j):
        self.parents[self.find(i)] = j

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

sortx = sorted(xys, key=lambda xy: xy[0][0])
roadsx = [(sortx[i][0][0]-sortx[i-1][0][0], sortx[i][1], sortx[i-1][1]) for i in range(1, n)]
sorty = sorted(xys, key=lambda xy: xy[0][1])
roadsy = [(sorty[i][0][1]-sorty[i-1][0][1], sorty[i][1], sorty[i-1][1]) for i in range(1, n)]
roads = roadsx + roadsy
roads.sort(key=lambda x:x[0])

ctr = 1
ans = 0
uf = UnionFind(n)
for road in roads:
    if ctr >= n:
        break
    cost, i1, i2 = road
    if uf.find(i1) != uf.find(i2):
        ans += cost
        ctr += 1
        uf.union(i1, i2)

print(ans)

Solution (Python):
A=range(input())
P=[map(int,raw_input().split())+[i]for i in A]
o=sorted
def r(x):
 if A[x]<x:A[x]=x=r(A[x])
 return x
def u((w,X)):x,y=o(map(r,X));A[y]=x;return(x<y)*w
def s(i):P.sort(key=lambda x:x[i]);return[(q[i]-p[i],(q[2],p[2]))for p,q in zip(P,P[1:])]
print sum(map(u,o(s(0)+s(1))))

Solution (Python):
n = input()
R = range(n)
P = [map(int,raw_input().split())+[i]for i in R]

a = range(n)
def root(x):
    if x != a[x]:a[x]=x=root(a[x])
    return x
def unite(x, y):
    x=root(x);y=root(y)
    a[max(x,y)]=min(x,y)
Q=[]
def s(i):
    P.sort(key=lambda x:x[i])
    for j in R[:-1]:
        Q.append((P[j+1][i] - P[j][i], P[j][2], P[j+1][2]))
s(0);s(1);Q.sort()
ans = 0
for w,x,y in Q:
    if root(x)!=root(y):
        ans += w
        unite(x, y)
print ans

Solution (Python):

import numpy as np
N = int(input())
X = []
Y = []

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


X_s = np.argsort(np.array(X))
Y_s = np.argsort(np.array(Y))

edge_list = []
edge_weight = []
for i in range(N-1):
    edge_list.append([X_s[i], X_s[i+1]])
    edge_weight.append(X[X_s[i+1]] - X[X_s[i]])
    edge_list.append([Y_s[i], Y_s[i+1]])
    edge_weight.append(Y[Y_s[i+1]] - Y[Y_s[i]])
    

sel = np.argsort(np.array(edge_weight))


uf = np.arange(N)


res = 0
flg = np.zeros(N)

for s in sel:
    m, n = edge_list[s]
    
    gr_m = m
    gr_m_list = []
    gr_n = n
    gr_n_list = []
    while gr_m != uf[gr_m]:
        gr_m_list.append(gr_m)
        gr_m = uf[gr_m]
    for m_ in gr_m_list:
        uf[m_] = gr_m
        
    while gr_n != uf[gr_n]:
        gr_n_list.append(gr_n)
        gr_n = uf[gr_n]
    for n_ in gr_n_list:
        uf[n_] = gr_n
        
    if gr_m == gr_n:
        pass
    else:
        res += edge_weight[s]
        uf[gr_n] = gr_m
print(res)

Solution (Python):


import array
import collections
import heapq
import itertools


AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
Town = collections.namedtuple("Town", "idx x y")
INF = 2 ** 31 - 1
NO_VERTEX = -1



def compute_mst_prim(max_v, adj_list):
    
    pred = [NO_VERTEX for _ in range(max_v)]
    
    key = [INF for _ in range(max_v)]
    key[0] = 0
    
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)


def solve(n, towns):
    txs = sorted(towns, key=lambda t: t.x)
    tys = sorted(towns, key=lambda t: t.y)
    adj_list = [set() for _ in range(n)]
    g = itertools.chain(zip(txs[:-1], txs[1:]), zip(tys[:-1], tys[1:]))
    for t1, t2 in g:
        cost = min(abs(t1.x - t2.x), abs(t1.y - t2.y))
        adj_list[t1.idx].add(AdjacentVertex(t2.idx, cost))
        adj_list[t2.idx].add(AdjacentVertex(t1.idx, cost))
    (_, key) = compute_mst_prim(n, adj_list)
    return sum(key)


def main():
    n = int(input())
    towns = [Town(idx, *(int(z) for z in input().split())) for idx in range(n)]
    res = solve(n, towns)
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):

import array, bisect, collections, copy, heapq, itertools, math, random, re, string, sys, time

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())
def ILI(): return list(map(int, input().split()))
def IAI(LINE): return [ILI() for __ in range(LINE)]
def IDI(): return {key: value for key, value in ILI()}


def read():
    N = II()
    x, y = [], []
    for i in range(N):
        _x, _y = ILI()
        x.append((i, _x))
        y.append((i, _y))
    return N, x, y


class UnionFind(object):
    def __init__(self, number_of_nodes):  
        self.par = array.array("L", range(number_of_nodes))
        self.rank = array.array("L", (0 for i in range(number_of_nodes)))

    def root(self, node):  
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r  
            return r

    def in_the_same_set(self, node1, node2):  
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):  
        x = self.root(node1)
        y = self.root(node2)
        if x == y:
            pass
        elif 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 solve(N, x, y):
    edges = []
    x.sort(key=lambda x: x[1])
    y.sort(key=lambda x: x[1])
    for i in range(N - 1):
        x_s, x_e = x[i], x[i + 1]
        y_s, y_e = y[i], y[i + 1]
        edges.append((x_s[0], x_e[0], x_e[1] - x_s[1]))
        edges.append((y_s[0], y_e[0], y_e[1] - y_s[1]))

    edges.sort(key=lambda x: x[2])
    union_find = UnionFind(N)
    ans = 0
    for edge in edges:
        if not union_find.in_the_same_set(edge[0], edge[1]):
            union_find.unite(edge[0], edge[1])
            ans += edge[2]

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

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

p.sort()
q.sort()
pid = [0 for i in range(n)]
qid = [0 for i in range(n)]
for i in range(n):
    pid[p[i][2]] = i
    qid[q[i][2]] = i
used = [False] * n

total = 0

hq = [(0, 0)]
cnt = 0
s = set()
while hq and cnt < n:
    c, i = heapq.heappop(hq)
    
    if i not in s:
        cnt += 1
        s.add(i)
        total += c
    else:
        continue
    pi = pid[i]
    qi = qid[i]
    if pi > 0 and p[pi-1][2] not in s:
        heapq.heappush(hq, (p[pi][0] - p[pi-1][0], p[pi-1][2]))
    if pi < n-1 and p[pi+1][2] not in s:
        heapq.heappush(hq, (p[pi+1][0] - p[pi][0], p[pi+1][2]))
    if qi > 0 and q[qi-1][2] not in s:
        heapq.heappush(hq, (q[qi][0] - q[qi-1][0], q[qi-1][2]))
    if qi < n-1 and q[qi+1][2] not in s:
        heapq.heappush(hq, (q[qi+1][0] - q[qi][0], q[qi+1][2]))
    
        

print(total)

Solution (Python):
import operator
import sys
import heapq




def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def link(x, y):
    if rank[x] > rank[y]:
        p[y] = x
    else:
        p[x] = y
        if rank[x] == rank[y]:
            rank[y] = rank[x] + 1


def _union(x, y):
    link(find_set(x), find_set(y))


def find_set(x):
    if x != p[x]:
        p[x] = find_set(p[x])
    return p[x]


def dist(j, k):
    return min(abs(pairs[j][0] - pairs[k][0]), abs(pairs[j][1] - pairs[k][1]))


n = read_int()
pairs = [read_int_list() for i in range(n)]

p = list(range(n))
rank = [0] * n

edges = []

for pos in range(2):
    indices = list(range(n))
    indices.sort(key=lambda u: pairs[u][pos])
    for i in range(1, n):
        j = indices[i - 1]
        k = indices[i]
        w = dist(j, k)
        heapq.heappush(edges, (w, j, k))

res = 0
while edges:
    edge = heapq.heappop(edges)
    w, j, k = edge
    if find_set(j) != find_set(k):
        res += w
        _union(j, k)

print(res)

Solution (Python):
class UnionFind:
    def __init__(self,size):
        self.parent=range(size)
        self.tree_num=size
        self.tree_w=[1]*size
        self.rank=[0]*size

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

    def unite(self,x,y):
        x=self.findset(x)
        y=self.findset(y)
        if x==y:
            return
        if self.rank[x]<self.rank[y]:
            self.parent[x]=y
            self.tree_num-=1
            self.tree_w[y]+=self.tree_w[x]
        else:
            self.parent[y]=x
            self.tree_num-=1
            self.tree_w[x]+=self.tree_w[y]
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

    def same(self,x,y):
        if self.findset(x)==self.findset(y):
            return True
        else:
            return False

    def tree_number(self):
        return self.tree_num

    def tree_weight(self,x):
        return self.tree_w[self.findset(x)]
n=int(raw_input())
xy=[]
yx=[]
for i in xrange(n):
    x, y = map(int,raw_input().split())
    xy.append([x,y,i])
    yx.append([y,x,i])
xy.sort()
yx.sort()
dist=[]
for i in xrange(n-1):
    a,b,idx1=xy[i]
    c,d,idx2=xy[i+1]
    dist.append([min(abs(a-c),abs(b-d)),idx1,idx2])
for i in xrange(n-1):
    a,b,idx1=yx[i]
    c,d,idx2=yx[i+1]
    dist.append([min(abs(a-c),abs(b-d)),idx1,idx2])
dist.sort()
uf=UnionFind(n)
ans=0
for i in xrange(2*(n-1)):
    d,idx1,idx2=dist[i]
    if uf.same(idx1,idx2):continue
    uf.unite(idx1,idx2)
    ans+=d
print ans

Solution (Python):
import numpy as np 

class union_find:
	def __init__(self, size):
		
		
		self.size=size
		self.table = [-(i+1) for i in range(size)]
		self.num=[0 for i in range(size)]

	
	def find(self, x):
		if self.table[x] < 0:
			self.size+=-1
			return(x)
		else:
			
			self.table[x] = self.find(self.table[x])
			return(self.table[x])

	
	def unite(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] <= self.table[s2]:
				
				self.table[s1] += self.table[s2]
				self.table[s2] = s1
			else:
				self.table[s2] += self.table[s1]
				self.table[s1] = s2
			return(True)
		return(False)

	
	def same(self, x, y):
		if self.find(x)==self.find(y):
			return(True)
		else:
			return(False)

	
	def definite(self):
		for i in range(self.size):
			self.num[i]=self.find(i)
		return(True)


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

edge = []

argxl = np.argsort(xl)
argyl = np.argsort(yl)
soxl = np.sort(xl)
soyl = np.sort(yl)

for i in range(N-1):
	edge.append((soxl[i+1]-soxl[i], argxl[i], argxl[i+1]))
	edge.append((soyl[i+1]-soyl[i], argyl[i], argyl[i+1]))

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

uni = union_find(N)
res = 0
for dis, i, j in edge:
	if not uni.same(i,j):
		uni.unite(i,j)
		res += dis

print(res)

Solution (Python):
class DisjointSet(object):
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.num = n  

    def union(self, x, y):
        self._link(self.find_set(x), self.find_set(y))

    def _link(self, x, y):
        if x == y:
            return
        self.num -= 1
        if self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

def read_data():
    N = int(input())
    xs = []
    ys = []
    for i in range(N):
        x, y = map(int, input().split())
        xs.append((x, i))
        ys.append((y, i))
    return N, xs, ys

def add_edges(xs):
    es = []
    prev_x, prev_i = xs[0]
    for x, i in xs[1:]:
        es.append((x - prev_x, prev_i, i))
        prev_x = x
        prev_i = i
    return es

def solve(N, xs, ys):
    xs.sort()
    ys.sort()
    es = add_edges(xs)
    es.extend(add_edges(ys))
    es.sort()
    ds = DisjointSet(N)
    cost = 0
    for d, i, j in es:
        if ds.find_set(i) == ds.find_set(j):
            continue
        ds.union(i, j)
        cost += d
    return cost

N, xs, ys = read_data()
print(solve(N, xs, ys))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


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

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    N = I()
    a = []
    b = []
    for i in range(N):
        x,y = LI()
        a.append((x,i))
        b.append((y,i))
    a.sort()
    b.sort()
    t = []
    for i in range(1,N):
        t.append((a[i][0]-a[i-1][0], a[i][1], a[i-1][1]))
        t.append((b[i][0]-b[i-1][0], b[i][1], b[i-1][1]))
    t.sort()
    r = 0
    uf = UnionFind(N)
    for c,d,e in t:
        if uf.union(d,e):
            r += c

    return r

print(main())