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.



Sample input:
3
1 1
5 1
5 5


Sample output:
1

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict
    import sys
    # functions used
    r = lambda: sys.stdin.readline().strip()
    R = lambda: list(map(int, r().split()))

    N = int(r())
    Dic = defaultdict(list)
    V = 10**5 + 5
    Arrived = [False] * (2 * V)
    for _ in range(N):
        x, y = R()
        y += V
        Dic[x].append(y)
        Dic[y].append(x)

    ans = 0
    task = []
    for k, v in Dic.items():
        if Arrived[k]:
            continue
        Arrived[k] = True
        if k < V:
            cntx = 1
            cnty = 0
        else:
            cntx = 0
            cnty = 1
        cntdot = 0
        task.extend(v)
        cntdot += len(v)
        while task:
            s = task.pop()
            if Arrived[s]:
                continue
            if s < V:
                cntx += 1
            else:
                cnty += 1
            Arrived[s] = True
            task.extend(Dic[s])
            cntdot += len(Dic[s])
        ans += cntx * cnty - cntdot // 2
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# using main() makes code faster from the point of view of "access to variables in global name-space"
# def main():

# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def factorize(n):
    """return the factors of the Arg and count of each factor
    
    Args:
        n (long): number to be resolved into factors
    
    Returns:
        list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
    """
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def combinations_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    # TODO: How should I do when n - r is negative?
    if n < 0 or r < 0:
        raise Exception('combinations_count(n, r) not defined when n or r is negative')
    if n - r < r: r = n - r
    if r < 0: return 0
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combinations_with_replacement_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    if n < 0 or r < 0:
        raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
    elif n == 0:
        return 1
    else:
        return combinations_count(n + r - 1, r)
from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from operator import itemgetter
# ex1: List.sort(key=itemgetter(1))
# ex2: sorted(tuples, key=itemgetter(1,2))
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

# first create factorial_list
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

# initialize variables and set inputs
# initialize variables
    # to initialize list, use [0] * n
    # to initialize two dimentional array, use [[0] * N for _ in range(N)]
# set inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
# preprocessing
    # transpose = [x for x in zip(*data)]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
# calculate and output
    # output pattern
    # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6

# functions used
r = lambda: sys.stdin.readline().strip()
r_int = lambda: int(r())
R = lambda: list(map(int, r().split()))
Rfloat = lambda: list(map(float, r().split()))
Rtuple = lambda: tuple(map(int, r().split()))
Rmap = lambda: map(int, r().split())
# single int: int(r())
# single string: r()
# single float: float(r())
# line int: R()
# line string: r().split()
# line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
# lines int: [R() for _ in range(n)]

# set inputs
# sys.stdin = open('sample.txt') # for test
N = r_int()
Dic = defaultdict(list)
V = 10**5 + 5
Arrived = [False] * (2 * V)
for _ in range(N):
    x, y = R()
    y += V
    Dic[x].append(y)
    Dic[y].append(x)

ans = 0
task = []
for k, v in Dic.items():
    if Arrived[k]:
        continue
    Arrived[k] = True
    cntx = 0
    cnty = 0
    if k < V:
        cntx += 1
    else:
        cnty += 1
    cntdot = 0
    task.extend(v)
    cntdot += len(v)
    while task:
        s = task.pop()
        if Arrived[s]:
            continue
        if s < V:
            cntx += 1
        else:
            cnty += 1
        Arrived[s] = True
        task.extend(Dic[s])
        cntdot += len(Dic[s])
    ans += cntx * cnty - cntdot // 2
print(ans)

# if __name__ == '__main__':
#     main()

Submission status: Accepted

Solution code:
N = int(input())
points = []
for i in range(0, N):
    points.append(list(map(int, input().split(' '))))
X = dict()
Y = dict()
count = 0
for p in points:
    if p[0] not in X.keys():
        X[p[0]] = []
    X[p[0]].append(p[1])
    if p[1] not in Y.keys():
        Y[p[1]] = []
    Y[p[1]].append(p[0])
