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 sys
sys.setrecursionlimit(1000000)

N = int(input())

P = [n for n in range(N)]
points = []

def root(a):
  if P[a] == a:
    return a
  P[a] = root(P[a])
  return P[a]

def is_same_set(a, b):
  return root(a) == root(b)

def unite(a, b):
  P[root(a)] = root(b)


for i in range(N):
  x, y = [int(n) for n in input().split()]
  points.append((i, x, y))

xs = sorted([(x, i) for i, x, y in points], key=lambda p: p[0])
xedges = [(xs[n][1], xs[n+1][1], xs[n+1][0]-xs[n][0] ) for n in range(N-1)]
ys = sorted([(y, i) for i, x, y in points], key=lambda p:p[0])
yedges = [(ys[n][1], ys[n+1][1], ys[n+1][0]-ys[n][0]) for n in range(N-1)]

edges = xedges + yedges
edges.sort(key=lambda x: x[2])
res = 0
for edge in edges:
  i, j, cost = edge
  if not is_same_set(i, j):
    unite(i, j)
    res += cost

print(res)

Solution (Python):

"""
http://abc065.contest.atcoder.jp/tasks/arc076_b
TLE
"""
import sys
from sys import stdin
input = stdin.readline
from collections import namedtuple


class DisjointSet(object):
    def __init__(self, size):
        self.rank = []
        self.p = []
        for i in range(size):
            self.makeSet(i)

    def makeSet(self, x):
        self.p.insert(x, x)
        self.rank.insert(x, 0)

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

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

    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]


def kruskal(V, E, es):
    es.sort(key=lambda x: x.c)
    uf = DisjointSet(V)
    res = 0

    for i in range(E):
        e = es[i]
        if not uf.same(e.u, e.v):
            uf.unite(e.u, e.v)
            res += e.c
    return res


edge = namedtuple('edge', ['u', 'v', 'c'])
def main(args):
    N = int(input())
    cities = []
    for i in range(1, N+1):
        x, y = map(int, input().split())
        cities.append([x, y, i])

    es = []
    cities.sort(key=lambda x: x[0])
    prev_x, _, prev_i = cities[0]
    for x, y, i in cities[1:]:
        es.append(edge(prev_i, i, x - prev_x))

        prev_x = x
        prev_i = i

    cities.sort(key=lambda x: x[1])
    _, prev_y, prev_i = cities[0]
    for x, y, i in cities[1:]:
        es.append(edge(prev_i, i, y - prev_y))

        prev_y = y
        prev_i = i

    result = kruskal(N+1, len(es), es)
    print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
N = int(input())

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


adj = [[] for i in range(N)]
for xy in [1, 2]:
    towns.sort(key=lambda t: t[xy])
    for i in range(N - 1):
        t1 = towns[i][0]
        t2 = towns[i + 1][0]
        cost = towns[i + 1][xy] - towns[i][xy]
        adj[t1].append((t2, cost))
        adj[t2].append((t1, cost))


import heapq
pq = []
heapq.heappush(pq, (0, 0))

done = set()
ans = 0
while pq:
    cost, v_now = heapq.heappop(pq)

    if v_now in done:
        continue

    ans += cost
    done.add(v_now)

    if len(done) == N:
        break

    for v, c in adj[v_now]:
        if v not in done:
            heapq.heappush(pq, (c, v))

print(ans)

Solution (Python):
N = int(input())

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


edges = []
for xy in [1, 2]:
    towns.sort(key=lambda t: t[xy])
    for i in range(N - 1):
        edges.append((towns[i + 1][xy] - towns[i][xy], towns[i][0], towns[i + 1][0]))


edges.sort()


parent = [i for i in range(N)]
rank = [0 for i in range(N)]

def find(v):
    if parent[v] != v:
        parent[v] = find(parent[v])
    return parent[v]

def union(a, b):
    rootA = find(a)
    rootB = find(b)

    if rootA == rootB:
        return
    if rank[rootA] < rank[rootB]:
        parent[rootA] = rootB
    else:
        parent[rootB] = rootA
        if rank[rootA] == rank[rootB]:
            rank[rootA] += 1


numTree = N
ans = 0
for cost, v1, v2 in edges:

    if find(v1) != find(v2):
        union(v1, v2)
        ans += cost
        numTree -= 1

    if numTree == 1:
        break

print(ans)

Solution (Python):
from collections import deque

n = int(input())
uni = list(range(n))
cityx = [None] * n
cityy = [None] * n
for i in range(n):
    x, y = map(int, input().split())
    cityx[i] = (x, i)
    cityy[i] = (y, i)

