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):
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    M = 10 ** 5

    N = int(input())

    g = tuple(set() for _ in range(M * 2))
    ps = set()
    for _ in range(N):
        x, y = (int(x) - 1 for x in input().split())  
        g[x].add(y + M)
        g[y + M].add(x)
        ps.add(x)
        ps.add(y + M)

    visited = [0] * (M * 2)
    ans = 0
    for s in ps:
        if visited[s]: continue
        visited[s] = 1
        dq = deque()
        dq.append(s)

        sz = 0
        x = 0
        while dq:
            v = dq.popleft()
            sz += 1
            if v < M:
                x += 1
            for u in g[v]:
                if visited[u]: continue
                visited[u] = 1
                dq.append(u)
        ans += (sz - x) * x

    ans -= N

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    M = 10 ** 5

    N = int(input())

    g = tuple(set() for _ in range(M * 2))
    for _ in range(N):
        x, y = (int(x) - 1 for x in input().split())  
        g[x].add(y + M)
        g[y + M].add(x)

    visited = [0] * (M * 2)
    ans = 0
    for s in range(M * 2):  
        if visited[s]: continue
        visited[s] = 1
        dq = deque()
        dq.append(s)

        sz = 0
        x = 0
        while dq:
            v = dq.popleft()
            sz += 1
            if v < M:
                x += 1
            for u in g[v]:
                if visited[u]: continue
                visited[u] = 1
                dq.append(u)
        ans += (sz - x) * x

    ans -= N

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    M = 10 ** 5

    N = int(input())

    g = tuple(set() for _ in range(M * 2))
    for _ in range(N):
        x, y = (int(x) - 1 for x in input().split())  
        g[x].add(y + M)
        g[y + M].add(x)

    visited = [0] * (M * 2)
    ans = 0
    for s in range(M * 2):
        if visited[s]: continue
        visited[s] = 1
        dq = deque()
        dq.append(s)

        sz = 0
        x = 0
        e = 0
        while dq:
            v = dq.popleft()
            sz += 1
            if v < M:
                x += 1
            for u in g[v]:
                e += 1
                if visited[u]: continue
                visited[u] = 1
                dq.append(u)
        ans += (sz - x) * x - (e // 2)
        

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n = int(input())
v = 10**5+2
e = [[] for i in range(2*v)]
for i in range(n):
    x,y = map(int,input().split())
    y += v
    e[x].append(y)
    e[y].append(x)
visit = [0]*(2*v)
def dfs(x):
    if not visit[x]:
        visit[x] = 1
        count[x//v] += 1
        for nex in e[x]:
            dfs(nex)
ans = 0
for i in range(v):
    if not visit[i]:
        count = [0]*2
        dfs(i)
        ans += count[0]*count[1]
print(ans-n)

Solution (Python):


def dfs(v):
    cnt = [0, 0]
    if v < OFFSET:
        cnt[0] += 1
    else:
        cnt[1] += 1
    visited[v] = True
    stack = [v]
    while stack:
        v = stack.pop()
        for nxt_v in graph[v]:
            if visited[nxt_v]:
                continue
            if nxt_v < OFFSET:
                cnt[0] += 1
            else:
                cnt[1] += 1
            visited[nxt_v] = True
            stack.append(nxt_v)
    return cnt[0] * cnt[1]

n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
OFFSET = 10 ** 5

graph = [[] for i in range(2 * OFFSET)]
for x, y in info:
    x -= 1
    y -= 1
    y += OFFSET
    graph[x].append(y)
    graph[y].append(x)

ans = 0
visited = [False] * (2 * OFFSET)
for v in range(2 * OFFSET):
    if visited[v]:
        continue
    else:
        ans += dfs(v)
print(ans - n)

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

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

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

        if root1 == root2:  
            return

        self.componentCount -= 1  

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

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

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

from collections import defaultdict

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

xGrp = defaultdict(list)
yGrp = defaultdict(list)
for i, (x, y) in enumerate(XY):
    xGrp[x].append(i)
    yGrp[y].append(i)

tree = UnionFind(N)
for grp in xGrp.values():
    for l, r in zip(grp, grp[1:]):
        tree.union(l, r)
for grp in yGrp.values():
    for l, r in zip(grp, grp[1:]):
        tree.union(l, r)

xGrpList = defaultdict(set)
yGrpList = defaultdict(set)
for i, (x, y) in enumerate(XY):
    xGrpList[tree.root(i)].add(x)
    yGrpList[tree.root(i)].add(y)

ans = 0
for i in range(N):
    if i != tree.root(i):
        continue
    X, Y = xGrpList[i], yGrpList[i]
    if len(X) + len(Y) < 3:
        continue
    A = len(X) * len(Y)
    ans += A - tree.sizeOfSameRoot(i)
print(ans)

Solution (Python):
class Union_Find():
    def __init__(self, num):
        self.par = [-1]*(num+1)
        self.siz = [1]*(num+1)

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

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

    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
                self.siz[rx] += self.siz[ry]
            elif self.par[rx] > self.par[ry]:
                self.par[rx] = ry
                self.siz[ry] += self.siz[rx]
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
                self.siz[rx] += self.siz[ry]
        return

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

n = int(input())
uf = Union_Find(n)

d = [list(map(int, input().split())) for i in range(n)]
x = [[] for i in range(100001)]
y = [[] for i in range(100001)]

for i in range(n):
    xi, yi = d[i]
    x[xi].append(i+1)
    y[yi].append(i+1)


for i in range(1, 100001):
    for j in range(len(x[i])-1):
        uf.union(x[i][j], x[i][j+1])

for i in range(1, 100001):
    for j in range(len(y[i])-1):
        uf.union(y[i][j], y[i][j+1])

par = [[] for i in range(n+1)]
for i in range(1, n+1):
    par[uf.find(i)].append(d[i-1])

ans = -n
for i in range(1, n+1):
    x = set()
    y = set()
    for xi, yi in par[i]:
        x.add(xi)
        y.add(yi)

    ans += len(x)*len(y)

print(ans)

Solution (Python):
n = int(input())
xy=[list(map(int,input().split())) for i in range(n)]
from collections import defaultdict
x_d = defaultdict(list)
y_d = defaultdict(list)
for i in range(n):
    x,y = xy[i]
    x_d[x].append(i)
    y_d[y].append(i)

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())
uf = UnionFind(n)
for k in x_d.keys():
    if len(x_d[k])==1:
        continue
    last=x_d[k][0]
    for itm in x_d[k]:
        uf.union(last, itm)
        last=itm

for k in y_d.keys():
    if len(y_d[k])==1:
        continue
    last=y_d[k][0]
    for itm in y_d[k]:
        uf.union(last, itm)
        last=itm
ans=0
for root in uf.roots():
    mems = uf.members(root)
    xset=set()
    yset=set()
    for m in mems:
        x,y=xy[m]
        xset.add(x)
        yset.add(y)
    points = len(xset)*len(yset)
    points -= len(mems)
    ans+=points
print(ans)

Solution (Python):
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components
n=int(input())
m=10**5+5
l=[]
lx=[]
for _ in range(n):
    a,b=map(int,input().split())
    l.append((a,b+m,1))
    lx.append(a)
edge=np.array(l,dtype=np.int64).T
graph=csr_matrix(((edge[2],edge[:2]-1)),(2*m,2*m))
n,labels=connected_components(graph)
lx=np.array(lx)
x=np.bincount(labels[:m],minlength=n)
y=np.bincount(labels[m:],minlength=n)
e=np.bincount(labels[lx],minlength=n)
print((x*y-e).sum())

Solution (Python):

import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())

