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):
N=int(input())
from collections import defaultdict
X=dict()
Y=dict()
P=[]
root=[-1]*N
def find(i):
    global root
    if root[i]>=0:
        root[i]=find(root[i])
        return root[i]
    return i
for i in range(N):
    x,y=map(int,input().split())
    P+=[(x,y)]
    if x not in X.keys():
        rx=i
        X[x]=i
    else:
        rx=find(X[x])
        X[x]=rx
    if y not in Y.keys():
        ry=i
        Y[y]=i
    else:
        ry=find(Y[y])
        Y[y]=ry
    if rx==ry:
        if i!=rx:
            root[i]=rx
        continue
    elif root[rx]<=root[ry]:
        root[rx]+=root[ry]
        root[ry]=rx
        if i!=rx:
            root[i]=rx
    else:
        root[ry]+=root[rx]
        root[rx]=ry
        if i!=ry:
            root[i]=ry
cntx=defaultdict(set)
cnty=defaultdict(set)
RP=set()
ans=0
for i in range(N):
    x,y=P[i]
    r=find(i)
    cntx[r]|={x}
    cnty[r]|={y}
    RP|={r}
for k in RP:
    ans+=len(cntx[k])*len(cnty[k])
print(ans-N)

Solution (Python):

from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import random
import collections
import math
import itertools
import bisect

def real_main():
    n = read_int()
    points = [read_int_array() for _ in range(n)]
    next_id = 1
    scc = [0]*n
    y_idx = collections.defaultdict(list)
    x_idx = collections.defaultdict(list)
    for i, (x, y) in enumerate(points):
        y_idx[y].append(i)
        x_idx[x].append(i)

    def bfs(start):
        q = [start]
        for i in q:
            x, y = points[i]
            for ni in y_idx[y]:
                if not scc[ni]:
                    scc[ni] = next_id
                    q.append(ni)
            for ni in x_idx[x]:
                if not scc[ni]:
                    scc[ni] = next_id
                    q.append(ni)
        return q

    ans = 0
    for i in range(n):
        if not scc[i]:
            scc[i] = next_id
            scc_points = bfs(i)
            diff_x, diff_y = len(set(points[idx][0] for idx in scc_points)), len(set(points[idx][1] for idx in scc_points))
            if diff_x > 1 and diff_y > 1:
                ans += diff_x * diff_y - len(scc_points)
            next_id += 1
    print(ans)


def solve():
    pass


def main():
    if False and 'PYCHARM_HOSTED' in os.environ:
        main_pycharm()
    else:
        real_main()


from copy import deepcopy
def main_pycharm():
    solution = solve

    test_inputs = None
    test_outputs = None
    judge = None
    slow_solution = None
    if solution is not None:
        if test_outputs is not None:
            test_with_answers(solution, test_inputs, test_outputs)
        if judge is not None:
            test_with_judge(solution, test_inputs, judge)
        if slow_solution is not None:
            test_with_slow_solution(solution, test_inputs, slow_solution)