cityx.sort()
cityy.sort()
dcx, dcy = [], []
for i in range(n - 1):
    dcx.append((cityx[i+1][0] - cityx[i][0], (cityx[i][1], cityx[i+1][1])))
    dcy.append((cityy[i+1][0] - cityy[i][0], (cityy[i][1], cityy[i+1][1])))

dqx = deque(sorted(dcx))
dqy = deque(sorted(dcy))

def root(a):
    if(a == uni[a]):
        return a
    uni[a] = root(uni[a])
    return uni[a]

def connect(a, b):
    a = root(a)
    b = root(b)
    uni[b] = a

ans = 0
while dqx or dqy:
    if(dqx and (not dqy or dqx[0] < dqy[0])):
        d, (i, j) = dqx.popleft()
    else:
        d, (i, j) = dqy.popleft()
    if(root(i) != root(j)):
        ans += d
        connect(i, j)

print(ans)

Solution (Python):
from operator import itemgetter
from queue import deque

N = int(input())

xin = []
yin = []

for _ in range(N):
    x, y = map(int, input().split())
    xin.append(x)
    yin.append(y)
    
xin = sorted(list(enumerate(xin)), key=itemgetter(1))
yin = sorted(list(enumerate(yin)), key=itemgetter(1))

xd = []
yd = []

for i in range(N-1):
    xd.append((xin[i+1][1] - xin[i][1], (xin[i][0], xin[i+1][0])))
    yd.append((yin[i+1][1] - yin[i][1], (yin[i][0], yin[i+1][0])))
    
xdq = deque(sorted(xd))
ydq = deque(sorted(yd))

par = list(range(N))

def find(x):
    if x == par[x]:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
    
def union(x, y):
    px, py = find(x), find(y)
    if px != py:
        par[py] = px
    
ans = 0

while xdq or ydq:
    if xdq and (not ydq or xdq[0] < ydq[0]):
        d, (i, j) = xdq.popleft()
    else:
        d, (i, j) = ydq.popleft()
        
    if find(i) != find(j):
        ans += d
        union(i, j)
        
print(ans)

Solution (Python):
from operator import itemgetter
from collections import deque

N = int(input())

xs, ys = [], []
for _ in range(N):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)
    
xis = sorted(list(enumerate(xs)), key = itemgetter(1))
yis = sorted(list(enumerate(ys)), key = itemgetter(1))

xds, yds = [], []
for i in range(N-1):
    xds.append((xis[i+1][1] - xis[i][1], (xis[i][0], xis[i+1][0])))
    yds.append((yis[i+1][1] - yis[i][1], (yis[i][0], yis[i+1][0])))

xdq, ydq = deque(sorted(xds)), deque(sorted(yds))

par = list(range(N))
def find(x):
    if x == par[x]: 
        return x 
    else:
        par[x] = find(par[x])
        return par[x]

def union(x,y):
    rx, ry = find(x), find(y)
    par[ry] = rx

ans = 0
while xdq or ydq:
    if xdq and (not ydq or xdq[0] < ydq[0]):
        d, (i,j) = xdq.popleft()
    else:
        d, (i,j) = ydq.popleft()
    if find(i) != find(j): 
        ans += d
        union(i,j)

print(ans)

Solution (Python):
N = int(input())
xs, ys = [], []
for _ in range(N):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)

from operator import itemgetter
xis = sorted(list(enumerate(xs)), key=itemgetter(1))
yis = sorted(list(enumerate(ys)), key=itemgetter(1))

xds, yds = [], []
for i in range(N - 1):
    xds.append((xis[i + 1][1] - xis[i][1], (xis[i][0], xis[i + 1][0])))
    yds.append((yis[i + 1][1] - yis[i][1], (yis[i][0], yis[i + 1][0])))

from collections import deque
xdq, ydq = deque(sorted(xds)), deque(sorted(yds))

par = list(range(N))
def find(x):
    if x == par[x]:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def union(x, y):
    rx, ry = find(x), find(y)
    par[ry] = rx

ans = 0
while xdq or ydq:
    if xdq and (not ydq or xdq[0] < ydq[0]):
        d, (i, j) = xdq.popleft()
    else:
        d, (i, j) = ydq.popleft()
    if find(i) != find(j):
        ans += d
        union(i, j)

print(ans)

Solution (Python):
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 cal(d,xl):
    N=len(xl)
    for i in range(N-1):
        r1=abs(xl[i+1][0]-xl[i][0])
        try:
            l=d[r1]
            l.append([xl[i+1][1],xl[i][1]])
            d[r1]=l
        except:
            d[r1]=[[xl[i+1][1],xl[i][1]]]
    return d
