Problem:
 Score : 600 points    Problem Statement There are N dots in a two-dimensional plane. The coordinates of the i -th dot are (x_i, y_i) .  We will repeat the following operation as long as possible:   Choose four integers a , b , c , d  (a \neq c, b \neq d) such that there are dots at exactly three of the positions (a, b) , (a, d) , (c, b) and (c, d) , and add a dot at the remaining position.   We can prove that we can only do this operation a finite number of times. Find the maximum number of times we can do the operation.      Constraints  1 \leq N \leq 10^5  1 \leq x_i, y_i \leq 10^5  If i \neq j , x_i \neq x_j or y_i \neq y_j .  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  x_1  y_1  :  x_N  y_N       Output Print the maximum number of times we can do the operation.        Sample Input 1 3
1 1
5 1
5 5      Sample Output 1 1  By choosing a = 1 , b = 1 , c = 5 , d = 5 , we can add a dot at (1, 5) . We cannot do the operation any more, so the maximum number of operations is 1 .       Sample Input 2 2
10 10
20 20      Sample Output 2 0  There are only two dots, so we cannot do the operation at all.       Sample Input 3 9
1 1
2 1
3 1
4 1
5 1
1 2
1 3
1 4
1 5      Sample Output 3 16  We can do the operation for all choices of the form a = 1 , b = 1 , c = i , d = j  (2 \leq i,j \leq 5) , and no more. Thus, the maximum number of operations is 16 .

Solution (Python):

from collections import defaultdict
from collections import deque
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] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    s = S()
    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            print("Bad")
            quit()
    print("Good")
    return


def B():
    n,l = LI()
    a = [i+l for i in range(n)]
    ans = sum(a)
    m = n+l-1
    for i in a[::-1]:
        if i < 0:break
        m = min(m,i)
    ans -= m
    print(ans)
    return


def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
def C():
    a,b,c,d = LI()
    g = gcd(c,d)
    l = c*d//g
    sc = b//c-(a-1)//c
    sd = b//d-(a-1)//d
    sl = b//l-(a-1)//l
    print(b-a+1-sc-sd+sl)
    return


def D():
    n = I()
    w = LIR(n)
    w.sort(key = lambda x: x[1])
    t = 0
    for a,b in w:
        if t+a > b:
            print("No")
            quit()
        t += a
    print("Yes")
    return


def E():
    n,k = LI()
    if k == 0:
        m = (n*(n-1))//2
        print(m)
        for i in range(1,n+1):
            for j in range(i+1,n+1):
                print(i,j)
    else:
        if k > ((n-1)*(n-2))//2:
            print(-1)
        else:
            ans = []
            for i in range(2,n+1):
                ans.append((1,i))
            m = ((n-1)*(n-2))//2
            for i in range(2,n+1):
                for j in range(i+1,n+1):
                    if m == k:break
                    ans.append((i,j))
                    m -= 1
                if m == k:break
            print(len(ans))
            for i,j in ans:
                print(i,j)
    return


def F():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]
    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 = defaultdict(list)
    h = defaultdict(list)
    par = defaultdict(int)
    rank = defaultdict(int)
    for i in range(n):
        a,b = LI()
        v[a].append(b)
        h[b].append(a)
        par[a] = a
        rank[a] = 0
    h = h.values()
    for l in h:
        for i in range(len(l)-1):
            x = l[i]
            y = l[i+1]
            if root(x) != root(y):
                unite(x,y)
    h = defaultdict(list)
    for i in par.keys():
        par[i] = root(par[i])
        h[par[i]].append(i)
    h = h.values()
    ans = 0
    for k in h:
        f = defaultdict(lambda : 0)
        l = []
        m = 0
        for i in k:
            for j in v[i]:
                if not f[j]:
                    m += 1
                    f[j] = 1
        for i in k:
            ans += m-len(v[i])
    print(ans)
    return


if __name__ == "__main__":
    F()

Solution (Python):

import sys
sys.setrecursionlimit(100000+10)


def add_edge(u, v):
	G[u].append(v)
	G[v].append(u)