while len(X.items()) > 0:
    item = list(X.items())[0]
    del X[item[0]]
    queue = [item]
    point_dict = {'x': [], 'y': []}
    queue_is_x = [True]
    while len(queue) > 0:
        item = queue.pop(0)
        is_x = queue_is_x.pop(0)
        if is_x:
            point_dict['x'].append(item[0])
            for i in item[1]:
                if i in Y.keys():
                    queue.append((i, Y[i]))
                    queue_is_x.append(False)
                    del Y[i]
        else:
            point_dict['y'].append(item[0])
            for i in item[1]:
                if i in X.keys():
                    queue.append((i, X[i]))
                    queue_is_x.append(True)
                    del X[i]
    # print((point_dict['x']))
    # print(len((point_dict['x'])))
    # print((point_dict['y']))
    # print(len((point_dict['y'])))
    count += len(set(point_dict['x'])) * len(set(point_dict['y']))

print(count - len(points))

Submission status: Accepted

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]

class Union:
  def __init__(s, n):
    s.N = n
    s.L = [-1] * n

  def root(s, x):
    if s.L[x] < 0:
      return x, -s.L[x]
    return s.root(s.L[x])

  def merge(s, x, y):
    a, ar = s.root(x)
    b, br = s.root(y)
    if a == b:
      return True
    if ar < br:
      s.L[b] -= ar
      s.L[a] = b
    else:
      s.L[a] -= br
      s.L[b] = a
    return False

  def getList(s):
    D = []
    DN = [0] * N
    for i in range(N):
      if s.L[i] < 0:
        DN[i] = len(D)
        D.append([])
    for i in range(N):
      D[DN[s.root(i)[0]]].append(i)
    return D

M = 10**5 + 1
xL = [-1] * M
yL = [-1] * M
uni = Union(N)

for i in range(N):
  x = xy[i][0]
  y = xy[i][1]
  if xL[x] != -1:
    uni.merge(xL[x], i)
  if yL[y] != -1:
    uni.merge(yL[y], i)
  xL[x] = i
  yL[y] = i

L = uni.getList()
ans = 0
for t in L:
  xL = [0] * M
  yL = [0] * M
  xN = 0
  yN = 0
  for i in t:
    x, y = xy[i]
    if xL[x] == 0:
      xL[x] = 1
      xN += 1
    if yL[y] == 0:
      yL[y] = 1
      yN += 1
  ans += xN * yN - len(t)

print(ans)

Submission status: Accepted

Solution code:
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())


class PotentialUnionFind:
    def __init__(self,N): # 頂点数 N
        self.table = [i for i in range(N)]    # 親 table[x] == x で根
        self.rank  = [1 for i in range(N)]    # 木の長さ
        self.size  = [1 for i in range(N)]    # 集合のサイズ
        self.diffweight = [0 for i in range(N)]

    def Find(self,x):    #xの根を返す
        if self.table[x] == x:
            return x
        else:
            root = self.Find(self.table[x]) #親の更新
            self.size[x] = self.size[self.table[x]]
            self.diffweight[x] += self.diffweight[self.table[x]]
            self.table[x] = root
            return root

    def Unite(self,x,y,w): #xとyをDiff(x,y)=W で繋げる
        w = w - self.Weight(y) + self.Weight(x)
        x,y = self.Find(x), self.Find(y)
        sx,sy = self.Size(x), self.Size(y)
        if x == y: return
        if self.rank[x] > self.rank[y]:
            self.table[y] = x
            self.size[x] = sx + sy
            self.diffweight[y] = w
        else:
            self.table[x] = y
            self.size[y] = sx + sy
            self.diffweight[x] = -w
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def Check(self,x,y):
        return self.Find(x) == self.Find(y)

    def Size(self,x):
        return self.size[self.Find(x)]

    def Weight(self,x): # 重さ(根からの距離)
        self.Find(x)
        return self.diffweight[x]

    def Diff(self,x,y): # 繋がってる二点間距離
        return self.Weight(y) - self.Weight(x)


N = int(input())
PUF = PotentialUnionFind(10**5+1)

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 PUF.Check(s,t):
            PUF.Unite(s,t,1)

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

print(ans)

Submission status: Accepted

Solution code:
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())

