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

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



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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 = 10 ** 9 + 7


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



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



X = [0] * 10 ** 5 * 2
Y = [0] * 10 ** 5 * 2
for x in range(10 ** 5):
    X[U.root(x)] += 1
for y in range(10 ** 5, 10 ** 5 * 2):
    Y[U.root(y)] += 1


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


print(ret - n)

Solution (Python):
def main():
    MAX = 10 ** 5 + 1

    data = [-1] * (2 * MAX)

    def find(x):
        if data[x] < 0:
            return x
        else:
            data[x] = find(data[x])
            return data[x]

    def union(x, y):
        x, y = find(x), find(y)
        if x != y:
            if data[y] < data[x]:
                x, y = y, x
            data[x] += data[y]
            data[y] = x
        return (x != y)


    N, *XY = map(int, open(0).read().split())

    for x, y in zip(*[iter(XY)] * 2):
        union(x, y + MAX)

    X = [0] * (MAX * 2)
    Y = [0] * (MAX * 2)

    for i in range(MAX):
        X[find(i)] += 1
    for i in range(MAX, MAX * 2):
        Y[find(i)] += 1

    res = sum(X[i] * Y[i] for i in range(MAX * 2))

    print(res - N)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter


def main():
    MAX = 10 ** 5 + 1

    data = [-1] * (2 * MAX)

    def find(x):
        if data[x] < 0:
            return x
        else:
            data[x] = find(data[x])
            return data[x]

    def union(x, y):
        x, y = find(x), find(y)
        if x != y:
            if data[y] < data[x]:
                x, y = y, x
            data[x] += data[y]
            data[y] = x
        return (x != y)


    N, *XY = map(int, open(0).read().split())

    for x, y in zip(*[iter(XY)] * 2):
        union(x, y + MAX)

    X = Counter(find(i) for i in range(MAX))
    Y = Counter(find(i) for i in range(MAX, MAX * 2))
    res = sum(X[i] * Y[i] for i in range(MAX * 2))

    print(res - N)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter


def main():
    class UnionFind:
        def __init__(self, size):
            self.data = [-1] * size

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

        def union(self, x, y):
            x, y = self.find(x), self.find(y)
            if x != y:
                if self.data[y] < self.data[x]:
                    x, y = y, x
                self.data[x] += self.data[y]
                self.data[y] = x
            return (x != y)

    MAX = 10 ** 5 + 1
    uf = UnionFind(2 * MAX)

    N, *XY = map(int, open(0).read().split())

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

    X = Counter(uf.find(i) for i in range(MAX))
    Y = Counter(uf.find(i) for i in range(MAX, MAX * 2))
    res = sum(X[i] * Y[i] for i in range(MAX * 2))

    print(res - N)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter


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

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)

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

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


def main():
    MAX = 10 ** 5 + 1
    uf = UnionFind(2 * MAX)

    N, *XY = map(int, open(0).read().split())

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

    X = Counter(uf.find(i) for i in range(MAX))
    Y = Counter(uf.find(i) for i in range(MAX, MAX * 2))
    res = sum(X[i] * Y[i] for i in range(MAX * 2))

    print(res - N)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter

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

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)

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

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


MAX = 10 ** 5 + 10
uf = UnionFind(2 * MAX)

N, *XY = map(int, open(0).read().split())

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

X = Counter(uf.find(i) for i in range(MAX))
Y = Counter(uf.find(i) for i in range(MAX, MAX * 2))
res = sum(X[i] * Y[i] for i in range(MAX * 2))

print(res - N)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

"""
点(x,y) を、辺x-yと見て二部グラフとみなす
"""

N = int(readline())
XY = np.array(read().split(),np.int32)

U = 10**5 + 100
X = XY[::2]; Y = XY[1::2]
graph = csr_matrix((np.ones(N),(X,Y+U)),(U+U,U+U))
Ncomp,comp = connected_components(graph)

comp_x=np.bincount(comp[:U],minlength=Ncomp) 
comp_y=np.bincount(comp[U:],minlength=Ncomp) 
comp_E=np.bincount(comp[X],minlength=Ncomp) 

answer = (comp_x * comp_y - comp_E).sum()
print(answer)

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


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