def dfs(vertex, x_set, y_set):

	global visited

	if visited[vertex]:
		
		return 0
	visited[vertex] = True

	x_set.add(coords[vertex][1])
	y_set.add(coords[vertex][2])
	for v in G[vertex]:
		if visited[v]:
			
			pass
		else:
			dfs(v, x_set, y_set)

	return len(x_set)*len(y_set)

n = int(input())

G = [[] for _ in range(n)] 

visited = [False] * n
now_index = n-1

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

from operator import itemgetter


coords_xs = sorted(coords, key = itemgetter(1))
for i in range(n-1):
	if coords_xs[i][1] == coords_xs[i+1][1]: 
		
		add_edge(coords_xs[i][0], coords_xs[i+1][0])


coords_ys = sorted (coords, key = itemgetter(2))
for i in range(n-1):
	if coords_ys[i][2] == coords_ys[i+1][2]: 
		
		add_edge(coords_ys[i][0], coords_ys[i+1][0])


final = 0
for i in range(n):
	x_set = {coords[i][1]} 
	y_set = {coords[i][2]}
	final += dfs(i, x_set, y_set)

print(final - n)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
N = int(input())
K = 10**5+1
P = [i for i in range(K)]

def par(a):
    if P[a] == a:
        return a
    t = par(P[a])
    P[a] = t
    return t
def cb(a, b):
    P[par(b)] = par(a)

X = [[] for _ in range(K)]
Y = [[] for _ in range(K)]
for _ in range(N):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    Y[y-1].append(x-1)
for i in range(K):
    for j in range(len(Y[i])-1):
        cb(Y[i][j], Y[i][j+1])

M = [[] for _ in range(K)]
for i in range(K):
    M[par(i)].append(i)
ans = -N
for i in range(K):
    S = []
    for j in M[i]:
        for k in X[j]:
            S.append(k)
    S = list(set(S))
    ans += len(S)*len(M[i])
print(ans)

Solution (Python):
from collections import defaultdict
U = 10 ** 5
root = [None] * (2*U+1)
N = int(input())
XY = [[int(x) for x in input().split()] for _ in range(N)]

def find_root(x):
  y = root[x]
  if y is None:
    root[x] = x
    return x
  if x == y:
    return y
  z = find_root(y)
  root[x] = z
  return z

def merge(x,y):
  rx = find_root(x)
  ry = find_root(y)
  if rx == ry:
    return
  root[ry] = rx
  return

for x,y in XY:
  merge(x,U+y)

pts_cnt = defaultdict(int)
x_cnt = defaultdict(int)
y_cnt = defaultdict(int)

for x in range(U+1):
  if root[x] is None:
    continue
  x_cnt[find_root(x)] += 1

for y in range(U+1,U+U+1):
  if root[y] is None:
    continue
  y_cnt[find_root(y)] += 1

for x,y in XY:
  pts_cnt[find_root(x)] += 1

answer = 0
for k,v in pts_cnt.items():
  answer += x_cnt[k] * y_cnt[k] - v

print(answer)

Solution (Python):
import sys
input=sys.stdin.readline
from collections import defaultdict
class UnionFind:
    def __init__(self,n):
        self.par=[i for i in range(n)]
        self.rank=[0]*n
    def find(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        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())
uf=UnionFind(n)
XY=[tuple(map(int,input().split())) for _ in range(n)]
Xd=defaultdict(list)
Yd=defaultdict(list)
for i,(x,y) in enumerate(XY):
    Xd[x].append(i)
    Yd[y].append(i)
for x in Xd:
    i=Xd[x][0]
    for j in Xd[x]:
        uf.union(i,j)
for y in Yd:
    i=Yd[y][0]
    for j in Yd[y]:
        uf.union(i,j)
d=defaultdict(list)
for i in range(n):
    d[uf.find(i)].append(i)
ans=0
for k in d:
    Xs,Ys=set(),set()
    for i in d[k]:
        x,y=XY[i]
        Xs.add(x); Ys.add(y)
    ans+=len(Xs)*len(Ys)