class UnionFind:
    def __init__(self,N): # 頂点数 N
        self.table = [i for i in range(N)]    #木の親 table[x] == x なら根
        self.rank  = [1 for i in range(N)]    #木の長さ
        self.size  = [1 for i in range(N)]    #集合のサイズ

    def Find(self,x):    #xの根を返す
        if self.table[x] == x:
            return x
        else:
            self.table[x] = self.Find(self.table[x])    #親の更新(根を直接親にして参照距離を短く)
            self.size[x] = self.size[self.table[x]]
            return self.table[x]

    def Unite(self,x,y):    #xとyを繋げる
        x,y = self.Find(x), self.Find(y)
        sx,sy = self.Size(x), self.Size(y)
        if x == y: return
        if self.rank[x] > self.rank[y]:
            self.table[y] = x
            self.size[x] = sx + sy
        else:
            self.table[x] = y
            self.size[y] = sx + sy
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def Check(self,x,y):
        return self.Find(x) == self.Find(y)

    def Size(self,x):
        return self.size[self.Find(x)]



N = int(input())
UF = UnionFind(10**5+1)

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 UF.Check(s,t):
            UF.Unite(s,t)

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

print(ans)

Submission status: Accepted

Solution code:
V=10**5+5
class UnionFind:
    def __init__(self,n):
        self.parent=[i for i in range(n)]
        self.rank=[0 for _ in range(n)]
        # use for n=2*V
        self.xSize=[1 if i<V else 0 for i in range(n)]
        self.ySize=[0 if i<V else 1 for i in range(n)]

    def find(self,x):
        if self.parent[x]==x:
            return x
        else:
            parentx=self.find(self.parent[x])
            self.parent[x]=parentx
            return parentx

    def union(self,x,y):
        rootx=self.find(x)
        rooty=self.find(y)
        if rootx==rooty:
            return
        if self.rank[rootx]>self.rank[rooty]:
            self.parent[rooty]=rootx
            self.xSize[rootx]+=self.xSize[rooty]
            self.ySize[rootx]+=self.ySize[rooty]
        else:
            self.parent[rootx]=rooty
            self.xSize[rooty]+=self.xSize[rootx]
            self.ySize[rooty]+=self.ySize[rootx]
            if self.rank[rootx]==self.rank[rooty]:
                self.rank[rooty]+=1

n=int(input())
xy=[tuple(map(int,input().split())) for _ in range(n)]
uf=UnionFind(V*2)
for xi,yi in xy:
    uf.union(xi,yi+V)

# for i in range(V*2):
#     uf.find(i)

ans=0
used=set()
for i in range(V*2):
    rooti=uf.find(i)
    if rooti not in used:
        used.add(rooti)
        ans+= uf.xSize[rooti]*uf.ySize[rooti]
print(ans-n)

Submission status: Accepted

Solution code:
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 Count(self, x):
        return -self.root[self.Find_Root(x)]

m = 100010
uf = UnionFind(m*2)
n = int(input())
for i in range(n):
    x,y = map(int,input().split())
    y = y+m
    uf.Unite(x,y)

lx = {}
ly = {}
ans = 0
for i in range(m):
    rx = uf.Find_Root(i)
    lx[rx] = lx.get(rx,0)+1
    ry = uf.Find_Root(i+m)
    ly[ry] = ly.get(ry,0)+1
for i in range(m*2):
    ans += lx.get(i,0)*ly.get(i,0)

print(ans-n)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


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


def read_int_n():
    return tuple(map(int, input().split()))


def read_float():
    return float(input())


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


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


