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











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

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

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

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        
        
        
        if root_x != root_y:
            
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root

def main():
    MAX_XY = 10**5
    N=I()
    XY=LLIN_(N)
    uf=UnionFind(2*MAX_XY)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes
    
    for x,y in XY:
        unite(x,y+MAX_XY)
    x_cnt = defaultdict(int)
    y_cnt = defaultdict(int)
    for x in range(MAX_XY):
        x_cnt[get_root(x)] += 1
    for y in range(MAX_XY,2*MAX_XY):
        y_cnt[get_root(y)] += 1
    
    ans = 0
    for x in range(MAX_XY):
        if(get_root(x)==x):
            ans += x_cnt[x]*y_cnt[x]
        y = x+MAX_XY
        if(get_root(y)==y):
            ans += x_cnt[y]*y_cnt[y]
    ans-=N
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  
            return index
        rootIndex = self.root(self.parent[index])  
        self.parent[index] = rootIndex  
        return rootIndex

    def union(self, index1, index2) :  
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  
            return

        self.component -= 1  

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

N = int(input())
R = 10**5 + 10
IXY = []

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

X = [[] for _ in range(R)]
Y = [[] for _ in range(R)]
for i, x, y in IXY:
    X[x].append(i)
    Y[y].append(i)

tree = UnionFind(N)

for x in X:
    for fr, to in zip(x, x[1:]):
        tree.union(fr, to)
for y in Y:
    for fr, to in zip(y, y[1:]):
        tree.union(fr, to)

G = [[0, set(), set()] for _ in range(N)]
for i, x, y in IXY:
    r = tree.root(i)
    G[r][0] += 1
    G[r][1].add(x)
    G[r][2].add(y)

ans = 0
for grp in G:
    if grp[0] < 3:
        continue
    x = len(grp[1])
    y = len(grp[2])
    A = x * y
    ans += max(0, A - grp[0])
print(ans)

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

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

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

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

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

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

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

import sys

input=sys.stdin.readline

N=int(input())
uf=UnionFindVerSize(10**5+1)
X=[[] for i in range(0,10**5+1)]
Y=[[] for i in range(0,10**5+1)]
for i in range(0,N):
    x,y=map(int,input().split())
    X[x].append(y)
    Y[y].append(x)

for i in range(0,10**5+1):
    if len(Y[i])>1:
        for j in range(1,len(Y[i])):
            uf.unite(Y[i][0],Y[i][j])

xgroup=[(uf.find_root(i),i) for i in range(0,10**5+1)]
xgroup.sort()
ans=0
stack=[xgroup[0][1]]
g=xgroup[0][0]
for i in range(1,10**5+1):
    if xgroup[i][0]==g:
        stack.append(xgroup[i][1])
    else:
        yco=[]
        for j in range(0,len(stack)):
            yco+=X[stack[j]]
        yco=set(yco)
        ans+=len(stack)*len(yco)
        stack=[xgroup[i][1]]
        g=xgroup[i][0]
yco=[]
for j in range(0,len(stack)):
    yco+=X[stack[j]]
yco=set(yco)
ans+=len(stack)*len(yco)
print(ans-N)

Solution (Python):
def main():
    N = int(input())
    X, Y = {}, {}
    for _ in range(N):
        x, y = map(int, input().split())
        if x not in X:
            X[x] = set()
        X[x].add(y)
        if y not in Y:
            Y[y] = set()
        Y[y].add(x)
    r = 0
    while X:
        x, ys = X.popitem()
        tx = set([x])
        ty = set(ys)
        mx, my = set(), set(ys)
        while mx or my:
            while my:
                y = my.pop()
                mx |= Y.pop(y, set())
            tx |= mx
            while mx:
                x = mx.pop()
                my |= X.pop(x, set())
            ty |= my
        r += len(tx) * len(ty)
    return r - N

print(main())

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

class UnionFind:
    def __init__(self, N):
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

N = int(input())
a = [-1] * (10**5+1)
uf = UnionFind(10**5+1)
xs = [set() for _ in range(10**5+1)]
for _ in range(N):
    x, y = map(int, input().split())
    if a[x] == -1:
        a[x] = y
    else:
        uf.unite(a[x], y)
    xs[y].add(x)

root = defaultdict(set)
for y in range(10**5+1):
    root[uf.find(y)] |= xs[y]
ans = 0
for y in range(10**5+1):
    ans += len(root[uf.find(y)]) - len(xs[y])
print(ans)