def main():
    N = int(input())
    xy_list = []
    x_list = []
    y_list = []
    for i in range(N):
        x, y = map(int, input().split())
        xy_list.append((x, y))
        x_list.append(x)
        y_list.append(y)

    x_list = list(set(x_list))
    y_list = list(set(y_list))
    x_list.sort()
    y_list.sort()
    dictX = {}
    dictY = {}
    for i, x in enumerate(x_list):
        dictX[x] = i
    for i, y in enumerate(y_list):
        dictY[y] = i

    xy_c = [[] for _ in range(len(x_list))]
    for x, y in xy_list:
        xc, yc = dictX[x], dictY[y]
        xy_c[xc].append(yc)

    UF = UnionFind(len(y_list) + 1)
    for i in range(len(x_list)):
        j_list = xy_c[i]
        if len(j_list) > 1:
            j0 = j_list[0]
            for j in j_list[1:]:
                UF.unite(j0, j)

    ans = 0
    for i in range(len(x_list)):
        j0 = xy_c[i][0]
        ans += UF.size(j0) - len(xy_c[i])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n, = [int(x) for x in input().split(" ")]
dx = [set() for x in range(10**5+1)]
dy = [set() for x in range(10**5+1)]

class UnionFindNode:
    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1
        self.member_num_ = 1
        self.x_num = 0

    def is_root(self):
        return not self.parent_

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

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

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

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

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

for i in range(n):
    x, y = [int(x) for x in input().split(" ")]
    dx[x].add(y)
    dy[y].add(x)

node_list = [UnionFindNode(i) for i in range(len(dy))]

for xi, dxx in enumerate(dx):
    b = None
    for y in dxx:
        if b == None:
            b = y
            continue
        node_list[y].unite(node_list[b])
        b = y

r = 0
for xi, dxx in enumerate(dx):
    if len(dxx) == 0:
        continue
    r += node_list[dxx.pop()].root().member_num_ 

print(r-n)

Solution (Python):
import sys
from collections import defaultdict
import queue

n = int(sys.stdin.readline())

graph = defaultdict(list)

X, Y = [[] for i in range(n)], [[] for i in range(n)]
atX, atY = defaultdict(list), defaultdict(list)

for i in range(n):
	a, b = map(int, sys.stdin.readline().split())
	a -= 1; b-= 1
	X[i] = a; Y[i] = b
	atX[X[i]].append(i)
	atY[Y[i]].append(i)

visX = set(); visY = set()
found = [False]*n

ans = n*(-1)
for root in range(n):
	if found[root]: continue
	usedX, usedY = set(), set()

	que = queue.Queue()
	que.put(root)
	found[root] = True
	usedX.add(X[root])
	usedY.add(Y[root])

	while not que.empty():
		cur = que.get()
		toVisit = []
		if X[cur] not in visX:
			visX.add(X[cur])
			for ele in atX[X[cur]]:
				toVisit.append(ele)
		if Y[cur] not in visY:
			visY.add(Y[cur])
			for ele in atY[Y[cur]]:
				toVisit.append(ele)

		for ele in toVisit:
			if found[ele]: continue
			found[ele] = True
			usedX.add(X[ele])
			usedY.add(Y[ele])
			que.put(ele)
	ans += len(usedX)*len(usedY)
print(ans)

Solution (Python):
n = int(input())
p = [list(map(int, input().split())) for _ in range(n)]
adj = [[] for _ in range(200000)]
for x, y in p:
	adj[x-1].append(y+99999)
	adj[y+99999].append(x-1)

visited = [False for _ in range(200000)]