class UnionFind:
    def __init__(self,n):
        self.par=[i for i in range(n)]
        self.siz=[1]*n
        
    def root(self,x):
        while self.par[x]!=x:
            self.par[x]=self.par[self.par[x]]
            x=self.par[x]
        return x
    
    def unite(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.siz[x]<self.siz[y]:
            x,y=y,x
        self.siz[x]+=self.siz[y]
        self.par[y]=x
        return True
    
    def is_same(self,x,y):
        return self.root(x)==self.root(y)
    
    def size(self,x):
        return self.siz[self.root(x)]
MAX=10**5
u=UnionFind(MAX*2)
for _ in range(N):
    x,y=map(int1,input().split())
    u.unite(x,y+MAX)
lx,ly=[0]*MAX*2,[0]*MAX*2
for i in range(MAX):
    lx[u.root(i)]+=1
    ly[u.root(i+MAX)]+=1
ans=0
for i in range(MAX*2):
    ans+=lx[i]*ly[i]
print(ans-N)

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class UnionFind:
    def __init__(self, n: int):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x: int):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x: int, y: int):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        if self.parents[y] < self.parents[x]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x: int):
        return -self.parents[self.find(x)]
    
    def same(self, x: int, y: int):
        return self.find(x) == self.find(y)
    
    def members(self, x: int):
        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())