Solution (Python):
from collections import defaultdict
import sys
input = sys.stdin.readline
n = int(input())
xy = [list(map(int,input().split())) for i in range(n)]
graph = [[] for i in range(2*10**5+1)]
ans = 0
for x,y in xy:
  y += 10**5
  graph[x].append(y)
  graph[y].append(x)
  ans -= 1
vis = [0 for i in range(2*10**5+1)]
for i in range(1,2*10**5+1):
  if vis[i]:
    continue
  stack = [i]
  nx = 0
  ny = 0
  while stack:
    x = stack.pop()
    if x > 10**5:
      ny += 1
    else:
      nx += 1
    vis[x] = 1
    for y in graph[x]:
      if not vis[y]:
        stack.append(y)
        vis[y] = 1
  ans += nx*ny
print(ans)

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


class Vector:
    def __init__(self, a):
        self.a = a

    def __add__(self, b):
        c = []
        for i, j in zip(self.a, b.a):
            c.append(i + j)
        return Vector(c)


class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n
        self.rank = [1] * n
        self.count = [Vector([1, 0] if i % 2 == 0 else [0, 1])
                      for i in range(n)]

    def get_root(self, i):
        while self.parent[i] != -1:
            i = self.parent[i]
        return i

    def is_same_tree(self, i, j):
        return self.get_root(i) == self.get_root(j)

    def merge(self, i, j):
        i = self.get_root(i)
        j = self.get_root(j)
        if i == j:
            return

        if self.rank[i] > self.rank[j]:
            self.parent[j] = i
            self.rank[i] = max(self.rank[i], self.rank[j] + 1)
            self.count[i] += self.count[j]
        else:
            self.parent[i] = j
            self.rank[j] = max(self.rank[j], self.rank[i] + 1)
            self.count[j] += self.count[i]


uf = UnionFind(2 * 10 ** 5)
for _ in range(n):
    x, y = [int(i) - 1 for i in input().split()]
    uf.merge(2 * x, 2 * y + 1)

ans = 0
for i, j in zip(uf.count, uf.parent):
    if j == -1:
        a = i.a
        ans += a[0] * a[1]
print(ans - n)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
MAX = 10 ** 5

uf = UnionFind(MAX * 2)

for x, y in xy:
    x -= 1
    y -= 1
    uf.unite(x, y + MAX)

x_size = [0] * MAX * 2
y_size = [0] * MAX * 2
for i in range(MAX * 2):
    root = uf.find_set(i)
    if i < MAX:
        x_size[root] += 1
    else:
        y_size[root] += 1

ans = -n
for i in range(MAX * 2):
    ans += x_size[i] * y_size[i]

print(ans)

Solution (Python):
n=int(input())
class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
    
uf=unionfind(n)
import collections
dx=collections.defaultdict(int)
dy=collections.defaultdict(int)
l=[list(map(int,input().split())) for i in range(n)]
for i,j in enumerate(l,1):
    x,y=j
    if dx[x]:
        uf.unite(dx[x],i)
    else:
        dx[x]=i
    if dy[y]:
        uf.unite(dy[y],i)
    else:
        dy[y]=i
dx=collections.defaultdict(set)
dy=collections.defaultdict(set)
for i,j in enumerate(l,1):
    x,y=j
    dx[uf.find(i)].add(x)
    dy[uf.find(i)].add(y)
ans=0
for i,j in dx.items():
    ans+=len(j)*len(dy[i])-uf.count(i)
print(ans)

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.ps[x] > self.ps[y]:
            x, y = y, x
        self.ps[x] += self.ps[y]
        self.ps[y] = x
        return True

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

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

n = int(input())
v = 10**5 + 5
uf = UnionFind(v*2 + 10)
for _ in range(n):
  x, y = map(int, input().split())
  uf.unite(x, y+v)
d = dict()
for i in range(v*2):
  if uf.size(i) > 1:
    p = uf.find(i)
    if p not in d:
      d[p] = [0, 0]
    d[p][i > v] += 1
print(sum(x*y for x,y in d.values()) - n)

Solution (Python):
import bisect
import heapq
import sys
import queue


input = sys.stdin.readline
sys.setrecursionlimit(100000)


class V:
    def __init__(self, f):
        self.f = f
        self.v = None

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n)

    def get(self):
        return self.v


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def f(x, X, VX):
    visit_node = [set(), set()]
    visit_link = set()

    q = queue.Queue()
    q.put((0, x))
    while not q.empty():
        p, s = q.get()
        if s in visit_node[p]:
            continue

        visit_node[p].add(s)
        VX[p][s] = True
        for t in X[p][s]:
            l = (s, t) if p == 0 else (t, s)
            if l in visit_link:
                continue
            visit_link.add(l)

            if t in visit_node[1 - p]:
                continue
            q.put((1 - p, t))

    return len(visit_node[0]) * len(visit_node[1]) - len(visit_link)