ans-=n
print(ans)

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


class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, x, y, parent=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.size_ = 1
        self.rank_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, size: {}, rank: {})"
        return template.format(self.group_id_, self.parent_, self.size_,
                               self.rank_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def get_size(self):
        root = self.root()
        return root.size_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
                root.size_ += unite_root.size_

            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                unite_root.size_ += root.size_


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

node_array = [UnionFindNode(xy[0], xy[1], xy[2]) for xy in xy_array]

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

for i in range(N - 1):
    if xsort_array[i][1] == xsort_array[i + 1][1]:
        node_array[xsort_array[i][0]].unite(node_array[xsort_array[i + 1][0]])

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

for i in range(N - 1):
    if ysort_array[i][2] == ysort_array[i + 1][2]:
        node_array[ysort_array[i][0]].unite(node_array[ysort_array[i + 1][0]])




ans = 0

xy_group = [[set(), set()] for i in range(N)]
for node, xy in zip(node_array, xy_array):
    group = node.find()
    xy_group[group][0].add(xy[1])
    xy_group[group][1].add(xy[2])

ans = 0
for i, xy in enumerate(xy_group):
    if len(xy[0]) <= 1 or len(xy[1]) <= 1:
        continue
    ans += len(xy[0]) * len(xy[1]) - node_array[i].get_size()

print(ans)

Solution (Python):
class UnionFind(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, x_zahyou, y_zahyou,parent=None, value=None):
        self.group_id_ = group_id
        self.x_zahyou = x_zahyou
        self.y_zahyou = y_zahyou
        self.parent_ = parent
        self.value = value
        self.rank_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.rank_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
                root.x_zahyou += unite_root.x_zahyou
                root.y_zahyou += unite_root.y_zahyou
            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                unite_root.x_zahyou+= root.x_zahyou 
                unite_root.y_zahyou+= root.y_zahyou
                
N = int(input())
X = []
Y = []
node_list = []
for i in range(N):
  x, y = map(int,input().split())
  X += [[i,x]]
  Y += [[i,y]]
  node_list += [UnionFind(i,[x],[y])]
X.sort(key=lambda x: x[1])
Y.sort(key=lambda x: x[1])
for i in range(N-1):
  if X[i][1] == X[i+1][1] :
    node_list[X[i][0]].unite(node_list[X[i+1][0]])
  if Y[i][1] == Y[i+1][1] :
    node_list[Y[i][0]].unite(node_list[Y[i+1][0]])
    
chouten = 0
for i in range(N):
  if node_list[i].is_root():
    chouten += len(set(node_list[i].x_zahyou)) * len(set(node_list[i].y_zahyou))
    
print(chouten - N)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
N = int(input())
K = 10**5+1
P = [i for i in range(K)]

def par(a):
    if P[a] == a:
        return a
    t = par(P[a])
    P[a] = t
    return t
def cb(a, b):
    pa = par(a)
    pb = par(b)
    if pa != pb:
        P[pa] = pb

X = [[] for _ in range(K)]
Y = [[] for _ in range(K)]
for _ in range(N):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    Y[y-1].append(x-1)
for i in range(K):
    for j in range(len(Y[i])-1):
        cb(Y[i][j], Y[i][j+1])

M = [[] for _ in range(K)]
for i in range(K):
    M[par(i)].append(i)
ans = -N
for i in range(K):
    S = []
    for j in M[i]:
        for k in X[j]:
            S.append(k)
    S = list(set(S))
    ans += len(S)*len(M[i])
print(ans)

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

    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
from collections import defaultdict

N = int(input())
u = UnionFind(N)
xy = [list(map(int,input().split())) for _ in range(N)]
x_d = defaultdict(lambda:[])
y_d = defaultdict(lambda:[])
for i in range(N):
    x,y = xy[i]
    x_d[x].append(i)
    y_d[y].append(i)
for x in x_d:
    j = x_d[x][0]
    for i in x_d[x]:
        u.union(i,j)
for y in y_d:
    j = y_d[y][0]
    for i in y_d[y]:
        u.union(i,j)

d = defaultdict(lambda:[])
for i in range(N):
    d[u.find(i)].append(i)

ans = 0
for f in d:
    x_l = []
    y_l = []
    for i in d[f]:
        x,y = xy[i]
        x_l.append(x)
        y_l.append(y)
    x_s = set(x_l)
    y_s = set(y_l)
    ans += len(x_s)*len(y_s)-len(d[f])

print(ans)

Solution (Python):
from bisect import bisect_left
from collections import defaultdict
N = int(input())
points = list(tuple(map(int,input().split())) for _ in range(N))

xty = defaultdict(list)
ytx = defaultdict(list)
for x,y in points:
    xty[x].append(y)
    ytx[y].append(x)

area = 0
X = set()
Y = set()

for x,y in points:
    if x in X or y in Y:
        continue

    stack_x = [x]
    stack_y = [y]

    dx = set()
    dy = set()

    while stack_x or stack_y:

        while stack_x:
            x = stack_x.pop()
            if x not in dx:
                dx.add(x)
                for y in xty[x]:
                    if y not in dy:
                        stack_y.append(y)

        while stack_y:
            y = stack_y.pop()
            if y not in dy:
                dy.add(y)
                for x in ytx[y]:
                    if x not in dx:
                        stack_x.append(x)
    X |= dx
    Y |= dy
    area += len(dx)*len(dy)

print(area-len(points))

Solution (Python):
N = int(input())
x, y = (
    zip(*(map(int, input().split()) for _ in range(N))) if N else
    ((), ())
)


class UnionFindTree:
    def __init__(self, n):
        self.p = [i for i in range(n + 1)]
        self.r = [1 for _ in range(n + 1)]

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

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.r[px] < self.r[py]:
                self.p[px] = py
                self.r[py] += self.r[px]
            else:
                self.p[py] = px
                self.r[px] += self.r[py]

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


uft = UnionFindTree(10**5)
X = [[] for _ in range(10**5 + 1)]
for a, b in zip(x, y):
    X[a].append(b)
Y = [[] for j in range(10**5 + 1)]
for a, b in zip(x, y):
    Y[b].append(a)
SX = set(x)
SY = set(y)
for j in SY:
    for i in Y[j]:
        uft.union(Y[j][0], i)

X2 = [[] for _ in range(10**5 + 1)]
for i in SX:
    X2[uft.find(i)].append(i)
ans = 0
for i in SX:
    S = set()
    for i2 in X2[i]:
        for j in X[i2]:
            S.add(j)
    ans += len(X2[i]) * len(S)
ans -= N

print(ans)

Solution (Python):
N = int(input())
Points = [list(map(int, input().split())) for i in range(N)]

X_dict = {x: [] for x in range(1, 10 ** 5 + 1)}
Y_dict = {y: [] for y in range(1, 10 ** 5 + 1)}
for i, (x, y) in enumerate(Points):
    X_dict[x].append((y, i))
    Y_dict[y].append((x, i))


ans = 0
Visited = [False] * N
for i, (x, y) in enumerate(Points):
    if Visited[i]:
        continue

    stack = [('x', x), ('y', y)]
    cnt = 1
    x_set, y_set = {x}, {y}
    Visited[i] = True
    while stack:
        s, v = stack.pop()
        if s == 'x':
            for yd, j in X_dict[v]:
                if Visited[j]:
                    continue
                else:
                    cnt += 1
                    y_set.add(yd)
                    stack.append(('y', yd))
                    Visited[j] = True
        else:
            for xd, j in Y_dict[v]:
                if Visited[j]:
                    continue
                else:
                    cnt += 1
                    x_set.add(xd)
                    stack.append(('x', xd))
                    Visited[j] = True

    ans += len(x_set) * len(y_set) - cnt

print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(100000+10)


def add_edge(u, v):
	G[u].append(v)
	G[v].append(u)

def dfs(vertex, x_set, y_set):

	global visited

	if visited[vertex]:
		
		return 0
	visited[vertex] = True

	x_set.add(coords[vertex][1])
	y_set.add(coords[vertex][2])
	for v in G[vertex]:
		if visited[v]:
			
			pass
		else:
			dfs(v, x_set, y_set)

	return len(x_set)*len(y_set)

n = int(input())

G = [[] for _ in range(n)] 

visited = [False] * n
now_index = n-1

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

from operator import itemgetter


coords_xs = sorted(coords, key = itemgetter(1))
for i in range(n-1):
	if coords_xs[i][1] == coords_xs[i+1][1]: 
		
		add_edge(coords_xs[i][0], coords_xs[i+1][0])


coords_ys = sorted (coords, key = itemgetter(2))
for i in range(n-1):
	if coords_ys[i][2] == coords_ys[i+1][2]: 
		
		add_edge(coords_ys[i][0], coords_ys[i+1][0])


final = 0
for i in range(n):
	x_set = {coords[i][1]} 
	y_set = {coords[i][2]}
	final += dfs(i, x_set, y_set)

print(final - n)

Solution (Python):
import sys


def dfs(s, links, dots, checked):
    q = [s]
    xs = set()
    ys = set()
    cnt = 0
    while q:
        v = q.pop()
        if checked[v]:
            continue
        checked[v] = True

        x, y = dots[v]
        xs.add(x)
        ys.add(y)
        cnt += 1
        q.extend(links[v])
    return max(0, len(xs) * len(ys) - cnt)


n = int(input())
dots = [tuple(map(int, line.split())) for line in sys.stdin]
xs = {}
ys = {}
links = [set() for _ in [0] * n]
for i, (x, y) in enumerate(dots):
    if x in xs:
        links[i].add(xs[x])
        links[xs[x]].add(i)
    else:
        xs[x] = i
    if y in ys:
        links[i].add(ys[y])
        links[ys[y]].add(i)
    else:
        ys[y] = i

checked = [False] * n
ans = 0
for i in range(n):
    if checked[i]:
        continue
    ans += dfs(i, links, dots, checked)
print(ans)

Solution (Python):



class UnionFind:
    def __init__(self, n,xy):
        self.parent = list(range(n))
        self.size = [1]*n 
        self.xval = [{x} for x,y in xy]
        self.yval = [{y} for x,y in xy]

    def root(self, x): 
        while self.parent[x] != x:
            x, self.parent[x] = self.parent[x], self.parent[self.parent[x]]
        return x 
 
    def merge(self, x, y): 
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]: 
            self.size[y] += self.size[x] 
            self.parent[x] = y 
            self.xval[y].update(self.xval[x])
            self.yval[y].update(self.yval[x])
        else:
            self.size[x] += self.size[y] 
            self.parent[y] = x 
            self.xval[x].update(self.xval[y])
            self.yval[x].update(self.yval[y])
        return True
 
    def issame(self, x, y): 
        return self.root(x) == self.root(y)
        
    def size(self,x): 
        return self.size[self.root(x)]