def read_str_n():
    return list(map(str, input().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):
    g = [[] for _ in range((10**5)*2)]
    offset = 10**5
    cs = set()
    for x, y in XY:
        x -= 1
        y = y - 1 + offset
        g[x].append(y)
        g[y].append(x)
        cs.add(x)
        cs.add(y)
    ans = 0
    while cs:
        error_print(len(cs))
        q = set([cs.pop()])
        done = set()
        done_c = set()
        while q:
            v = q.pop()
            for u in g[v]:
                if v >= offset:
                    e = (u, v)
                else:
                    e = (v, u)
                if e not in done:
                    q.add(u)
                    done.add(e)
                    done_c.add(u)
                    done_c.add(v)
        xn = set()
        yn = set()
        for v, u in done:
            for z in (v, u):
                if z >= offset:
                    yn.add(z)
                else:
                    xn.add(z)
        ans += (len(xn) * len(yn)) - len(done)
        cs -= done_c

    return ans

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class DGraph:
    def __init__(self, n, edges):
        self._vertice = [{} for _ in range(n)]
        for e in edges:
            self._vertice[e[0]][e[1]] = e[2] if len(e) == 3 else 1

    def __len__(self):
        return len(self._vertice)

    def edges(self, n=None):
        srcs = range(len(self)) if n is None else [n]
        return sum([[(s, d, c) for d, c in self._vertice[s].items()] for s in srcs], [])

    def transpose(self):
        tedges = [(t, f, c) for f, t, c in self.edges()]
        return DGraph(len(self), tedges)

    def cost(self, src, dst):
        return self._vertice[src].get(dst, float('inf'))

class Graph(DGraph):
    def __init__(self, n, edges):
        nd_edges = edges + [(d, s, c) for s, d, c in edges]
        super().__init__(n, nd_edges)

    def transpose(self):
        return self


def solve(N: int, x: "List[int]", y: "List[int]"):
    xs = {v:i for i, v in enumerate(set(x))}
    ys = {v:i for i, v in enumerate(set(y), len(xs))}
    
    n = len(xs) + len(ys)
    es = [(xs[cx], ys[cy], 1) for cx, cy in zip(x, y)]
    g = Graph(n, es)

    visited = [False] * len(g)
    def dfs(g, src):
        nonlocal visited
        stack = [(src, 0)]
        while stack:
            n, c = stack.pop()
            if visited[n]:
                continue
            visited[n] = True

            for _, d, _ in g.edges(n):
                #yield d
                stack.append((d, c + 1))
            yield n

    def _f(i):
        ls = list(i)
        if len(ls) == 0:
            return 0

        xc = 0
        yc = 0
        es = 0
        for i in ls:
            es += len(g.edges(i))
            if i < len(xs):
                xc += 1
            else:
                yc += 1
        es //= 2

        if xc < 2 or yc < 2:
            return 0

        return xc * yc - es

    return sum([_f(dfs(g, i)) for i in range(n)])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]" 
    y = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    result = solve(N, x, y)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class DGraph:
    def __init__(self, n, edges):
        self._vertice = [{} for _ in range(n)]
        for e in edges:
            self._vertice[e[0]][e[1]] = e[2] if len(e) == 3 else 1

    def __len__(self):
        return len(self._vertice)

    def edges(self, n=None):
        srcs = range(len(self)) if n is None else [n]
        return sum([[(s, d, c) for d, c in self._vertice[s].items()] for s in srcs], [])

    def transpose(self):
        tedges = [(t, f, c) for f, t, c in self.edges()]
        return DGraph(len(self), tedges)

    def cost(self, src, dst):
        return self._vertice[src].get(dst, float('inf'))

class Graph(DGraph):
    def __init__(self, n, edges):
        nd_edges = edges + [(d, s, c) for s, d, c in edges]
        super().__init__(n, nd_edges)

    def transpose(self):
        return self


def solve(N: int, x: "List[int]", y: "List[int]"):
    xs = {v:i for i, v in enumerate(set(x))}
    ys = {v:i for i, v in enumerate(set(y), len(xs))}
    
    n = len(xs) + len(ys)
    es = [(xs[cx], ys[cy], 1) for cx, cy in zip(x, y)]
    g = Graph(n, es)

    visited = [False] * len(g)
    def dfs(g, src):
        nonlocal visited
        stack = [(src, 0)]
        while stack:
            n, c = stack.pop()
            if visited[n]:
                continue
            visited[n] = True

            for _, d, _ in g.edges(n):
                #yield d
                stack.append((d, c + 1))
            yield n, c

    def _f(i):
        ls = list(i)
        if len(ls) == 0:
            return 0

        xc = 0
        yc = 0
        es = 0
        for i, _ in ls:
            es += len(g.edges(i))
            if i < len(xs):
                xc += 1
            else:
                yc += 1
        es //= 2

        if xc < 2 or yc < 2:
            return 0

        return xc * yc - es

    return sum([_f(dfs(g, i)) for i in range(n)])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]" 
    y = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    result = solve(N, x, y)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:

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

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

  def union(self, x, y):
    x, y = self.find(x), self.find(y)
    if x == y:
      return False
    elif self.rank[x] < self.rank[y]:
      self.par[x] = y
      self.sizes[y] += self.sizes[x]
    elif self.rank[x] > self.rank[y]:
      self.par[y] = x
      self.sizes[x] += self.sizes[y]
    else:
      self.par[y] = x
      self.rank[x] += 1
      self.sizes[x] += self.sizes[y]
    return True

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

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