def dfs(orig):
	stack = [orig]
	edges = len(adj[orig])
	if orig < 100000:
		x_num, y_num = 1, 0
	else:
		x_num, y_num = 0, 1

	while stack:
		v = stack.pop()
		for w in adj[v]:
			if visited[w] == False:
				visited[w] = True
				if w < 100000:
					x_num += 1
				else:
					y_num += 1
				edges += len(adj[w])
				stack.append(w)
	return x_num * y_num - (edges // 2)

ans = 0
for i in range(200000):
	if visited[i] == False and adj[i]:
		visited[i] = True
		ans += dfs(i)
print(ans)

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

m = 10**5

edge = [[] for i in range(2*m)]

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

used = [False]*2*m

res = 0

for e in range(m):
    if used[e]:
        continue
    used[e] = True
    tank = []
    new = [e]

    px = 0
    py = 0

    if e >= 10**5:
        py += 1
    else:
        px += 1

    while len(new) > 0:
        tank = []
        for fr in new:
            for go in edge[fr]:
                if not used[go]:
                    tank.append(go)
                    used[go] = True
                    if go >= 10**5:
                        py += 1
                    else:
                        px += 1

        new = tank
    
    res += px*py
print(res-n)

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


class UnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
    def find(self, x):
        if self.pars[x] == x: return x
        else:
            self.pars[x] = self.find(self.pars[x])
            return self.pars[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
        else:
            self.pars[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)

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

UF = UnionFind(N)
for k in range(2):
    xys.sort(key=itemgetter(k))
    for i in range(N-1):
        if xys[i][k] == xys[i+1][k]:
            UF.union(xys[i][2], xys[i+1][2])

Xs = defaultdict(set)
Ys = defaultdict(set)
for x, y, i in xys:
    no = UF.find(i)
    Xs[no].add(x)
    Ys[no].add(y)

ans = 0
for no in Xs.keys():
    ans += len(Xs[no]) * len(Ys[no])

print(ans - N)

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


class UnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
    def find(self, x):
        if self.pars[x] == x: return x
        else:
            self.pars[x] = self.find(self.pars[x])
            return self.pars[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
        else:
            self.pars[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)

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

M = 10**5
UF = UnionFind(2*M)
for x, y in xys:
    x, y = x-1, y-1
    UF.union(x, y+M)

for x in range(2*M):
    UF.find(x)

cntX = Counter(UF.pars[:M])
cntY = Counter(UF.pars[M:])

ans = 0
for v in cntX.keys():
    ans += cntX[v] * cntY[v]

print(ans - N)

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

n = int(input())
xy = [[[] for _ in range(10**5+1)] for __ in range(2)]

for _ in range(n):
    x,y = map(int,input().split())
    xy[0][x].append(y)
    xy[1][y].append(x)

ans = 0
used = [[False for _ in range(10**5+1)] for __ in range(2)]

def dfs(i,flag):
    for v in xy[flag][i]:
        if not used[1-flag][v]:
            used[1-flag][v] = True
            dfs(v,1-flag)
            count[1-flag] += 1

for i in range(10**5+1):
    if xy[0][i] and not used[0][i]:
        used[0][i] = True
        count = [1,0]
        dfs(i,0)
        ans += count[0]*count[1]

ans -= n
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
from collections import defaultdict
import math
mod = 10**9 + 7
def I(): return int(input())
def II(): return map(int, input().split())
def L(): return list(map(int, input().split()))
def TWO(M):
  L=[0]*M
  R=[0]*M
  for i in range(M):
    L[i],R[i] = II()
  return L, R

class UF(object):
  def __init__(self, n=1):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ in range(n)]
    self.size = [1 for _ in range(n)]

  def find(self, x):
    """
    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 と 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[y] = x
      self.size[x] += self.size[y]

  def is_same(self, x, y):
    """
    x と y が同じグループか否か
    """
    return self.find(x) == self.find(y)

  def get_size(self, x):
    """
    x が属するグループの要素数
    """
    x = self.find(x)
    return self.size[x]

N = I()
x,y = TWO(N)
G = UF(N)


X = defaultdict(list)
Y = defaultdict(list)
for i in range(N):
  X[x[i]].append(i)
  Y[y[i]].append(i)


for v in X.values():
  if len(v)==1:
    continue
  for i in v[1:]:
    G.union(v[0],i)
  

for v in Y.values():
  if len(v)==1:
    continue
  for i in v[1:]:
    G.union(v[0],i)


X2 = defaultdict(set)
Y2 = defaultdict(set)
for i in range(N):
  root = G.find(i)
  X2[root].add(x[i])
  Y2[root].add(y[i])


checked = [False]*N
ans = -N
for i in range(N):
  root = G.find(i)
  if checked[root] == True:
    continue
  checked[root] = True
  ans += len(X2[root])*len(Y2[root])
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(pow(10, 6))

xedges = [[] for _ in range(100001)]
yedges = [[] for _ in range(100001)]
xvisited = [False for _ in range(100001)]
yvisited = [False for _ in range(100001)]

def dfs(i, xy):
  if xy == 0:
    xvisited[i] = True
  else:
    yvisited[i] = True
  xc, yc, ec = (xy+1)%2, xy%2, 0
  if xy == 0:
    ec += len(xedges[i])
    for toy in xedges[i]:
      if not yvisited[toy]:
        _xc, _yc, _ec = dfs(toy, 1)
        xc += _xc
        yc += _yc
        ec += _ec
  else :
    ec += len(yedges[i])
    for tox in yedges[i]:
      if not xvisited[tox]:
        _xc, _yc, _ec = dfs(tox, 0)
        xc += _xc
        yc += _yc
        ec += _ec
  return xc, yc, ec

def main():
  n = int(input())
  for _ in range(n):
    x, y = map(int, input().split())
    xedges[x].append(y)
    yedges[y].append(x)

  ans = 0
  for i in range(1, 100001):
    if not xvisited[i] and len(xedges[i]) != 0:
      xc, yc, ec = dfs(i, 0)
      ans += xc*yc-ec//2
    elif not yvisited[i] and len(yedges[i]) != 0:
      xc, yc, ec = dfs(i, 1)
      ans += xc*yc-ec//2

  print(ans)


if __name__ == '__main__':
  main()

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:
            x, y = y, x
        self.v[x] += self.v[y]
        self.v[y] = x

    def root(self, x):
        return self.v[x] < 0

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


mx = 10 ** 5 + 10

n = int(input())

uf = UnionFind(mx * 2)

for _ in range(n):
    x, y = map(int, input().split())
    uf.unite(x, y + mx)

vx = [0] * (mx * 2)
vy = [0] * (mx * 2)

for i in range(mx):
    root = uf.find(i)
    vx[root] += 1

for i in range(mx, mx * 2):
    root = uf.find(i)
    vy[root] += 1

ans = -n
for xx, yy in zip(vx, vy):
    ans += xx * yy
print(ans)

Solution (Python):
from queue import PriorityQueue
import sys

sys.setrecursionlimit(10**9)

IA = lambda: [int(x) for x in input().split()]
IM = lambda N: [IA() for _ in range(N)]


N=100005
fa=[int(0) for i in range(2*(N+1))]
xNum=[int(0) for i in range(2*(N+1))]
yNum=[int(0) for i in range(2*(N+1))]

def find(x):
    if(x==fa[x]):return x
    else:
        fa[x]=find(fa[x])
        return fa[x]

n=input()
n=int(n)

for i in range(2*N+1):
    fa[i]=i

for i in range(n):
    x,y=IA()
    y+=N
    fx=int(find(x))
    fy=int(find(y))
 
    if(fx!=fy):
        fa[fy]=fx
for i in range(N):
    xNum[find(i)]+=1
for i in range(N):
    yNum[find(i+N)]+=1
ans=0
for i in range(N):
    ans+=xNum[i]*yNum[i]
print(ans-n)

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

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

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

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

if __name__ == '__main__':
    maxxy = 10**5
    N = int(input())
    ds = DisjointSet(maxxy*2+1)
    left = [0 for i in range(maxxy*2+1)]
    right = [0 for i in range(maxxy*2+1)]
    for i in range(N):
        x, y = map(int, input().split())
        ds.unite(x, maxxy+y)
    for i in range(maxxy+1):
        left[ds.findSet(i)] += 1
    for i in range(maxxy+1, maxxy*2+1):
        right[ds.findSet(i)] += 1
    ans = 0
    for i in range(maxxy*2+1):
        ans += left[i] * right[i]
    ans -= N
    print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n: int) -> None:
        
        self.nodes = [-1]*n
 
    def find_root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find_root(self.nodes[x])
            return self.nodes[x]
 
    def unite(self, x: int, y: int) -> None:
        x, y = self.find_root(x), self.find_root(y)
        
        if (x != y):
            if (x < y):
                self.nodes[y] += self.nodes[x]
                self.nodes[x] = y
            else:
                self.nodes[x] += self.nodes[y]
                self.nodes[y] = x
                
    def get_num(self, x: int) -> int:
        return -(self.nodes[x])

MAX = 10**5+1

N = int(input())
uf = UnionFind(2*MAX)

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


num_x = [0]*2*MAX
num_y = [0]*2*MAX
for i in range(MAX):
  num_x[uf.find_root(i)] += 1
  num_y[uf.find_root(i+MAX)] += 1
  

ans = 0
for i in range(2*MAX):
  ans += num_x[i] * num_y[i]

print(ans - N)

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
v = 100005
visited = [False]*(2*v)
count = [0, 0]

def dfs(a):
    visited[a] = True
    count[a//v] += 1
    for i in vertex[a]:
        if not visited[i]:
            dfs(i)

input = sys.stdin.readline
N = int(input())
vertex = [[] for _ in range(v*2)]
for _ in range(N):
    x, y=map(int, input().split())
    y += v
    vertex[x].append(y)
    vertex[y].append(x)

ans = 0
for i in range(v):
    if not visited[i]:
        count = [0, 0]
        dfs(i)
        ans += count[0]*count[1]

print(ans-N)

Solution (Python):
from itertools import groupby
from operator import itemgetter

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


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

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

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

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




uft = UnionFindTree(N)
for d in range(2):
    for _, g in groupby(
                sorted(
                    zip(
                        x,
                        y,
                        range(1, N + 1)
                    ),
                    key=itemgetter(d)
                ),
                key=itemgetter(d)
            ):
        p = list(g)
        for (_, _, i), (_, _, j) in zip(p[1:], p):
            uft.union(i, j)
ans = sum(
    len({x for x, _, _ in C}) * len({y for _, y, _ in C}) - len(list(C))
    for C in (
        list(g)
        for _, g in groupby(
            sorted(
                (
                    (x, y, uft.find(i))
                    for x, y, i in zip(
                        x,
                        y,
                        range(1, N + 1)
                    )
                ),
                key=itemgetter(2)
            ),
            key=itemgetter(2)
        )
    )
)

print(ans)

Solution (Python):
from itertools import groupby
from operator import itemgetter

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


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

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

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

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




uft = UnionFindTree(N)
for d in range(2):
    for _, g in groupby(
                sorted(
                    zip(
                        x,
                        y,
                        range(1, N + 1)
                    ),
                    key=itemgetter(d)
                ),
                key=itemgetter(d)
            ):
        p = list(g)
        for (_, _, i), (_, _, j) in zip(p[1:], p):
            uft.union(i, j)
ans = sum(
    len({x for x, _, _ in C}) * len({y for _, y, _ in C}) - len(list(C))
    for C in (
        list(C)
        for _, C in groupby(
            sorted(
                (
                    (x, y, uft.find(i))
                    for x, y, i in zip(
                        x,
                        y,
                        range(1, N + 1)
                    )
                ),
                key=itemgetter(2)
            ),
            key=itemgetter(2)
        )
    )
)

print(ans)

Solution (Python):
import sys
from collections import defaultdict, deque
readline = sys.stdin.readline
N = int(readline())
P = defaultdict(list); Q = defaultdict(list)
for i in range(N):
    x, y = map(int, readline().split())
    P[x].append(y)
    Q[y].append(x)
X = set(); Y = set()

res = 0
que = deque()
for x in P:
    que.append((0, x))
    X.add(x)
    cx = 1; cy = 0
    while que:
        t, v = que.popleft()
        if t:
            for x in Q[v]:
                if x in X:
                    continue
                X.add(x)
                que.append((0, x))
                cx += 1
        else:
            for y in P[v]:
                if y in Y:
                    continue
                Y.add(y)
                que.append((1, y))
                cy += 1
    res += cx * cy
print(res - N)

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

MAXVAL = 10**5
N = int(input())
edge = [[] for _ in range(MAXVAL*2)]
visited = [0] * (MAXVAL*2)
ans = 0
xnum = 0; ynum = 0; nodes = 0

def dfs(n):
    global xnum, ynum, nodes
    if visited[n] == 1:
        return True
    if n < MAXVAL:
        xnum += 1
    else:
        ynum += 1
    visited[n] = 1
    for item in edge[n]:
        nodes += 1
        dfs(item)
    return True

for i in range(N):
    x, y = [int(item) for item in input().split()]
    x -= 1; y -= 1
    edge[x].append(y+MAXVAL)
    edge[y+MAXVAL].append(x)

for i in range(MAXVAL*2):
    if visited[i] == 1:
        continue
    xnum = 0; ynum = 0; nodes = 0
    dfs(i)
    if nodes >= 3:
        ans += xnum * ynum - nodes // 2
print(ans)