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):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """ 根を見つける関数を定義（同時にxを直接根にくっつける操作も行う）"""
        tmp = []
        parents = self.parents
        while parents[x] >= 0:
            tmp.append(x)
            x = parents[x]
        for y in tmp:
            parents[y] = x
        return x

    def union(self, x, y):
        """ 二つの木をくっつける（子を多く持つ方を根とした親子関係）。これは破壊的操作を行う。"""
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        """ xとyが同じ根の子かを判定 """
        return self.find(x) == self.find(y)

    def size(self, x):
        """ x の根の parent（= 要素数）を返す """
        return -self.parents[self.find(x)]

    def members(self, x):
        """ xが属するグループの要素をリストとして返す O(N)"""
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """ 全ての根の要素をリストとして返す O(N)"""
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """ グループの数を返す O(1)"""
        return len(self.roots())

    def size_list(self):
        """ 各グループの要素数のリストを返す(根の番号は返さない) O(N)"""
        return [-x for x in self.parents if x < 0]

    def all_group_members(self):
        """ {根:[根の子(根を含む)のリスト],...}を辞書で返す """
        res = [[] for _ in range(self.n)]
        for i in range(self.n):
            x = self.find(i)
            res[x].append(i)
        return {r: res[r] for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



import sys
input = sys.stdin.readline


N = int(input())
U = UnionFind(2*N)
P = [[] for _ in range(N)]
code1, code2 = {}, {}
for i in range(N):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    if a not in code1:
        code1[a]=i
    if b not in code2:
        code2[b]=i+N
    U.union(code1[a],code2[b])
res = 0
for a in U.all_group_members().values():
    x, y = 0, 0
    for b in a:
        if b<N: x += 1
        else: y += 1
    res += x*y
print(res-N)

Solution (Python):
n = int(input())
MAX = 10**5
adj = [[[] for u in range(MAX+1)] for t in range(2)]
vis = [[False for u in range(MAX+1)] for t in range(2)]
for i in range(n):
	x, y = map(int,input().split())
	adj[0][x].append(y)
	adj[1][y].append(x)

import sys
sys.setrecursionlimit(4*10**5+1)

def dfs(t,u): 
	vis[t][u] = True

	ct = [0,0,0]
	ct[t] += 1
	for v in adj[t][u]:
		ct[2] += 1
		if not vis[t^1][v]:
			ctv = dfs(t^1,v)

			ct[0] += ctv[0]
			ct[1] += ctv[1]
			ct[2] += ctv[2]

	return ct

ans = 0
for u in range(1,MAX+1):
	if not vis[0][u]:
		L, R, M = dfs(0,u)
		ans += L*R-M//2

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
edges = [[] for i in range(200000)]
for i in range(n):
    x, y = map(int, input().split())
    edges[x - 1].append(y + 99999)
    edges[y + 99999].append(x - 1)
ans = 0
visited = [0] * (200000)
cntx, cnty = 0, 0
def dfs(u):
    global cntx, cnty
    visited[u] = 1
    if u // 100000 >= 1:
        cnty += 1
    else:
        cntx += 1
    for i in edges[u]:
        if visited[i] == 0:
            dfs(i)
ans = -1 * n
for i in range(100000):
    if visited[i] == 0:
        cntx, cnty = 0, 0
        dfs(i)
        ans += cntx * cnty
print(ans)

Solution (Python):
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


def main():
    N, *XY = map(int, read().split())

    MAX = 100010
    uf = UnionFind(MAX * 2)
    for x, y in zip(*[iter(XY)] * 2):
        uf.union(x, y + MAX)

    x_comp = Counter()
    y_comp = Counter()
    for i in range(MAX):
        x_comp[uf.find(i)] += 1
    for i in range(MAX, 2 * MAX):
        y_comp[uf.find(i)] += 1

    ans = 0
    for k in x_comp.keys():
        ans += x_comp[k] * y_comp[k]

    ans -= N

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


def main():
    N, *XY = map(int, read().split())

    MAX = 100010
    uf = UnionFind(MAX * 2)
    for x, y in zip(*[iter(XY)] * 2):
        uf.union(x, y + MAX)

    x_comp = Counter()
    y_comp = Counter()
    for i in range(MAX):
        x_comp[uf.find(i)] += 1
    for i in range(MAX, 2 * MAX):
        y_comp[uf.find(i)] += 1

    ans = 0
    for k in x_comp.keys():
        ans += x_comp[k] * y_comp[k]

    ans -= N

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from operator import itemgetter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


def main():
    N, *XY = map(int, read().split())

    P = [(x, y) for x, y in zip(*[iter(XY)] * 2)]
    uf = UnionFind(N)

    Q = [(x, y, i) for i, (x, y) in enumerate(P)]

    Q.sort()
    for j in range(N - 1):
        if Q[j][0] == Q[j + 1][0]:
            uf.union(Q[j][2], Q[j + 1][2])

    Q.sort(key=itemgetter(1))
    for j in range(N - 1):
        if Q[j][1] == Q[j + 1][1]:
            uf.union(Q[j][2], Q[j + 1][2])

    ans = 0
    for vec in uf.all_group_members().values():
        x_points = len(set(P[i][0] for i in vec))
        y_points = len(set(P[i][1] for i in vec))
        ans += x_points * y_points - len(vec)

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind():
    "Either 0-indexed or 1-indexed"

    __slots__ = ["parent"]

    def __init__(self, size):
        self.parent = [-1] * (size + 1)
    
    def find(self, a):
        path = []
        while self.parent[a] > 0:
            path.append(a)
            a = self.parent[a]
        for child in path:
            self.parent[child] = a
        return a

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)

        if a == b:
            return
        else:
            if self.parent[a] == self.parent[b]:
                self.parent[a] = b
                self.parent[b] -= 1
            elif self.parent[a] < self.parent[b]: 
                self.parent[b] = a
            else:
                self.parent[a] = b 
        
    def same(self, a, b):
        return self.find(a) == self.find(b)

    
    
    
    
    
    
    
    
    
    
    
    
    


    

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