def solve():
    N = int(rl())
    x, y = [0] * N, [0] * N
    for i in range(N):
        x[i], y[i] = map(int, rl().split())
    MAX_N = 10 ** 5
    
    uf = UnionFind(2 * MAX_N + 1)
    for xi, yi in zip(x, y):
        uf.union(xi, MAX_N + yi)
    
    x_counter = defaultdict(int)
    y_counter = defaultdict(int)
    for xi in range(1, MAX_N + 1):
        if uf.parents[xi] == -1:
            continue
        x_counter[uf.find(xi)] += 1
    for yi in range(MAX_N + 1, 2 * MAX_N + 1):
        if uf.parents[yi] == -1:
            continue
        y_counter[uf.find(yi)] += 1
    
    united = defaultdict(int)
    for xi in x:
        united[uf.find(xi)] += 1
    
    ans = 0
    for key, val in united.items():
        ans += x_counter[key] * y_counter[key] - val
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap



@mt
def slv(N, XY):
    from collections import defaultdict
    g = defaultdict(set)
    yo = 10**6
    V = set()
    for x, y in XY:
        y += yo
        g[x].add(y)
        g[y].add(x)
        V.add(x)
        V.add(y)


    rem = set(v for v in V)
    done = set()
    ans = 0
    while rem:
        u = rem.pop()
        s = [u]
        done.add(u)
        xs = set()
        ys = set()
        if u >= yo:
            ys.add(u)
        else:
            xs.add(u)
        while s:
            u = s.pop()
            if u >= yo:
                ys.add(u)
            else:
                xs.add(u)
            for v in g[u]:
                if v in done:
                    continue
                s.append(v)
                done.add(v)
        rem -= xs
        rem -= ys
        e = 0
        for u in xs:
            e += len(g[u])
        ans += len(xs) * len(ys) - e

    return ans