def main():
    N = int(input())
    X = {}
    Y = {}

    for _ in range(N):
        x, y = read_values()
        x -= 1
        y -= 1
        X.setdefault(x, set()).add(y)
        Y.setdefault(y, set()).add(x)

    VX = [False] * (10 ** 5)
    VY = [False] * (10 ** 5)

    res = 0
    for x in X.keys():
        if VX[x]:
            continue

        res += f(x, [X, Y], [VX, VY])

    for y in Y.keys():
        if VY[y]:
            continue

        res += f(y, [Y, X], [VY, VX])

    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

n = int(input())
m = 10**5
G = [[] for i in range(2*m)]
for i in range(n):
    x,y = map(int, input().split())
    x,y = x-1, y-1
    G[x].append(m+y)
    G[m+y].append(x)

from collections import deque
used = [0]*(2*m)
def dfs(i):
    q = deque([i])
    x = 0
    y = 0
    edge = 0
    while q:
        cur = q.pop()
        if used[cur]:
            continue
        used[cur] = 1
        if cur<m:
            x += 1
        else:
            y += 1
        edge += len(G[cur])
        for to in G[cur]:
            if used[to] == 0:
                q.append(to)
    return x*y-edge//2

ans = 0
for i in range(2*m):
    if used[i]:
        continue
    ans += dfs(i)
print(ans)

Solution (Python):



n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

mx =0
my = 0
for i in range(n):
    mx = max(mx,xy[i][0])
    my = max(my,xy[i][1])

*p, = range(mx+my+1)
rank = [1]*(mx+my+1)

for i in range(n):
    xy[i][1] += mx

def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    rx = rank[px]; ry = rank[py]
    if ry < rx:
        p[py] = px
    elif rx < ry:
        p[px] = py
    else:
        p[py] = px
        rank[px] += 1
    return 1

for x,y in xy:
    unite (x,y)

xp = [0]*(mx+my+1)
yp = [0]*(mx+my+1)

for i in range(mx+my+1):
    if i<=mx:
        xp[root(i)]+=1
    else:
        yp[root(i)]+=1
ans = 0
for i in range(mx+my+1):
    ans += xp[i]*yp[i]
ans -= n
print(ans)

Solution (Python):
n = int(input())
xy = {}
for i in range(n):
  x,y = map(int,input().split())
  xy[x] = xy.get(x,[]) + [y]
d = {}
for x in xy:
  v0 = xy[x][0]
  while d.get(v0,v0) != v0:
    v0 = d[v0]
  for v in xy[x]:
    v1 = d.get(v,v)
    while d.get(v1,v1) != v1:
      v1 = d[v1]
    d[v1] = v0
for y in d:
  yp = d[y]
  y2 = [y]
  while yp != d[yp]:
    y2 += [yp]
    yp = d[yp]
  for y3 in y2:
    d[y3] = yp
e = {}
for y in d:
  e[d[y]] = e.get(d[y],0)+1
ans = 0
for x in xy:
  ans += e[d[xy[x][0]]] - len(xy[x])
print(ans)

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

from collections import deque

n = int(input())
xy = [list(map(int,input().split())) for _ in range(n)]

x_list = {}
y_list = {}
for i in range(1,10**5+1):
    x_list[i] = set()
    y_list[i] = set()

for i in range(n):
    x,y = xy[i]
    x_list[x].add(i)
    y_list[y].add(i)

remain = set(range(n))
ans = 0
while(len(remain) > 0):
    d = deque()
    d.append(remain.pop())
    num = 0
    xs = set()
    ys = set()
    while(len(d) > 0):
        tmp = d.pop()
        x,y = xy[tmp]
        num += 1
        xs.add(x)
        ys.add(y)
        while(len(x_list[x]) > 0):
            j = x_list[x].pop()
            if( j in remain):
                d.append(j)
                remain.remove(j)
        while(len(y_list[y]) > 0):
            j = y_list[y].pop()
            if(j in remain):
                d.append(j)
                remain.remove(j)

    ans += len(xs) * len(ys) - num

print(ans)

Solution (Python):
import sys
from bisect import bisect_left

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
XY = [lr() for _ in range(N)]
V = list(range(2 * 10**5 + 1)) 