xs_decode, ys_decode = map(sorted, map(set, zip(*xys)))
xs_encode = {x: i for i, x in enumerate(xs_decode)}
ys_encode = {y: i for i, y in enumerate(ys_decode, start=len(xs_decode))}

uf = UnionFind(len(xs_decode) + len(ys_decode))
for x, y in xys:
    i = xs_encode[x]
    j = ys_encode[y]
    uf.union(i, j)

ancestor2group = dict()
for i in range(len(xs_decode) + len(ys_decode)):
    a = uf.find(i)
    if a in ancestor2group:
        ancestor2group[a].append(i)
    else:
        ancestor2group[a] = [i]

ans = 0
for group in ancestor2group.values():
    xs_count = 0
    ys_count = 0
    for elem in group:
        if elem < len(xs_decode):
            xs_count += 1
        else:
            ys_count += 1
    ans += xs_count * ys_count

ans -= len(xys)

print(ans)

Solution (Python):
class UnionFind:
    
    def __init__(self,n):
        self.p = [i for i in range(n)]
        self.component = n
    
    def root(self,x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def unite(self,x,y):
        x,y = self.root(x),self.root(y)
        if x != y:
            self.p[x] = y
            self.component -=1
    
    def same(self,x,y):
        return (self.root(x)==self.root(y))

n = int(input())
MAX = 100010
UF = UnionFind(2*MAX)
for _ in range(n):
    x,y = map(int,input().split())
    UF.unite(x,y+MAX)

cnt_x,cnt_y = [0]*2*MAX,[0]*2*MAX

for i in range(MAX):
    cnt_x[UF.root(i)] += 1


for i in range(MAX,2*MAX):
    cnt_y[UF.root(i)] += 1

print(sum(cnt_x[i]*cnt_y[i] for i in range(2*MAX))-n)

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

N = int(input())
vertex = set()
conn = [[] for _ in range(2*10**5 + 1)]
check = [False]*(2*10**5 + 1)
for i in range(N):
    x, y = [int(x) for x in input().split()]
    vertex.add(x)
    vertex.add(y + 10**5)
    conn[x].append(y + 10**5)
    conn[y + 10**5].append(x)

count = [0] * 2
def dfs(z):
    if check[z] == True:
        return
    check[z] = True
    if z <= 10**5:
        count[0] += 1
    else:
        count[1] += 1
    for w in conn[z]:
        dfs(w)

ans = 0
for z in vertex:
    if check[z] == False:
        count = [0]*2
        dfs(z)
        X, Y = count[0], count[1]
        ans += X * Y
ans -= N

print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N = I()
data = ILL(N)

Xs = DD(list)
Ys = DD(list)

for i in range(N):
  x,y = data[i]
  Xs[x].append(i)
  Ys[y].append(i)


state = [0 for i in range(N)]
Q = list(range(N))

ans = 0
while Q:
  s = Q.pop()
  if state[s]: continue
  activex = {data[s][0]}
  activey = {data[s][1]}
  q = [s]
  state[s] = 1
  while q:
    x = q.pop()
    for xx in Xs[data[x][0]]:
      if state[xx]: continue
      state[xx] = 1
      activex.add(data[xx][0])
      activey.add(data[xx][1])
      q.append(xx)
    for xx in Ys[data[x][1]]:
      if state[xx]: continue
      state[xx] = 1
      activex.add(data[xx][0])
      activey.add(data[xx][1])
      q.append(xx)
  ans += len(activex)*len(activey)
  
print(ans-N)

Solution (Python):
n=int(input())
xy=[]
X=[]
Y=[]
for _ in range(n):
  x,y=map(int,input().split())
  xy.append([x,y])
  X.append(x)
  Y.append(y)
X=list(set(X))
Y=list(set(Y))
X.sort()
Y.sort()
from bisect import bisect_left
xy=[[bisect_left(X,x),bisect_left(Y,y)] for x,y in xy]
mx=0
my=0
for x,y in xy:
  mx=max(mx,x)
  my=max(my,y)
mx,my=mx+1,my+1
bg=[[] for _ in range(mx+my)]
for x,y in xy:
  y+=mx
  bg[x].append(y)
  bg[y].append(x)
mi=set(range(mx+my))
ren=[]
while mi:
  todo=[mi.pop()]
  rx,ry=0,0
  while todo:
    v=todo.pop()
    if v<mx:
      rx+=1
    else:
      ry+=1
    for nv in bg[v]:
      if nv in mi:
        todo.append(nv)
        mi.discard(nv)
  ren.append([rx,ry])
ans=0
for rx,ry in ren:
  ans+=rx*ry
ans-=n
print(ans)

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

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

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

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N = int(input())
xtoy = [-1]*(10**5+1)
uf = UnionFind(10**5+1)
xy = []
for i in range(N):
    x,y = map(int,input().split())
    if xtoy[x] == -1:
        xtoy[x] = y
    xy.append((x,y))
for x,y in xy:
    uf.union(y,xtoy[x])
ans = -N
for i in range(10**5+1):
    if xtoy[i] != -1:
        ans += uf.size(xtoy[i])
print(ans)

Solution (Python):
import sys
from collections import deque
from operator import itemgetter
input = sys.stdin.readline

def main():
    n = int(input())
    p = [list(map(int, input().split()))+[i] for i in range(n)]
    tree = [[] for _ in range(n)]
    
    p.sort()
    for i in range(n-1):
        if p[i][0] == p[i+1][0]:
            tree[p[i][2]].append(p[i+1][2])
            tree[p[i+1][2]].append(p[i][2])

    p.sort(key=itemgetter(1))
    for i in range(n-1):
        if p[i][1] == p[i+1][1]:
            tree[p[i][2]].append(p[i+1][2])
            tree[p[i+1][2]].append(p[i][2])

    p.sort(key=itemgetter(2))

    
    already = [False]*n
    ans = -n
    for i in range(n):
        if already[i]:
            continue
        already[i] = True
        not_yet = deque([i])
        key_x = {p[i][0]}
        key_y = {p[i][1]}
        while not_yet:
            key = not_yet.popleft()
            for v in tree[key]:
                if already[v]:
                    continue
                already[v] = True
                key_x.add(p[v][0])
                key_y.add(p[v][1])
                not_yet.append(v)
        ans += len(key_x)*len(key_y)
    
    print(ans)
        
    
    
if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
import sys


sys.setrecursionlimit(10 ** 6)


def main():
    N = int(input())
    V = 100005
    to = defaultdict(list)
    for _ in range(N):
        X, Y = map(int, input().split())
        Y += V
        to[X].append(Y)
        to[Y].append(X)
    visited = [0] * (2 * V)
    cnt = [0] * 2  

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

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readlines = sys.stdin.buffer.readlines
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)