N=int(input())
x=[[0,0] for _ in range(N)]
y=[[0,0] for _ in range(N)]
for i in range(N):
    x[i][0],y[i][0]=list(map(int,input().split()))
    x[i][1],y[i][1]=i,i
x=sorted(x,key=lambda l: l[0])
y=sorted(y,key=lambda l: l[0])
a=cal(cal({},x),y)
p=UnionFind(N)
c=0
cost=0
edgecount=0
while True:
    if(edgecount==N-1):
        print(cost)
        break
    try:
        l=a[c]
        for item in l:
            if(p.union(item[0],item[1])):
                cost+=c
                edgecount+=1
            
        c+=1
    except:
        c+=1
        continue

Solution (Python):
import sys

import numpy as np


class Graph:
    def __init__(self, N):
        self.townarrow = [i for i in range(N)]

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

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

    def link(self, x, y):
        self.townarrow[y] = x


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

useful_road = []

l = sorted(range(N), key=lambda j: x[j])
for i in range(len(l) - 1):
    cost = min(abs(x[l[i]] - x[l[i + 1]]), abs(y[l[i]] - y[l[i + 1]]))
    useful_road.append((cost, l[i], l[i + 1]))

l = sorted(range(N), key=lambda j: y[j])
for i in range(len(l) - 1):
    cost = min(abs(x[l[i]] - x[l[i + 1]]), abs(y[l[i]] - y[l[i + 1]]))
    useful_road.append((cost, l[i], l[i + 1]))


m = 0
cost = 0
towngroup = Graph(N)
for c, i, j in sorted(useful_road):
    if towngroup.find(i) == towngroup.find(j):
        continue
    cost += c
    m += 1

    towngroup.union(i, j)

    if m == N - 1:
        print(cost)
        sys.exit()