n = int(input())
xy = [[int(i) for i in input().split()] for j in range(n)] 

UF = UnionFind(n,xy)

xval = dict()
yval = dict()
for i,(x,y) in enumerate(xy):
    if y in yval:
        UF.merge(i,yval[y])
    else:
        yval[y] = i

    if x in xval:
        UF.merge(i,xval[x])
    else:
        xval[x] = i

ans = -n
for i,pi in enumerate(UF.parent):
    if i==pi:
        ans += len(UF.xval[pi]) * len(UF.yval[pi])



print(ans)

Solution (Python):
from bisect import bisect_left
N = int(input())
points = list(tuple(map(int,input().split())) for _ in range(N))

X = sorted(set(x for x,y in points))
Y = sorted(set(y for x,y in points))

points = set((bisect_left(X, x), bisect_left(Y, y)) for x,y in points)

xty = [list() for _ in range(len(X))]
ytx = [list() for _ in range(len(Y))]
for x,y in points:
    xty[x].append(y)
    ytx[y].append(x)

area = 0
visited = set()

for p in points:
    if p in visited:
        continue

    stack = [p]

    dx = set()
    dy = set()

    while stack:
        x,y = stack.pop()
        visited.add((x,y))
        if x not in dx:
            for yy in xty[x]:
                if yy != y:
                    stack.append((x,yy))
            dx.add(x)
        if y not in dy:
            for xx in ytx[y]:
                if xx != x:
                    stack.append((xx,y))
            dy.add(y)
    area += len(dx)*len(dy)