def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    print(slv(N, XY))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    
    

    n = int(input())
    visited_x = [0]*(10**5+1)
    visited_y = [0]*(10**5+1)
    adj_x = [[] for _ in range(10**5+1)]
    adj_y = [[] for _ in range(10**5+1)]

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

    res = 0
    for x in range(1, 10**5+1):
        if visited_x[x] or not adj_x[x]:
            continue
        visited_x[x] = 1
        vx = 1
        vy = 0
        
        d = deque([[x, 0]])
        while d:
            v, axis = d.popleft()
            if axis == 0:
                for nv in adj_x[v]:
                    if visited_y[nv]:
                        continue
                    visited_y[nv] = 1
                    vy += 1
                    d.append([nv, 1])
            else:
                for nv in adj_y[v]:
                    if visited_x[nv]:
                        continue
                    visited_x[nv] = 1
                    vx += 1
                    d.append([nv, 0])
        res += vx * vy

    print(res-n)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    
    

    n = int(input())
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    
    def unite(x,y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True
    
    def size(x):
        return -par[find(x)]
    
    par = [-1]*(2*10**5+2)
    s = set()
    for _ in range(n):
        x, y = map(int, input().split())
        unite(x, 10**5+y)
        s.add(x)
    
    cnt = Counter()
    for x in s:
        cnt[find(x)] += 1

    res = 0
    for k, v in cnt.items():
        res += v * (size(k)-v)

    print(res-n)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def main():
    N = int(input())
    V = 10 ** 5 + 5
    edge = [[] * (2 * V) for _ in range(2 * V)]
    visited = [False] * (2 * V)
    for i in range(N):
        x, y = map(int, input().split())
        y += V
        edge[x].append(y)
        edge[y].append(x)

    ans = 0
    for i in range(2 * V):
        if visited[i]:
            continue
        cnt = [0,0]
        q = deque([i])
        while q:
            s = q.pop() 
            if visited[s]:
                continue
            visited[s] = True
            cnt[s//V] += 1
            for v in edge[s]:
                if visited[v]:
                    continue
                q.append(v)
        ans += cnt[0] * cnt[1]

    print(ans - N)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class UnionFind(object):
    def __init__(self, n, recursion = False):
        self._par = list(range(n))
        self._size = [1] * n
        self._recursion = recursion

    def root(self, k):
        if self._recursion:
            if k == self._par[k]:
                return k
            self._par[k] = self.root(self._par[k])
            return self._par[k]
        else:
            root = k
            while root != self._par[root]: root = self._par[root]
            while k != root: k, self._par[k] = self._par[k], root
            return root

    def unite(self, i, j):
        i, j = self.root(i), self.root(j)
        if i == j: return False
        if self._size[i] < self._size[j]: i, j = j, i
        self._par[j] = i
        self._size[i] += self._size[j]
        return True

    def is_connected(self, i, j):
        return self.root(i) == self.root(j)

    def size(self, k):
        return self._size[self.root(k)]

def resolve():
    n = int(input())
    uf = UnionFind(n)
    potential = [[1, 1] for _ in range(n)]
    x_to_index = {}
    y_to_index = {}

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

        
        if x in x_to_index and y in y_to_index:
            s = uf.root(x_to_index[x])
            t = uf.root(y_to_index[y])
            xs, ys = potential[s]
            xt, yt = potential[t]
            
            if s == t:
                uf.unite(i, s)
                potential[uf.root(i)] = [xs, ys]
            
            else:
                uf.unite(i, s)
                uf.unite(i, t)
                potential[uf.root(i)] = [xs + xt, ys + yt]
        
        elif x in x_to_index:
            s = uf.root(x_to_index[x])
            xs, ys = potential[s]
            uf.unite(i, s)
            potential[uf.root(i)] = [xs, ys + 1]
        elif y in y_to_index:
            t = uf.root(y_to_index[y])
            xt, yt = potential[t]
            uf.unite(i, t)
            potential[uf.root(i)] = [xt + 1, yt]

        x_to_index[x] = i
        y_to_index[y] = i

    res = -n
    for v in range(n):
        if v != uf.root(v):
            continue
        x, y = potential[v]
        res += x * y

    print(res)
resolve()

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

def bfs(s):
    color[s] = 1
    q = deque([s])
    b, w = 1, 0
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if color[nv]==0:
                color[nv] = -color[v]
                q.append(nv)
                
                if color[nv]==1:
                    b += 1
                else:
                    w += 1
    
    return b*w
                    
N = int(input())
xy, xs, ys = [], [], []

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

xs = list(set(xs))
ys = list(set(ys))
xs.sort()
ys.sort()
idx1 = defaultdict(int)

for i in range(len(xs)):
    idx1[xs[i]] = i

idx2 = defaultdict(int)

for i in range(len(ys)):
    idx2[ys[i]] = i+len(xs)

M = len(xs)+len(ys)
G = [[] for _ in range(M)]

for x, y in xy:
    G[idx1[x]].append(idx2[y])
    G[idx2[y]].append(idx1[x])

color = [0]*M
S = 0

for i in range(M):
    if color[i]==0:
        S += bfs(i)

print(S-N)

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

N = int(input())
U = 10 ** 5
edge = [[] for _ in range(2 * U + 1)]
for _ in range(N):
    x, y = map(int, input().split())
    y += U
    edge[x].append(y)
    edge[y].append(x)

ans = 0
seen = [False] * (2 * U + 1)
for i in range(1, 2 * U + 1):
    if not edge[i] or seen[i]:
        continue
    seen[i] = True
    node = deque([i])
    x = 0
    y = 0
    while node:
        s = node.popleft()
        if s <= U:
            x += 1
        else:
            y += 1
        for t in edge[s]:
            if seen[t]:
                continue
            seen[t] = True
            node.append(t)
    ans += x * y

ans = ans - N
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [None]*n

    def root(self, x):
        if self.parent[x] == None:
            return x
        else:
            return self.root(self.parent[x])

    def union(self, x, y):
        x0 = self.root(x)
        y0 = self.root(y)
        if x0 == y0:
            return
        if x0 > y0:
            x0, y0 = y0, x0
        self.parent[y0] = x0


n = int(input())
m = 10**5
uf = UnionFind(2*m)
X, Y = [], []
for i in range(n):
    x, y = map(int, input().split())
    X.append(x-1)
    Y.append(y-1+m)
    uf.union(x-1, y-1+m)
R = {}
for x, y in zip(X, Y):
    r = uf.root(x)
    try:
        R[r][0].add(x)
        R[r][1].add(y)
    except:
        R[r] = [{x}, {y}]
ans = 0
for r in R.keys():
    ans += len(R[r][0])*len(R[r][1])
print(ans-n)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().strip()

def main():

    """
    <UnionFindを使わない別解>

    x方向とy方向に分けて頂点を辺だと思うのは定石？？？（確かに長方形がメインなら直積分解したくなる？）
    このとき問題文は「長さ３のパスがあればパスを１本追加する操作を繰り返して、各連結成分を完全二部グラフにせよ」

    完全二部グラフになるのは背理法からすぐわかる。なので解法は(¥Sum_{i:component}X_i Y_i) - N
    """

    N = int(input())
    V = 10 ** 5 + 1 
    repn = [[] for _ in range(V * 2)]
    for _ in range(N):
        x, y = map(int, input().split())
        repn[x].append(V + y)
        repn[V + y].append(x)

    visited = [0] * (V * 2)
    count = [0, 0]

    
    def dfs(v):
        if visited[v]:
            return
        visited[v] = 1
        count[v // V] += 1
        for u in repn[v]:
            dfs(u)

    ans = 0
    for i in range(V * 2):
        if visited[i]:
            continue
        count[:] = [0, 0]
        dfs(i)
        ans += count[0] * count[1]
    print(ans - N)


if __name__ == "__main__":
    main()

Solution (Python):




def main():
    from collections import Counter
    import sys
    input = sys.stdin.readline

    MX = 10 ** 5 + 10

    *p, = [r for r in range(MX * 2)]

    def root(x):
        if x == p[x]:
            return x
        p[x] = y = root(p[x])
        return y

    def unite(x, y):
        px = root(x)
        py = root(y)
        if px == py:
            return 0
        if px < py:
            p[py] = px
        else:
            p[px] = py
        return 1

    n = int(input())
    for _ in range(n):
        x, y = (int(x) - 1 for x in input().split())  
        unite(x, y + MX)

    ctr_x = Counter(root(r) for r in range(MX))
    ctr_y = Counter(root(r) for r in range(MX, MX * 2))

    rs = set(ctr_x.keys())
    rs.update(ctr_y.keys())

    ans = sum(ctr_x[r] * ctr_y[r] for r in rs) - n

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):



def main():
    import sys
    input = sys.stdin.readline

    MX = 10 ** 5 + 10
    
    *p, = [r for r in range(MX * 2)]

    def root(x):
        if x == p[x]:
            return x
        p[x] = y = root(p[x])
        return y

    def unite(x, y):
        px = root(x)
        py = root(y)
        if px == py:
            return 0
        if px < py:
            p[py] = px
        else:
            p[px] = py
        return 1

    n = int(input())
    for _ in range(n):
        x, y = (int(x) - 1 for x in input().split())  
        unite(x, y + MX)

    xs = [0] * (MX * 2)
    ys = [0] * (MX * 2)

    for r in range(MX):
        xs[root(r)] += 1

    for r in range(MX, MX * 2):
        ys[root(r)] += 1

    ans = -n
    for r in range(MX * 2):
        ans += xs[r] * ys[r]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().strip()

class UnionFind():
    """
    https://note.nkmk.me/python-union-find/
    DFSの上位互換と考えて良い
    ２要素x, yがpath-connectedかどうかをlogオーダーで判定する（螺旋本の14.1節参照）
    さらに連結成分の要素数がO(1)で取得可能なように改造してある
    """
    def __init__(self, n):
        """
        要素数をnとして、各ノードを0,1,...,(n-1)の番号で管理する
        parentsは各ノードの属する木の根を表す
        ただし根ノードのparentには(その木のノード数)*(-1)を格納する
        """
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        """
        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, yのそれぞれ属する木Tx, Tyの根同士を繋ぐ
        このとき木の要素数が小さい方を大きい方に繋ぐ（rankではなくsizeを用いる）
        """
        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):
        """
        xの属する木の要素数を返す
        根の親を要素数の(-1)倍で定めておいたおかげでO(1)で取得可能
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        xとyがpath-connectedかを判定する
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """
        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())



def main():

    """
    x方向とy方向に分けて頂点を辺だと思うのは定石？？？（確かに長方形がメインなら直積分解したくなる？）
    このとき問題文は「長さ３のパスがあればパスを１本追加する操作を繰り返して、各連結成分を完全二部グラフにせよ」

    完全二部グラフになるのは背理法からすぐわかる。なので解法は(¥Sum_{i:component}X_i Y_i) - N
    """

    N = int(input())
    vertex_x = set([])
    vertex_y = set([])
    edge = []
    for _ in range(N):
        x, y = map(int, input().split())
        vertex_x.add(x)
        vertex_y.add(y)
        edge.append((x, y))

    
    
    d = defaultdict(int)
    num = 0
    for x in vertex_x:
        d[(0, x)] = num
        num += 1
    x_num = num
    for y in vertex_y:
        d[(1, y)] = num
        num += 1

    
    uftree = UnionFind(num)
    for x, y in edge:
        uftree.union(d[(0, x)], d[(1, y)])

    ans = 0
    for r in uftree.roots():
        X = 0
        Y = 0
        for v in uftree.members(r):
            if v < x_num:
                X += 1
            else:
                Y += 1
        ans += X * Y
    print(ans - N)



if __name__ == "__main__":
    main()