def main():
    OFS = 100005
    N = int(input())
    G = [[] for _ in [0]*OFS*2]
    for line in readlines():
        x, y = map(int, line.split())
        y += OFS
        G[x].append(y)
        G[y].append(x)

    def dfs(v):
        if v < OFS:
            counter[0] += 1
        else:
            counter[1] += 1

        for u in G[v]:
            if visited[u]:
                continue
            visited[u] = 1
            dfs(u)

    visited = [0]*OFS*2
    ans = 0
    for i in range(OFS):
        if visited[i]:
            continue
        counter = [0]*2
        visited[i] = 1
        dfs(i)
        ans += counter[0] * counter[1]

    print(ans - N)


if __name__ == '__main__':
    main()

Solution (Python):

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

(n,), *q = [[*map(int,o.split())] for o in open(0)]
MAX = 10 ** 5 + 1
UF = UnionFind(2 * MAX)
for x, y in q:
    UF.union(x, y + MAX)
cnt_x = [0] * (2 * MAX)
cnt_y = cnt_x[:]
for i in range(MAX):
    cnt_x[UF.find(i)] += 1
    cnt_y[UF.find(i + MAX)] += 1
print(sum(X * Y for X, Y in zip(cnt_x, cnt_y)) - n)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    """
    二部グラフに変換，x,yそれぞれのグループにわけ，座標の値を点で，点の情報を辺で表す．
    連結成分の中で全部辺を繋ぐ
    """
    
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        重いかも！　　members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        重いかも！　all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

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

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

            if x == y:
                return

            if self.parents[x] > self.parents[y]:
                x, y = y, x

            self.parents[x] += self.parents[y]
            self.parents[y] = x

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

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

        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}

        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    
    
    M=10**5
    N=I()
    
    uf=UnionFind(2*M)
    for i in range(N):
        x,y=MI()
        x-=1
        y-=1
        y+=M
        uf.union(x,y)
        
    from collections import defaultdict
    ddx = defaultdict(int)
    ddy = defaultdict(int)
    
    for i in range(M):
        root=uf.find(i)
        ddx[root]+=1
        
        root=uf.find(i+M)
        ddy[root]+=1
        
    ans=-N
    
    roots=uf.roots()

    
    for v in roots:
        x=ddx[v]
        y=ddy[v]
        ans+=x*y
        
    print(max(ans,0))
    
    
    

