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

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        
        
        self.par = [i for i in range(n+1)]
        
        self.rank = [0] * (n+1)
        
        self.size = [1] * (n+1)
        
        self.tree = [True] * (n+1)

    def find(self, x):
        """ 根の検索(グループ番号と言えなくもない) """
        
        if self.par[x] == x:
            return x
        else:
            
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """ 併合 """
        
        x = self.find(x)
        y = self.find(y)

        
        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def get_size(self, x=None):
        if x is not None:
            """ あるノードの属する集合のノード数 """
            return self.size[self.find(x)]
        else:
            """ 集合の数 """
            res = set()
            for i in range(self.n+1):
                res.add(self.find(i))
            
            return len(res) - 1
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

MAX = 10 ** 5
N = INT()
uf = UnionFind(MAX * 2)
edges = []
for i in range(N):
    x, y = MAP()
    edges.append((x, y))
    uf.union(x, y+MAX)



D = defaultdict(lambda: [0, 0, 0])

for x, y in edges:
    D[uf.find(x)][0] += 1

for x in range(1, MAX+1):
    y = x + MAX
    D[uf.find(x)][1] += 1
    D[uf.find(y)][2] += 1

ans = 0

for edgecnt, xcnt, ycnt in D.values():
    
    ans += xcnt * ycnt - edgecnt
print(ans)

Solution (Python):
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq
sys.setrecursionlimit(100000)


def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()

class union_find:
    def __init__(self, n):
        self.N = n
        self._parent = [i for i in range(self.N)]
        self._mem = [1] * self.N
        self.compo = self.N

    def parent(self, a):
        if self._parent[a] == a:
            return a
        self._parent[a] = self.parent(self._parent[a])
        return self._parent[a]

    def united(self,a, b):
        return self.parent(a) == self.parent(b)
    
    def unite(self,a, b):
        a = self.parent(a)
        b = self.parent(b)
        if(a == b): return False
        if self._mem[a] > self._mem[b]: a, b = b, a
        self._parent[a] = b
        self._mem[b] += self._mem[a]
        self.compo -= 1
        return True
    
    def is_root(self,a):
        return a == self._parent[a]
    def mem_cnt(self,a):
        return self._mem[self.parent(a)]
    def dump(self):
        print(self._parent)



def main():
    N = ri()
    X = [0] * N
    Y = [0] * N
    for i in range(N):
        X[i], Y[i] = rip()
    
    uf = union_find(N)
    di = dict()
    for i in range(N):
        if not X[i] in di: di[X[i]] = i
        uf.unite(i, di[X[i]])
    di.clear()
    for i in range(N):
        if not Y[i] in di: di[Y[i]] = i
        uf.unite(i, di[Y[i]])

    hx = [set() for i in range(N)]
    hy = [set() for i in range(N)]
    for i in range(N):
        hx[uf.parent(i)].add(X[i])
        hy[uf.parent(i)].add(Y[i])
    
    tot = 0
    for i in range(N):
        tot += len(hx[i]) * len(hy[i])
    
    print(tot - N)



if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
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

N = int(input())
dx = defaultdict(list)
dy = defaultdict(list)
xy = []

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

u = UnionFind(N)

for x in dx:
    i = dx[x][0]
    for j in dx[x]:
        u.union(i,j)

for y in dy:
    i = dy[y][0]
    for j in dy[y]:
        u.union(i,j)

dx = defaultdict(list)
dy = defaultdict(list)

for i in range(N):
    dx[u.find(i)].append(xy[i][0])
    dy[u.find(i)].append(xy[i][1])

ans = -N
for i in dx:
    ans += len(set(dx[i]))*len(set(dy[i]))

print(ans)

Solution (Python):

def wantp(n):

    q = []
    while p[n] != n:
        q.append(n)
        n = p[n]

    for i in q:
        p[i] = n

    return n

N = int(input())

oXYi = []
XYi = []
YXi = []