def find(A,x):
    p = A[x]
    if p == x: return x
    a = find(A,p)
    A[x] = a
    return a

def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[by] = bx 

for x, y in XY:
    y += 10**5
    if find(V, x) != find(V, y):
        union(V, x, y)

set_V = [set() for _ in range(2 * 10**5 + 1)] 
for x, y in XY:
    root = find(V, x)
    set_V[root] |= set([x, y+10**5])

set_V = [x for x in set_V if x]
answer = 0
for z in set_V:
    z = sorted(list(z))
    cnt_x = bisect_left(z, 10 ** 5 + 1)
    cnt_y = len(z) - cnt_x
    answer += cnt_x * cnt_y

answer -= N
print(answer)

Solution (Python):


def dsMakeSet(ds, x):
    ds[x] = x


def dsFind(ds, x):
    if ds[x] == x:
        return x

    x0 = x
    while ds[x] != x:
        x = ds[x]

    ds[x0] = x
    return x


def dsUnion(ds, x, y):
    xRoot = dsFind(ds, x)
    yRoot = dsFind(ds, y)
    
    if xRoot != yRoot:
        ds[yRoot] = xRoot
        return True

    return False



N = int(input())
Q = {}

for _ in range(N):
    x, y = map(int, input().split())

    X = ('x', x)
    Y = ('y', y)

    if not (X in Q):
        dsMakeSet(Q, X)

    if not (Y in Q):
        dsMakeSet(Q, ('y', y))
    
    dsUnion(Q, X, Y)

R = {}

for q in Q:
    root = dsFind(Q, q)
    
    if not(root in R):
        R[root] = [0, 0]

    r = R[root]
    if q[0] == 'x':
        r[0] += 1
    else:
        r[1] += 1

s = 0
for r in R.values():
    s += r[0]*r[1]

print(s - N)

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

    
    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 sizeof(self, x):
        return self.sizex[self.find(x)] * self.sizey[self.find(x)]

    
    def unite(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
            self.sizex[y] += self.sizex[x]
            self.sizey[y] += self.sizey[x]
        else:
            self.par[y] = x
            self.sizex[x] += self.sizex[y]
            self.sizey[x] += self.sizey[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


def coordinate_compression(arr):
    return {v: k for k, v in enumerate(sorted(set(arr)))}


n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())
dx = coordinate_compression(x)
dy = coordinate_compression(y)
uf = UnionFind(len(dx) + len(dy), len(dx), len(dy))
for i in range(n):
    uf.unite(dx[x[i]], dy[y[i]] + len(dx))
s = set()
ans = 0
for i in range(len(dx)):
    p = uf.find(i)
    if p in s:
        continue
    ans += uf.sizeof(i)
    s.add(p)
print(ans - n)

Solution (Python):

import sys
sys.setrecursionlimit(100000)



def solve(x, x_set, y_set, x2y, y2x):
  num_e = 0
  if x in x2y:
    x_set.add(x)
    yl = x2y.pop(x)
    num_e += len(yl)
    for y in yl:
      num_e += solve(y, y_set, x_set, y2x, x2y)
  return num_e


N = int(input())
X2Y = {}
Y2X = {}
for i in range(N):
  x, y = map(int, input().split())
  if x in X2Y:
    X2Y[x].append(y)
  else:
    X2Y[x] = [y]
  if y in Y2X:
    Y2X[y].append(x)
  else:
    Y2X[y] = [x]


ans = 0
while X2Y:
    x = next(iter(X2Y)) 
    x_set = set() 
    y_set = set() 
    num_e = solve(x, x_set, y_set, X2Y, Y2X)
    ans += len(x_set)*len(y_set) - num_e//2

print(ans)

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

N = int(input())
XY = [[set() for i in range(10**5+1)] for j in range(2)]
for i in range(N):
  x, y = map(int, input().split())
  XY[0][x].add(y)
  XY[1][y].add(x)

is_visited_x = [False] * (10**5 + 1)
def dfs(x):
  global is_visited_x
  is_visited_x[x] = True
  stack = [[x], []]
  idx = 0
  num_e = 0
  num_xy = [1, 0]
  parent = 0
  while stack[0] or stack[1]:
    node = stack[idx][-1]
    children = XY[idx][node]
    if children:
      child = children.pop()
      XY[idx-1][child].remove(node) 
      num_e += 1
      if child in stack[idx-1]:
        continue
      stack[idx-1].append(child)
      num_xy[idx-1] += 1
      is_visited_x[child] += idx
      idx = (idx + 1) % 2
    else:
      stack[idx].pop()
      idx = (idx + 1) % 2
  return num_e, num_xy

ans = 0
for x in range(1, 10**5+1):
  if is_visited_x[x]:
    continue
  num_e, num_xy = dfs(x)
  ans += num_xy[0]*num_xy[1] - num_e

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(100000)

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] = [y]
    else:
        xtoy[x].append(y)
    if y not in ytox:
        ytox[y] = [x]
    else:
        ytox[y].append(x)