main()

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

class UnionFind():
    def __init__(self,num):
        self.n = num         
        self.parents = [-1 for i in range(self.n)]
          

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

    
    
    def union(self,x,y):
        xx=self.find(x)  
        yy=self.find(y)  
        if xx==yy:
            return     
        else:
            size_xx=abs(self.parents[xx]) 
            size_yy=abs(self.parents[yy]) 
            if size_xx>size_yy:
                xx,yy=yy,xx  

            self.parents[yy]+=self.parents[xx] 
            self.parents[xx]=yy   

    
    def size(self,x):
        xx=self.find(x)
        return abs(self.parents[xx])

    
    def same(self,x,y):
        return 1 if self.find(x)==self.find(y) else 0

    
    def members(self,x):
        xx=self.find(x)
        return [i for i in range(self.n) if self.find(i)==xx]
             

    
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x < -1]
        

    
    def all_group_members(self):
        return {r:self.members(r) for r in self.roots()}

    
    def state_grouping(self):
        return list(self.all_group_members().values())

    
    def __str__(self):
        return "\n".join("{}: {}".format(r,self.members(r)) for r in self.roots())
        
        
        
        

uf=UnionFind(2*10**5)
ans=0


for i in range(n):
    x,y=map(int,input().split())
    x-=1;y-=1;y+=10**5
    uf.union(x,y)