for i in range(N):

    x,y = map(int,input().split())
    oXYi.append([x,y,i])
    XYi.append([x,y,i])
    YXi.append([y,x,i])

p = [i for i in range(N)]
rank = [1] * N

XYi.sort()
YXi.sort()


li = -1
for i in range(N):

    if XYi[i][0] != XYi[li][0]:
        li = i

    else:
        ti = XYi[i][2]
        tli = XYi[li][2]
        ip = wantp(ti)
        lip = wantp(tli)

        if ip != lip:
        
            if rank[ip] < rank[lip]:
                p[ip] = lip
            elif rank[ip] > rank[lip]:
                p[lip] = ip
            else:
                p[lip] = ip
                rank[ip] += 1

li = -1
for i in range(N):

    if YXi[i][0] != YXi[li][0]:
        li = i

    else:
        ti = YXi[i][2]
        tli = YXi[li][2]
        ip = wantp(ti)
        lip = wantp(tli)
        
        if ip != lip:
        
            if rank[ip] < rank[lip]:
                p[ip] = lip
            elif rank[ip] > rank[lip]:
                p[lip] = ip
            else:
                p[lip] = ip
                rank[ip] += 1       

ndic = {}
xkazu = {}
ykazu = {}

for i in range(N):

    np = wantp(i)
    if np not in ndic:
        ndic[np] = 1
    else:
        ndic[np] += 1

    if np not in xkazu:
        xkazu[np] = {}
        ykazu[np] = {}

    xkazu[np][oXYi[i][0]] = 1
    ykazu[np][oXYi[i][1]] = 1

ans = 0

for i in ndic:
    ans += len(xkazu[i]) * len(ykazu[i]) - ndic[i]

print (ans)

Solution (Python):
class UnionFind:
    
    def __init__(self, n):
        
        self.par = [-1] * n
        
        self.rank = [0] * n

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

    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x != y:
            
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            
            self.par[x] += self.par[y]
            self.par[y] = x

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

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


import operator

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

for i in range(n):
    z[i].append(i)

u = UnionFind(n)
z.sort()
for i in range(1,n):
    if z[i][0]==z[i-1][0]:
        u.unite(z[i][2],z[i-1][2])

z.sort(key=operator.itemgetter(1))
for i in range(1,n):
    if z[i][1]==z[i-1][1]:
        u.unite(z[i][2],z[i-1][2])

l = [[]for i in range(n)]

z.sort(key=operator.itemgetter(2))
for i in range(n):
    l[u.find(i)].append(z[i])

ans = 0
for i in range(n):
    if l[i]!=[]:
        x = set()
        y = set()
        for a in l[i]:
            if a[0] not in x:
                x.add(a[0])
            if a[1] not in y:
                y.add(a[1])
        ans += len(x)*len(y)-len(l[i])
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**5)

def find_parent(i):
    aaa=0
    while True:
        if parent[i]<0:
            aaa=i
            break
        else:
            i=parent[i]
    return aaa

def connect(A,B):
    A=find_parent(A)
    B=find_parent(B)
    if A!=B:
        p_A,p_B=parent[A],parent[B]
        if p_A<p_B:
            parent[A]+=p_B
            parent[B]=A
            child[A].append(B)
        else:
            parent[B]+=p_A
            parent[A]=B
            child[B].append(A)

n=int(input())
x_max=0
y_max=0
xy=[]
for _ in range(n):
    x,y=map(int,input().split())
    x_max=max(x_max,x)
    y_max=max(y_max,y)
    xy.append([x,y])
data=[[] for _ in range(x_max+1)]
parent=[-1]*(x_max+1)
child=[[] for i in range(x_max+1)]
lst=[0]*(y_max+1)
for x,y in xy:
    data[x].append(y)
    if lst[y]==0:
        lst[y]=x
    else:
        connect(lst[y],x)