print(area-len(points))

Solution (Python):
class Union():
  def __init__(me,N):
    me.N = N
    me.up = [-1]*N
    me.down = [ [] for i in range(N) ]
  def union(me,a,b):
    ua = me.up[a] if me.up[a]!=-1 else a
    ub = me.up[b] if me.up[b]!=-1 else b
    if (ua == ub):
      return
    if ( len(me.down[ua]) < len(me.down[ub]) ):
      ub,ua = ua,ub
    for v in me.down[ub]:
      me.up[v] = ua
    me.down[ua].extend( me.down[ub] )
    me.down[ub] = []
    me.up[ub] = ua
    me.down[ua].append( ub )
  def count(me,a):
    ua = me.up[a] if me.up[a]!=-1 else a
    return len(me.down[ua])+1
  
N = int(input())
li = [ [int(it) for it in input().split()] for i in range(N) ]

for i in range(N):
  li[i].append(i)

lx = sorted(li,lambda x:x[0])
ly = sorted(li,lambda x:x[1])

uni = Union(N)
for i in range(N-1):
  if ( lx[i][0] == lx[i+1][0] ):
    uni.union(lx[i][2],lx[i+1][2])
for i in range(N-1):
  if ( ly[i][1] == ly[i+1][1] ):
    uni.union(ly[i][2],ly[i+1][2])