for p in uf.roots():
    l=uf.members(p) 
    tem= len([i for i in l if i>=10**5])
    ans+= (len(l)-tem)*tem
    
print(ans-n)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.components = n  

    def root(self, x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.p[x] = y
            self.components -= 1
    
    def same(self, x,y):
        return (self.root(x) == self.root(y))

N = int(input())
MAX = 100010
UF = UnionFind(2*MAX)

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


cnt_x, cnt_y = [0]*(2*MAX), [0]*(2*MAX)

for i in range(MAX):
    cnt_x[UF.root(i)] += 1

for i in range(MAX,2*MAX):
    cnt_y[UF.root(i)] += 1

print(sum([cnt_x[i]*cnt_y[i] for i in range(2*MAX)]) - N)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.components = n  

    def root(self, x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.p[x] = y
            self.components -= 1
    
    def same(self, x,y):
        return (self.root(x) == self.root(y))

N = int(input())
MAX = 100010
UF = UnionFind(2*MAX)

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


cnt_x, cnt_y = [0]*(2*MAX), [0]*(2*MAX)

for i in range(MAX):
    cnt_x[UF.root(i)] += 1

for i in range(MAX,2*MAX):
    cnt_y[UF.root(i)] += 1

print(sum([cnt_x[i]*cnt_y[i] for i in range(2*MAX)]) - N)

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

pos_max = 100000

dic = dict()

for _ in range(n):
    x, y = map(int, input().split())
    y += pos_max
    if not x in dic:
        dic[x] = set()
    if not y in dic:
        dic[y] = set()
    dic[x].add(y)
    dic[y].add(x)
checked = set()

count = 0
for x in dic:
    if x in checked:
        continue
    checked.add(x)

    member = {x}
    next_items = {x}
    while next_items:
        v = next_items.pop()
        member |= dic[v]
        next_items |= dic[v] - checked
        checked |= dic[v]
    x_n = sum(w <= pos_max for w in member)
    y_n = sum(w >  pos_max for w in member)
    count += x_n * y_n
print(count - n)

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
xy = map(int, read().split())
XY = zip(xy, xy)

max_num = 10 ** 5
delta = 10 ** 5 + 10

graph = [[] for _ in range(max_num + delta + 1)]

for x, y in XY:
    graph[x].append(delta + y)
    graph[delta + y].append(x)

x_used = [False] * (max_num + 1)
y_used = [False] * (max_num + 1)


def dfs(idx):
    x_res = 0
    y_res = 0
    edgenum = 0
    stack = []
    stack.append(idx)
    if idx >= delta:
        y_used[idx % delta] = True
    else:
        x_used[idx] = True
    while stack:
        v = stack.pop()
        if v >= delta:
            
            
            
            y_res += 1
        else:
            
            
            
            x_res += 1
        for u in graph[v]:
            if u >= delta:
                if y_used[u % delta]:
                    continue
                y_used[u % delta] = True
            else:
                if x_used[u]:
                    continue
                x_used[u] = True
            edgenum += 1
            stack.append(u)
    res = x_res * y_res
    return res


ans = 0
for i in range(max_num + 1):
    if x_used[i]:
        continue
    temp = dfs(i)
    ans += temp

for i in range(max_num + 1):
    if y_used[i]:
        continue
    i += delta
    temp = dfs(i)
    ans += temp

print(ans - n)