lsls=[]
for i in range(1,x_max+1):
    if parent[i]>=0:
        continue
    if not data[i]:
        continue
    que=[i]
    h=[i]
    while que:
        u=que.pop()
        for v in child[u]:
            que.append(v)
            h.append(v)
    lsls.append(h)

ans=0
for u in lsls:
    L=len(u)
    flag=[0]*(y_max+1)
    cnt=0
    count=0
    for v in u:
        for w in data[v]:
            count+=1
            if flag[w]==0:
                flag[w]=1
                cnt+=1
    ans+=L*cnt-count

print(ans)

Solution (Python):
def main():
    n=int(input())
    xy=[list(map(int,input().split())) for _ in [0]*n]
    ixy=[[i,x,y] for i,(x,y) in enumerate(xy)]
    class unionfind():
        
        def __init__(self,size):
            self.size=size
            self.tree_root=list(range(self.size))
            self.tree_depth=[1]*self.size
        
        
        def root(self,index):
            temp_list=[]
            temp=self.tree_root[index]
            while index!=temp:
                temp_list.append(index)
                index=temp
                temp=self.tree_root[index]
            for i in temp_list:
                self.tree_root[i]=index
            return index
        
        
        def unite(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1!=r2:
                d1,d2=self.tree_depth[r1],self.tree_depth[r2]
                if d1<=d2:
                    self.tree_root[r1]=r2
                    self.tree_depth[r2]=max(d1+1,d2)
                else:
                    self.tree_root[r2]=r1
                    self.tree_depth[r1]=max(d2+1,d1)
    
        
        def same(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            return r1==r2
    
        
        def component(self):
            return len({self.root(i) for i in range(self.size)})

    u=unionfind(n)
    ixy.sort(key=lambda x:x[1])
    for i in range(n-1):
        if ixy[i][1]==ixy[i+1][1]:
            u.unite(ixy[i][0],ixy[i+1][0])
    ixy.sort(key=lambda x:x[2])
    for i in range(n-1):
        if ixy[i][2]==ixy[i+1][2]:
            u.unite(ixy[i][0],ixy[i+1][0])
    tate=[set() for _ in [0]*n]
    yoko=[set() for _ in [0]*n]
    cnt=[0]*n
    for i in range(n):
        r=u.root(i)
        tate[r].add(xy[i][0])
        yoko[r].add(xy[i][1])
        cnt[r]+=1
    print(sum([len(tate[i])*len(yoko[i])-cnt[i] for i in range(n)]))
main()

Solution (Python):
class UnionFindTree:
    """Disjoint-Set Data Structure
       Union-Find Tree
       complexity:
          init: O(n)
          find, unite, same: O(alpha(n))
       used in SRM505 div.2 900, ATC001 A, DSL1A(AOJ)
    """
    def __init__(self, n):
        self.par = list(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 unite(self, x, y):
        x, y = self.find(x), 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(self, x, y):
        return self.find(x) == self.find(y)


N = int(input())
M = 10 ** 5
uft = UnionFindTree(2 * M)

for _ in range(N):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    uft.unite(x, y + M)
x_dict, y_dict = dict(), dict()
for x in range(M):
    par_x = uft.find(x)
    x_dict[par_x] = x_dict.get(par_x, 0) + 1
for y in range(M, 2 * M):
    par_y = uft.find(y)
    y_dict[par_y] = y_dict.get(par_y, 0) + 1
ans = -N
for r in x_dict.keys():
    ans += x_dict.get(r, 0) * y_dict.get(r, 0)
print(ans)

Solution (Python):
class UnionFindTree:
    """Disjoint-Set Data Structure
       Union-Find Tree
       complexity:
          init: O(n)
          find, unite, same: O(alpha(n))
       used in SRM505 div.2 900, ATC001 A, DSL1A(AOJ)
    """
    def __init__(self, n):
        self.par = list(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 unite(self, x, y):
        x, y = self.find(x), 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(self, x, y):
        return self.find(x) == self.find(y)


N = int(input())
M = 10 ** 5
uft = UnionFindTree(N + 2 * M)

for i in range(N):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    uft.unite(i, x + N)
    uft.unite(i, y + N + M)
x_dict, y_dict = dict(), dict()
for x in range(N, M + N):
    par_x = uft.find(x)
    x_dict[par_x] = x_dict.get(par_x, 0) + 1
for y in range(N + M, N + 2 * M):
    par_y = uft.find(y)
    y_dict[par_y] = y_dict.get(par_y, 0) + 1
ans = -N
for r in x_dict.keys():
    ans += x_dict.get(r, 0) * y_dict.get(r, 0)
print(ans)

Solution (Python):
import sys,os,math
from collections import Counter, defaultdict, deque, OrderedDict
import bisect
from sys import stdin, stdout
from itertools import repeat
import Queue








def main():
    n = map(int, raw_input().split())[0]
    G = defaultdict(list)
    bfs = []
    for i in range(n):
        a, b = map(int, raw_input().split())
        b += 100000
        G[a].append(b)
        G[b].append(a)
        bfs.append(a)

    vs = set()
    ans = 0
    for i in bfs:
        if i in vs:
            continue
        x, y = 0, 0
        t = 0
        vs.add(i)
        q = deque()
        q.append(i)
        while q:
            now = q.popleft()
            if now > 100000:
                y += 1
            else:
                x += 1
            for adj in G[now]:
                t += 1
                if adj not in vs:
                    
                    vs.add(adj)
                    q.append(adj)
        
        ans += x*y - t/2
    print ans




main()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


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


def B():
    n, l = LI()
    lis = [l + i for i in range(n)]
    s = sum(lis)
    a = inf
    for i in lis:
        if abs(a) > abs(i):
            a = i
    print(s-a)
    return


def C():
    def gcd(a, b):
        a, b = max(a, b), min(a, b)
        while b:
            a, b = b, a % b
        return a
    def lcm(a, b):
        return a * b // gcd(a, b)
    a, b, c, d = LI()
    x = b // c - (a-1) // c
    y = b // d - (a-1) // d
    z = b // lcm(c , d) - (a-1) // lcm(c , d)
    print(b-a+1-(x+y-z))
    return


def D():
    n = II()
    ab = LIR(n)
    ab.sort(key=lambda x: x[1])
    now = 0
    for a, b in ab:
        now += a
        if now <= b:
            continue
        print("No")
        return
    print("Yes")
    return


def E():
    n, k = LI()
    if k > (n - 1) * (n - 2) / 2:
        print(-1)
        return
    d = (n - 1) * (n - 2) // 2 - k
    a = [[] for i in range(n)]
    for i in range(n):
        if i != 1:
            a[i].append(1)
            a[1].append(i)
    l = 0
    m = 2
    while d > 0:
        a[l].append(m)
        m += 1
        d -= 1
        if m == n:
            l += 1
            m = l + 1
            if l == 1:
                l = 2
                m = 3
    aa = 0
    ans = []
    for num,i in enumerate(a):
        for l in i:
            if num < l:
                aa += 1
                ans.append((num+1,l+1))
    print(aa)
    for x, y in ans:
        print(x, y)
    return


def F():
    n = II()
    xy = LIR(n)
    d = defaultdict(list)
    par = defaultdict(int)
    for _, y in xy:
        par[y] = y
    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]
    
    def unite(x, y):
        x = root(x)
        y = root(y)
        if x == y:
            return False
        if x > y: x, y = y, x
        par[y] = x
        return True
    
    setx = set()
    for x, y in xy:
        d[x].append(y)
    for key, value in d.items():
        p = value[0]
        for v in value[1:]:
            unite(p, v)
    ans1 = defaultdict(int)
    ans2 = defaultdict(int)
    ans = 0
    for x, y in xy:
        root(y)
    
    for _, value in d.items():
        ans1[par[value[0]]] += 1
    for _, value in par.items():
        ans2[value] += 1
    
    for key, value in ans1.items():
        ans += ans2[key] * value
    print(ans - n)
    return


if __name__ == '__main__':
    F()

Solution (Python):
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, 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):
    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 size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(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=UF(2*10**5)
for i in range(n):
  x,y=map(int,input().split())
  UF.unite(x-1+10**5,y-1)
UF.groupnum()
ct=[[0,0] for i in range(2*10**5)]
for i in range(2*10**5):
  if i<10**5:
    ct[UF._parent[i]][0]+=1
  else:
    ct[UF._parent[i]][1]+=1
ans=0
for i in range(2*10**5):
  ans+=ct[i][0]*ct[i][1]
print(ans-n)

Solution (Python):
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]
        self.size = [1 for _ in range(size)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(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):
        x = self.find(x)
        return self.size[x]



N = int(input())
U = UnionFind(N)
xyi = []
xy = []
for i in range(N):
    x, y = map(int, input().split())
    xyi.append((x, y, i))
    xy.append((x, y))
xyi.sort()
for j in range(N-1):
    x0, y0, i0 = xyi[j]
    x1, y1, i1 = xyi[j+1]
    if x0 == x1:
        U.unite(i0, i1)
xyi.sort(key = lambda x:x[1])
for j in range(N-1):
    x0, y0, i0 = xyi[j]
    x1, y1, i1 = xyi[j+1]
    if y0 == y1:
        U.unite(i0, i1)
equiv = [[set(), set()] for _ in range(N)]
for i in range(N):
    p = U.find(i)
    equiv[p][0].add(xy[i][0])
    equiv[p][1].add(xy[i][1])
ans = 0
for i in range(N):
    ans+=len(equiv[i][0])*len(equiv[i][1])
ans-=N
print(ans)

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


def main():
    N = int(input())
    XY = [list(map(int, input().split())) for _ in range(N)]

    MAX = 10**5
    Xs = [[] for _ in range(MAX+1)]
    Ys = [[] for _ in range(MAX+1)]
    for i, (x, y) in enumerate(XY):
        Xs[x].append(i)
        Ys[y].append(i)

    ans = 0
    checked = [False]*N
    for i in range(N):
        if checked[i]: continue
        q = [i]
        checked[i] = True
        X = set()
        Y = set()
        c = 0
        while q:
            qq = []
            for p in q:
                x, y = XY[p]
                X.add(x)
                Y.add(y)
                c += 1
                for ni in Xs[x]:
                    if not checked[ni]:
                        checked[ni] = True
                        qq.append(ni)
                for ni in Ys[y]:
                    if not checked[ni]:
                        checked[ni] = True
                        qq.append(ni)
            q = qq
        ans += len(X)*len(Y)-c

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.buffer.readline


from collections import defaultdict


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

class UnionFind:
	def __init__(self, n):
		self.par = [i for i in range(n)]
		self.rank = [0] * n
		self.size = [1] * 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 same_check(self, x, y):
		return self.find(x) == self.find(y)

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if self.rank[x] < self.rank[y]:
			if self.same_check(x, y) != True:
				self.size[y] += self.size[x]
				self.size[x] = 0
			self.par[x] = y
		else:
			if self.same_check(x, y) != True:
				self.size[x] += self.size[y]
				self.size[y] = 0
			self.par[y] = x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1

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


def main():
	N = int(input())
	Lx = []
	Ly = []
	UF = UnionFind(N)
	for i in range(N):
		x, y = getlist()
		Lx.append([x, y, i])
		Ly.append([y, x, i])
	Lx = sorted(Lx)
	Ly = sorted(Ly)
	for i in range(N - 1):
		if Lx[i][0] == Lx[i + 1][0]:
			UF.union(Lx[i][2] , Lx[i + 1][2])
		if Ly[i][0] == Ly[i + 1][0]:
			UF.union(Ly[i][2] , Ly[i + 1][2])
	for i in range(N):
		UF.par[i] = UF.find(i)

	nodeX = [[] for i in range(N)] 
	nodeY = [[] for i in range(N)]
	PAR = UF.par
	for i in range(N):
		nodeX[PAR[Lx[i][2]]].append(Lx[i][0])
		nodeY[PAR[Lx[i][2]]].append(Lx[i][1])
	
	

	
	ans = 0
	D = defaultdict(int)
	for i in range(N):
		if D[PAR[i]] == 0:
			D[PAR[i]] = 1
			ans += len(set(nodeX[PAR[i]])) * len(set(nodeY[PAR[i]])) - UF.size[PAR[i]]
	print(ans) 



if __name__ == '__main__':
	main()

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

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

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

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

    def get_size(self, x):
        r = self.root(x)
        return self.size[r]

    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.size[r1] += self.size[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]
        self.group_num -= 1



U = UnionFind(10 ** 5 * 2)
n = I()
X = []
Y = []
for _ in range(n):
    x, y = LI()
    U.union(x - 1, y - 1 + 10 ** 5)


XD = defaultdict(int)
YD = defaultdict(int)
for i in range(10 ** 5 * 2):
    if i < 10 ** 5:
        XD[U.root(i)] += 1
    else:
        YD[U.root(i)] += 1


ret = 0
for j in range(10 ** 5 * 2):
    ret += XD[j] * YD[j]


print(ret - n)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    V=100005
    n=int(input())
    E=[[] for _ in range(V*2)]
    for _ in range(n):
        x,y=map(int,input().split())
        y+=V
        E[x].append(y)
        E[y].append(x)

    visited=[0]*(2*V)
    def dfs(v):
        if(visited[v]): return
        visited[v]=1
        cnt[v//V]+=1
        for nv in E[v]: dfs(nv)

    ans=[0]
    for v in range(2*V):
        if(visited[v]): continue
        cnt=[0]*2 
        dfs(v)
        ans[0]+=cnt[0]*cnt[1]
    print(ans[0]-n)
resolve()

Solution (Python):
import copy
import collections
import sys
read = sys.stdin.read
NXY = [int(_) for _ in read().split()]
N = NXY[0]
X = NXY[1::2]
Y = NXY[2::2]
xi = {x: i for i, x in enumerate(set(X))}
yj = {y: j for j, y in enumerate(set(Y))}


class UnionFind():
    def __init__(self, size):
        self.dat = list(range(size))
        self.SIZE = [1] * size  

    def find(self, x):
        dat = self.dat
        stack = [x]
        while True:
            y = stack[-1]
            if dat[y] != y:
                stack += [dat[y]]
            else:
                break
        for s in stack:
            dat[s] = y
        return y

    def unite(self, x, y):
        is_same = self.is_same
        find = self.find
        SIZE = self.SIZE
        dat = self.dat
        if not is_same(x, y):
            X, Y = find(x), find(y)
            SX, SY = SIZE[X], SIZE[Y]
            if SX > SY:
                m = dat[X] = Y
            else:
                m = dat[Y] = X
            SIZE[m] = SX + SY
            SIZE[X + Y - m] = 0

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

    def scan_uf(self):
        find = self.find
        length = len(self.dat)
        for i in range(length):
            find(i)

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


ufx = UnionFind(len(xi))
ufy = UnionFind(len(yj))
sxy = collections.defaultdict(set)
syx = collections.defaultdict(set)
for x, y in zip(X, Y):
    i = xi[x]
    j = yj[y]
    sxy[i].add(j)
    syx[j].add(i)
sxy2 = copy.deepcopy(sxy)
for sy in sxy.values():
    y1 = sy.pop()
    for y in sy:
        ufy.unite(y1, y)
for sx in syx.values():
    x1 = sx.pop()
    for x in sx:
        ufx.unite(x1, x)
ufx.scan_uf()
ufy.scan_uf()
ans = 0
for x, vx in enumerate(ufx.SIZE):
    if vx:
        vy = ufy.size(sxy2[x].pop())
        ans += vx * vy
print(ans - N)