s = 0
for i in range(N):
  if ( uni.up[i] != -1 ):
    continue
  px = set()
  py = set()
  px.add( li[i][0] )
  py.add( li[i][1] )
  for it in uni.down[i]:
      px.add( li[it][0] )
      py.add( li[it][1] )
  
  s += len(px)*len(py) - uni.count(i)
print ( s )

Solution (Python):
def uf_init(n):
    return list(range(n))

def uf_root(uf, x):
    if uf[x] != x:
        uf[x] = uf_root(uf, uf[x])
    return uf[x]

def uf_same(uf, x, y):
    return uf_root(uf, x) == uf_root(uf, y)

def uf_unite(uf, x, y):
    x = uf_root(uf, x)
    y = uf_root(uf, y)
    if x == y:
        return
    uf[x] = y


N = int(input())

x_dict = {}
y_dict = {}
uf = uf_init(N)

xy_arr = []
for i in range(N):
    x,y = (int(x) for x in input().split())
    if x in x_dict:
        uf_unite(uf, i, x_dict[x])
    else:
        x_dict[x] = i
    if y in y_dict:
        uf_unite(uf, i, y_dict[y])
    else:
        y_dict[y] = i
    xy_arr.append((x,y))

unite_dict = {}
for i in range(N):
    ur = uf_root(uf, i)
    unite_dict.setdefault(ur, [set(), set()])
    unite_dict[ur][0].add(xy_arr[i][0])
    unite_dict[ur][1].add(xy_arr[i][1])

total_points = 0
for k,v in unite_dict.items():
    total_points += len(v[0])*len(v[1])

print(total_points-N)

Solution (Python):
from operator import itemgetter

class UnionFindTree():
    def __init__(self, N):
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    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 range(len(self.__parent_of)):
            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())
    uft = UnionFindTree(N)
    P = [None] * N
    for i in range(N):
        x, y = map(int, input().split())
        P[i] = (i, x, y)
    Q = sorted(P, key=itemgetter(1))
    for i in range(1, N):
        if Q[i-1][1] == Q[i][1]:
            uft.unite(Q[i-1][0], Q[i][0])
    R = sorted(P, key=itemgetter(2))
    for i in range(1, N):
        if R[i-1][2] == R[i][2]:
            uft.unite(R[i-1][0], R[i][0])
    groups = uft.groups()
    ans = 0
    for g in groups:
        if len(g) < 3:
            continue
        xs = set()
        ys = set()
        for i in g:
            _, x, y = P[i]
            xs.add(x)
            ys.add(y)
        ans += len(xs) * len(ys) - len(g)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xtoy = {}