def doit(x, xs, ys, xtoy, ytox):
    ret = 0
    if x in xtoy:
        xs.add(x)
        yl = xtoy.pop(x)
        ret += len(yl)
        for y in yl:
            ret += doit(y, ys, xs, ytox, xtoy)
    return ret

ret = 0
while len(xtoy) > 0:
    x = next(iter(xtoy))
    xs = set()
    ys = set()
    num = doit(x, xs, ys, xtoy, ytox)
    ret += len(xs) * len(ys) - num // 2

print(ret)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
s = set()
res = 0

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

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

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

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

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

uf = UnionFind(2 * 10 ** 5)

for _ in range(N):
  u, v = map(int, input().split())
  s.add(u)
  uf.Unite(u, v + 10 ** 5)

ss = set()
c = [0] * (2 * 10 ** 5 + 1)
for x in s:
  y = uf.Find_Root(x)
  ss.add(y)
  c[y] += 1
for x in ss:
  t = uf.Count(x)
  xc = c[x]
  yc = t - xc
  res += xc * yc
print(res - N)

Solution (Python):
class UnionFind():
    def __init__(self,size):
        self.table=[-1]*size
    def root(self,x):
        while self.table[x]>=0:
            x=self.table[x]
        return x
    def unite(self,x,y):
        s1=self.root(x)
        s2=self.root(y)
        if s1!=s2:
            if self.table[s1]>self.table[s2]:
                s1,s2=s2,s1
            self.table[s1]+=self.table[s2]
            self.table[s2]=s1
        return
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.table[self.root(x)]
n,*z=map(int,open(0).read().split())
u=UnionFind(10**5*2+1)
for x,y in zip(*[iter(z)]*2):
    u.unite(x,10**5+y)
d=[[0,set(),set()]for _ in range(10**5*2+1)]
for x,y in zip(*[iter(z)]*2):
    t=d[u.root(x)]
    t[0]+=1
    t[1].add(x)
    t[2].add(y)
print(sum(len(x)*len(y)-a for a,x,y in d))

Solution (Python):
class UnionFind():
    def __init__(self,size):
        self.table=[-1]*size
    def root(self,x):
        while self.table[x]>=0:
            x=self.table[x]
        return x
    def unite(self,x,y):
        s1=self.root(x)
        s2=self.root(y)
        if s1!=s2:
            if self.table[s1]>self.table[s2]:
                s1,s2=s2,s1
            self.table[s1]+=self.table[s2]
            self.table[s2]=s1
        return
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.table[self.root(x)]
n,*z=map(int,open(0).read().split())
u=UnionFind(10**5*2+1)
for x,y in zip(*[iter(z)]*2):
    u.unite(x,10**5+y)
d=[[0,set(),set()]for _ in range(10**5*2+1)]
for x,y in zip(*[iter(z)]*2):
    t=d[u.root(x)]
    t[0]+=1
    t[1].add(x)
    t[2].add(y)
print(sum(len(x)*len(y)-a for a,x,y in d))

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

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

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

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        
        
        
        if root_x != root_y:
            
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root

def main():
    N=I()
    XY=LLIN(N)
    MAX_XY = 10**5+1
    uf=UnionFind((MAX_XY)*2)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes
    
    """ 
    http://drken1215.hatenablog.com/entry/2019/06/23/004700
    ・二部グラフにして
    ・連結成分ごとに
    ・完全二部グラフにするように辺を追加する(この二部グラフの辺(x,y)はグリッド上の点(x,y)に対応する)
    """
    

    for x,y in XY:
        unite(x,y+MAX_XY)
    
    cnt_x = defaultdict(int)
    cnt_y = defaultdict(int)
    
    for x in range(MAX_XY):
        cnt_x[ get_root(x) ] += 1
    for y in range(MAX_XY,2*MAX_XY):
        cnt_y[ get_root(y) ] += 1
    
    ans = 0
    
    for root in range(2*MAX_XY):
        ans += cnt_x[root] * cnt_y[root]
    
    ans -= N 
    print(ans)



if __name__ == '__main__':
    main()