Solution (Python):
class UnionFind3:
    def __init__(self, size):
        self.table = [-1 for _ in xrange(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
 
uf=UnionFind3(100001)
 
n = input()
cities = [map(int,raw_input().split(" "))+[i] for i in range(n)]
 
cities_x = sorted(cities, key=lambda a:a[0])
cities_y = sorted(cities, key=lambda a:a[1])
 
road = [[cities_x[i+1][0]-cities_x[i][0],cities_x[i][2],cities_x[i+1][2]] for i in range(n-1)]
road +=[[cities_y[i+1][1]-cities_y[i][1],cities_y[i][2],cities_y[i+1][2]] for i in range(n-1)]
 
sum = 0
for (cost,i,j) in sorted(road):
    if(uf.find(i)!=uf.find(j)):
        uf.union(i,j)
        sum += cost
 
print sum

Solution (Python):
import sys




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


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


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


def read_str():
    return input()


p = []
rank = []


def make_set(x):
    p[x] = x
    rank[x] = 0


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


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


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


def solve():
    n = read_int()
    a = [read_int_list() for i in range(n)]
    global p, rank
    p = [0] * n
    rank = [0] * n

    for x in range(n):
        make_set(x)

    def get_cost(i, j):
        return min(abs(a[i][0] - a[j][0]), abs(a[i][1] - a[j][1]))

    roads = []
    for j in range(2):
        l = sorted(range(n), key=lambda i: a[i][j])
        for i in range(n - 1):
            cost = get_cost(l[i], l[i + 1])
            road = (cost, l[i], l[i + 1])
            roads.append(road)
    roads.sort()

    res = 0
    m = 0
    for road in roads:
        c, u, v = road
        if find_set(u) != find_set(v):
            res += c
            m += 1
            _union(u, v)
        if m == n - 1:
            break
    return res


def main():
    res = solve()
    print(res)


main()

Solution (Python):
import operator
import sys




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


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


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


def read_str():
    return input()


p = []
rank = []


def make_set(x):
    p[x] = x
    rank[x] = 0


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


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


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


def solve():
    n = read_int()
    a = [read_int_list() for i in range(n)]
    global p, rank
    p = [0] * n
    rank = [0] * n

    for x in range(n):
        make_set(x)

    def get_cost(i, j):
        return min(abs(a[i][0] - a[j][0]), abs(a[i][1] - a[j][1]))

    roads = []
    for j in range(2):
        l = sorted(range(n), key=lambda i: a[i][j])
        for i in range(n - 1):
            cost = get_cost(l[i], l[i + 1])
            road = (cost, l[i], l[i + 1])
            roads.append(road)
    roads.sort()

    res = 0
    for road in roads:
        c, u, v = road
        if find_set(u) != find_set(v):
            res += c
            _union(u, v)
    return res


def main():
    res = solve()
    print(res)


main()

Solution (Python):

import sys
sys.setrecursionlimit(int(2e9))

def distance(P, p1, p2):
    return min(abs(P[p1][1]-P[p2][1]), abs(P[p1][2]-P[p2][2]))
def root(CI, p):
    if CI[p] == p:
        return p
    else:
        CI[p] = root(CI, CI[p])
        return CI[p] 

N = int(input())
P = [[j]+[int(i) for i in input().split(' ')] for j in range(N)]
sortX = sorted(P,key=lambda x:x[1])
sortY = sorted(P,key=lambda x:x[2])
EX = [[sortX[i][0], sortX[i+1][0], distance(P,sortX[i][0],sortX[i+1][0])] for i in range(N-1)]
EY = [[sortY[i][0], sortY[i+1][0], distance(P,sortY[i][0],sortY[i+1][0])] for i in range(N-1)]
E = EX + EY
E = sorted(E, key=lambda x:x[2])
CI = [i for i in range(N)]
disSum = 0
for e in E:
    s,l = min(e[0],e[1]),max(e[0],e[1])



    if root(CI, s) != root(CI, l):
        CI[root(CI, l)] = root(CI, s)
        disSum += e[2]
print(disSum)

Solution (Python):
from collections import defaultdict
import operator

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

es = defaultdict(lambda: float('inf'))
for i in range(N-1):
    xd = xs[i+1][0] - xs[i][0]
    i1 = min(xs[i+1][1], xs[i][1])
    i2 = max(xs[i+1][1], xs[i][1])
    es[(i1,i2)] = min(es[(i1,i2)], xd)
    yd = ys[i+1][0] - ys[i][0]
    i3 = min(ys[i+1][1], ys[i][1])
    i4 = max(ys[i+1][1], ys[i][1])
    es[(i3,i4)] = min(es[(i3,i4)], yd)

parent = [i for i in range(N)]
def root(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = root(parent[a])
        return parent[a]
def is_same(a,b):
    return root(a) == root(b)
def unite(a,b):
    ra = root(a)
    rb = root(b)
    if ra == rb: return
    parent[ra] = rb;

value = 0
for k,v in sorted(es.items(), key=operator.itemgetter(1)):
    a,b = k
    if is_same(a,b): continue
    unite(a,b)
    value += v
print value

Solution (Python):
import sys
sys.setrecursionlimit(int(2e9))
class obj:
    def __init__(self, N):
        self.fa = [i for i in range(N)]
    def find(self, x):
        if x == self.fa[x]:
            return x
        else:
            self.fa[x] = self.find(self.fa[x])
            return self.fa[x]

N = int(input())
node = [{"x":0, "y":0, "id":i} for i in range(N)]
edge = [{"u":0, "v":0, "d":0} for i in range(2*(N-1))]
ob = obj(N)
for i in range(N):
    node[i]["x"], node[i]["y"] = map(int, input().split())
    node[i]["id"] = i

xnode = sorted(node, key=lambda x:x["x"])
for i in range(N-1):
    edge[i]["u"] = xnode[i]["id"]
    edge[i]["v"] = xnode[i+1]["id"]
    edge[i]["d"] = xnode[i+1]["x"] - xnode[i]["x"]
ynode = sorted(node, key=lambda x:x["y"])
for i in range(N-1):
    edge[i+N-1]["u"] = ynode[i]["id"]
    edge[i+N-1]["v"] = ynode[i+1]["id"]
    edge[i+N-1]["d"] = ynode[i+1]["y"] - ynode[i]["y"]
dedge = sorted(edge, key=lambda x:x["d"])
ans = 0
for i in range(2*(N-1)):
    if ob.find(dedge[i]["u"]) != ob.find(dedge[i]["v"]):
        ans += dedge[i]["d"]
        ob.fa[ob.fa[dedge[i]["u"]]] = ob.fa[dedge[i]["v"]]
print(ans)

Solution (Python):
class UnionFind3:
    def __init__(self, size):
        self.table = [-1 for _ in xrange(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

uf=UnionFind3(100001)

n = input()
cities = [map(int,raw_input().split(" "))+[i] for i in range(n)]

cities_x = sorted(cities, key=lambda a:a[0])
cities_y = sorted(cities, key=lambda a:a[1])

road = [[cities_x[i+1][0]-cities_x[i][0],cities_x[i][2],cities_x[i+1][2]] for i in range(n-1)]
road +=[[cities_y[i+1][1]-cities_y[i][1],cities_y[i][2],cities_y[i+1][2]] for i in range(n-1)]

sum = 0
for (cost,i,j) in sorted(road):
    if(uf.find(i)!=uf.find(j)):
        uf.union(i,j)
        sum += cost

print sum