ytox = {}
for x, y in xy:
    if x not in xtoy:
        xtoy[x] = []
    xtoy[x].append(y)
    if y not in ytox:
        ytox[y] = []
    ytox[y].append(x)
ret = 0
while len(xtoy) > 0:
    x = next(iter(xtoy))
    xs = set()
    ys = set()
    xs.add(x)
    q = [(x, None)]
    while len(q) > 0:
        (xx, yy) = q.pop(0)
        if xx is not None:
            for y in xtoy.pop(xx):
                if y not in ys:
                    ys.add(y)
                    q.append((None, y))
        if yy is not None:
            for x in ytox.pop(yy):
                if x not in xs:
                    xs.add(x)
                    q.append((x, None))
    ret += len(xs) * len(ys)
print(ret - n)

Solution (Python):
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

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

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

from operator import itemgetter
from collections import defaultdict
from itertools import groupby
N = int(input())
XYI = []
for i in range(N):
    x, y = map(int, input().split())
    XYI.append([x, y, i])
XYx = sorted(XYI, key=itemgetter(0))
XYy = sorted(XYI, key=itemgetter(1))

uf = Uf(N)
px = py = -1
for x, y, i in XYx:
    if px==x:
        uf.unite(i, pi)
    px, pi = x, i
for x, y, i in XYy:
    if py==y:
        uf.unite(i, pi)
    py, pi = y, i
ddx = defaultdict(set)
ddy = defaultdict(set)
for x, y, i in XYI:
    ddx[uf.root(i)].add(x)
    ddy[uf.root(i)].add(y)
ans = 0
for i in range(N):
    if i==uf.root(i):
        ans += len(ddx[i]) * len(ddy[i])
print(ans - N)

Solution (Python):


N = int(input())
U = 10 ** 5
root_x = [None] * (U+1)
root_y = [None] * (U+1)
size_x = [0] * (U+1) 
size_y = [0] * (U+1) 
cnt_x = [0] * (U+1) 
cnt_y = [0] * (U+1) 
x_to_y = [None] * (U+1)
y_to_x = [None] * (U+1)

def find_root(root,size,x):
  y = root[x]
  if y is None:
    root[x] = x
    size[x] = 1
    return x
  if x == y:
    return y
  z = find_root(root,size,y)
  root[x] = z
  return z

def merge(root,size,cnt,x,y):
  rx = find_root(root,size,x)
  ry = find_root(root,size,y)
  if rx == ry:
    return
  sx = size[rx]
  sy = size[ry]
  if sx > sy:
    root[ry] = rx
    size[rx] += sy
    cnt[rx] += cnt[ry]
  else:
    root[rx] = ry
    size[ry] += sx
    cnt[ry] += cnt[rx]
  return

for _ in range(N):
  x,y = map(int,input().split())
  rx = find_root(root_x,size_x,x)
  ry = find_root(root_y,size_y,y)
  cnt_x[rx] += 1
  cnt_y[ry] += 1
  if x_to_y[rx] is None:
    x_to_y[rx] = ry
  if y_to_x[ry] is None:
    y_to_x[ry] = rx
  merge(root_y, size_y, cnt_y, x_to_y[rx], ry)
  merge(root_x, size_x, cnt_x, y_to_x[ry], rx)
  x_to_y[root_x[rx]] = root_y[ry]
  y_to_x[root_y[ry]] = root_x[rx]

  
answer = 0

for x in range(1,U+1):
  if root_x[x] is None:
    continue
  rx = find_root(root_x,size_x,x)
  if x != rx:
    continue
  y = x_to_y[x]
  ry = find_root(root_y,size_y,y)
  sx = size_x[rx]
  sy = size_y[ry]
  cnt = cnt_x[rx]
  answer += (sx * sy - cnt)
print(answer)