def test_with_answers(solution, inputs, answers):
    total, wrong = 0, 0
    for args, test_ans in zip(inputs, answers):
        ans = solution(*deepcopy(args))
        if ans != test_ans:
            print('WRONG! ans=%s, test_ans=%s, args=%s' % (ans, test_ans, args))
            wrong += 1
        else:
            print('GOOD')
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_judge(solution, inputs_gen, judge):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        if not judge(deepcopy(ans), *deepcopy(args)):
            print('WRONG! ans=%s, args=%s' % (ans, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_slow_solution(solution, inputs_gen, solution_slow):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        slow = solution_slow(*deepcopy(args))
        if ans != slow:
            print('WRONG! ans=%s, slow=%s, args=%s' % (ans, slow, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))




def mergesort(A, key=lambda x: x, reverse=False):
    C = A
    A = list(range(len(A)))
    B = list(A)

    n = len(A)
    for i in range(0, n - 1, 2):
        if key(C[A[i]]) > key(C[A[i ^ 1]]):
            A[i], A[i ^ 1] = A[i ^ 1], A[i]

    width = 2
    while width < n:
        for i in range(0, n, 2 * width):
            R1, R2 = min(i + width, n), min(i + 2 * width, n)
            j, k = R1, i
            while i < R1 and j < R2:
                if key(C[A[i]]) > key(C[A[j]]):
                    B[k] = A[j]
                    j += 1
                else:
                    B[k] = A[i]
                    i += 1
                k += 1
            while i < R1:
                B[k] = A[i]
                k += 1
                i += 1
            while k < R2:
                B[k] = A[k]
                k += 1
        A, B = B, A
        width *= 2

    if reverse:
        A.reverse()
    return A




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

def read():
    return input()

def read_int():
    return int(input())

def read_array(sep=None, maxsplit=-1):
    return input().split(sep, maxsplit)

def read_int_array():
    return [int(a) for a in read_array()]



if __name__ == "__main__":
    main()

Solution (Python):


N = int(input())
U = 10 ** 5
root_x = [None] * (U+1)
root_y = [None] * (U+1)
size_x = [0] * (U+1) 
size_y = [0] * (U+1) 
cnt_x = [0] * (U+1) 
cnt_y = [0] * (U+1) 
x_to_y = [None] * (U+1)
y_to_x = [None] * (U+1)

def find_root(root,size,x):
  y = root[x]
  if y is None:
    root[x] = x
    size[x] = 1
    return x
  if x == y:
    return y
  z = find_root(root,size,y)
  root[x] = z
  return z

def merge(root,size,cnt,x,y):
  rx = find_root(root,size,x)
  ry = find_root(root,size,y)
  if rx == ry:
    return
  sx = size[rx]
  sy = size[ry]
  if sx > sy:
    root[ry] = rx
    size[rx] += sy
    cnt[rx] += cnt[ry]
  else:
    root[rx] = ry
    size[ry] += sx
    cnt[ry] += cnt[rx]
  return

for _ in range(N):
  x,y = map(int,input().split())
  rx = find_root(root_x,size_x,x)
  ry = find_root(root_y,size_y,y)
  cnt_x[rx] += 1
  cnt_y[ry] += 1
  if x_to_y[rx] is None:
    x_to_y[rx] = ry
  if y_to_x[ry] is None:
    y_to_x[ry] = rx
  merge(root_y, size_y, cnt_y, x_to_y[rx], ry)
  merge(root_x, size_x, cnt_x, y_to_x[ry], rx)
  x_to_y[root_x[rx]] = root_y[ry]
  y_to_x[root_y[ry]] = root_x[rx]

  
answer = 0

for x in range(1,U+1):
  if root_x[x] is None:
    continue
  rx = find_root(root_x,size_x,x)
  if x != rx:
    continue
  y = x_to_y[x]
  ry = find_root(root_y,size_y,y)
  sx = size_x[rx]
  sy = size_y[ry]
  cnt = cnt_x[rx]
  answer += (sx * sy - cnt)
print(answer)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

class UnionFindTree:
    def __init__(self, n):
        self.nodes = list(range(n+1))
    def find(self, x):
        if self.nodes[x] == x:
            return x
        parent = self.find(self.nodes[x])
        self.nodes[x] = parent
        return parent
    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        self.nodes[a] = self.nodes[b]
    def is_same(self, a, b):
        return self.find(a) == self.find(b)

UFL=UnionFindTree(100010)
UFR=UnionFindTree(100010)

N=II()
rmap = {}
lmap = {}
for i in range(N):
    l,r=LI()
    if not r in rmap:
        rmap[r] = []
    if not l in lmap:
        lmap[l] = []
    rmap[r].append(l)
    lmap[l].append(r)

for l, lis in lmap.items():
    for r in lmap[l]:
        for l2 in rmap[r]:
            UFL.unite(l,l2)
for r, lis in rmap.items():
    for l in rmap[r]:
        for r2 in lmap[l]:
            UFR.unite(r,r2)

varl = {}
varr = {}

for l in lmap.keys():
    gr = UFL.find(l)
    if gr in varl:
        varl[gr] += 1
    else:
        varl[gr] = 1

for r in rmap.keys():
    gr = UFR.find(r)
    if gr in varr:
        varr[gr] += 1
    else:
        varr[gr] = 1

res = {}
for l, lis in lmap.items():
    gl = UFL.find(l)
    gr = UFR.find(lis[0])
    res[(gl,gr)] = varl[gl] * varr[gr]




ressum = 0
for i in res.values():
    ressum += i
print(ressum - N)

Solution (Python):
class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[i for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)
N=int(input())
P=[(i,)+tuple(map(int,input().split())) for i in range(N)]
G=UnionFind(N)
P.sort(key=lambda x:x[1])
for i in range(N-1):
    if P[i][1]==P[i+1][1]:
        G.unite(P[i][0],P[i+1][0])
P.sort(key=lambda x:x[2])
for i in range(N-1):
    if P[i][2]==P[i+1][2]:
        G.unite(P[i][0],P[i+1][0])
P.sort(key=lambda x:x[0])
Dx=dict()
Dy=dict()
for i in range(N):
    j=G.find(i)
    if j in Dx:
        Dx[j].add(P[i][1])
    else:
        Dx[j]={P[i][1]}
    if j in Dy:
        Dy[j].add(P[i][2])
    else:
        Dy[j]={P[i][2]}
ans=-N
for j in Dx:
    ans+=len(Dx[j])*len(Dy[j])
print(ans)

Solution (Python):
import sys
from collections import defaultdict
sys.setrecursionlimit(2*10**6)
class UF():
    def __init__(self, num):
        self.par = [-1]*num
        self.size = [1]*num
    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.size[rx] += self.size[ry] 
            elif self.par[rx] > self.par[ry]:
                self.par[rx] = ry
                self.size[ry] += self.size[rx]
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
                self.size[rx] += self.size[ry]
        return



N = int(input())

XY = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
X, Y = list(map(list, zip(*XY)))
G = UF(N)
checked = [False]*N

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

for v in Xc.values():
    if len(v) == 1:
        continue
    vx = v[0]
    for x in v[1:]:
        G.union(vx, x)

for v in Yc.values():
    if len(v) == 1:
        continue
    vy = v[0]
    for y in v[1:]:
        G.union(vy, y)

ans = -N

Zx = defaultdict(set)
Zy = defaultdict(set)
for i in range(N):
    ri = G.find(i)
    Zx[ri].add(X[i])
    Zy[ri].add(Y[i])

for i in range(N):
    ri = G.find(i)
    if checked[ri] == True:
        continue
    checked[ri] = True
    ans += len(Zx[ri])*len(Zy[ri])
print(ans)

Solution (Python):



get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: map(int, raw_input().strip().split())
getss = lambda n: [gets() for _ in xrange(n)]








N = get()
A = getss(N)
UF = {}


def find(x):
    if x != UF[x]:
        UF[x] = find(UF[x])
    return UF[x]


def union(x, y):
    UF.setdefault(x, x)
    UF.setdefault(y, y)
    UF[find(x)] = find(y)


for i, j in A:
    union(i, -j)


count = {}
for x in UF:
    root = find(x)
    if root not in count:
        count[root] = [0, 0]
    if x > 0:
        count[root][0] += 1
    else:
        count[root][1] += 1

res = 0
for x in count:
    pos, neg = count[x]
    if pos > 1 and neg > 1:
        res += pos * neg
    else:
        res += max(pos, neg)
print res - N

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def Find(x):    
    global table

    if table[x] == x:
        return x
    else:
        table[x] = Find(table[x])    
        size[x] = size[table[x]]
        return table[x]

def Unite(x,y):    
    global size
    global rank
    x = Find(x)
    y = Find(y)
    sx = Size(x)
    sy = Size(y)

    if x == y:
        return

    if rank[x] > rank[y]:
        table[y] = x
        size[x] = sx + sy
    else:
        table[x] = y
        size[y] = sx + sy
        if rank[x] == rank[y]:
            rank[y] += 1

def Check(x,y):
    if Find(x) == Find(y):
        return True
    else:
        return False

def Size(x):
    return size[Find(x)]

table = [i for i in range(10**5+1)]    
rank  = [1 for i in range(10**5+1)]    
size  = [1 for i in range(10**5+1)]    


N = int(input())
xys = [inpl() for _ in range(N)]
xys.sort()
tatedict = defaultdict(list)
xx = set()
for x,y in xys:
    tatedict[x].append(y)
    xx.add(x)

for x in xx:
    s = tatedict[x][0]
    for t in tatedict[x]:
        if not Check(s,t):
            Unite(s,t)

ans = 0
for x in xx:
    s = tatedict[x][0]
    ans += Size(s) - len(tatedict[x])

print(ans)

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

N=int(input())
P=[list(map(int,input().split()))+[i] for i in range(N)]
Q=copy.deepcopy(P)



Group=[i for i in range(N)]

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):  
    if find(x) != find(y):
        Group[find(y)]=Group[find(x)]=min(find(y),find(x))

P.sort(key=lambda x:x[0])

for i in range(1,N):
    if P[i][0]==P[i-1][0]:
        Union(P[i][2],P[i-1][2])


P.sort(key=lambda x:x[1])

for i in range(1,N):
    if P[i][1]==P[i-1][1]:
        Union(P[i][2],P[i-1][2])





B=[[] for i in range(N)]

for i in range(N):
    B[find(i)].append(i)

ANS=0
for BEL in B:
    X=[]
    Y=[]
    for b in BEL:
        X.append(Q[b][0])
        Y.append(Q[b][1])

    
    ANS+=len(set(X))*len(set(Y))-len(BEL)
print(ANS)

Solution (Python):
import sys
from bisect import bisect_left

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n = ni()

upper = [-1]*(2*n)
nxs = [0]*(2*n)
for i in range(n):
    nxs[i] += 1

def root(x):
    if upper[x] < 0:
        return x
    else:
        upper[x] = root(upper[x])
        return upper[x]

def equiv(x, y):
    return root(x) == root(y)

def unite(x, y):
    x, y = root(x), root(y)
    if x != y:
        if upper[y] < upper[x]:
            x, y = y, x
        upper[x] += upper[y]
        nxs[x] += nxs[y]
        upper[y] = x
    return x == y



co = []

for i in range(n):
    co.append(na())

xs = list(set(_[0] for _ in co))
xs.sort()

ys = list(set(_[1] for _ in co))
ys.sort()

for c in co:
    unite(bisect_left(xs, c[0]), bisect_left(ys, c[1])+n)

ans = 0
for i in range(2*n):
    if upper[i] < 0:
        ans += nxs[i] * (-upper[i] - nxs[i])
ans -= n
print(ans)