n = int(input())
nx = [0 for i in range(200020)]
ny = [0 for i in range(200020)]
uf = UnionFind(200020)
for i in range(n):
  x, y = list(map(int, input().split()))
  uf.union(x, y+100010)
ans = 0
for i in range(100010):
  nx[uf.find(i)] += 1
  ny[uf.find(i+100010)] += 1
for i in range(200020):
  ans += nx[i]*ny[i]
print(ans-n)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
from collections import deque


def solve(N: int, X: "List[int]", Y: "List[int]"):
    adj = defaultdict(list)
    done = set()
    for x, y in zip(X, Y):
        xnode = (x, 0)
        ynode = (y, 1)
        adj[xnode].append(ynode)
        adj[ynode].append(xnode)

    points_to_add = 0    
    for x, y in zip(X, Y):
        xnode = (x, 0)
        ynode = (y, 1)
        if xnode in done or ynode in done:
            continue
        x_count = 1
        y_count = 0
        done.add(xnode)
        Q = deque()
        Q.append(xnode)
        while len(Q) > 0:
            node = Q.pop()
            for node_next in adj[node]:
                if node_next in done:
                    continue
                if node_next[1] == 0:
                    x_count += 1
                else:
                    y_count += 1
                Q.append(node_next)
                done.add(node_next)
        points_to_add += x_count * y_count
    print(points_to_add - N)
        
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]" 
    y = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import csr_matrix, csgraph
import sys

input = sys.stdin.readline

U = 10 ** 5
n = int(input())
xy = np.array([input().split() for _ in range(n)], dtype=np.int32)

graph = csr_matrix((np.ones(n, dtype=np.bool), (xy[:, 0], U + xy[:, 1])), (2 * U + 1, 2 * U + 1))
_, component = csgraph.connected_components(graph)

x_cnt = np.bincount(component[:U + 1], minlength=2 * U + 2)
y_cnt = np.bincount(component[U + 1:], minlength=2 * U + 2)
pts_cnt = np.bincount(component[xy[:, 0]], minlength=2 * U + 2)
answer = (x_cnt * y_cnt - pts_cnt).sum()
print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))
from collections import defaultdict

class UnionFind:
    def __init__(self, N=None):
        if N is None or N < 1:
            self.parent = defaultdict(lambda: -1)
        else:
            self.parent = [-1]*int(N)

    def root(self, n):
        if self.parent[n] < 0:
            return n
        else:
            m = self.root(self.parent[n])
            self.parent[n] = m
            return m

    def merge(self, m, n):
        rm = self.root(m)
        rn = self.root(n)
        if rm != rn:
            if -self.parent[rm] < -self.parent[rn]:
                rm, rn = rn, rm
            self.parent[rm] += self.parent[rn]
            self.parent[rn] = rm

    def size(self, n):
        return -self.parent[self.root(n)]
    
    def connected(self, m, n):
        return self.root(m) == self.root(n)
    
    def groups(self):
        if isinstance(self.parent,list):
            return list(map(lambda x: x<0, self.parent)).count(True)
        else: # self.parent: defaultdict
            return list(map(lambda x: x<0, self.parent.values())).count(True) 

N = int(input())
uf = UnionFind()
for _ in range(N):
    x, y = inpl()
    uf.merge(2*x,2*y+1)

nxny = defaultdict(lambda: [0, 0])
for k in uf.parent.keys():
    nxny[uf.root(k)][k % 2] += 1

ans = sum([ nx * ny for nx, ny in nxny.values() ]) - N
print(ans)