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:
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)

#座標値をkeyにして辞書を作成
X = defaultdict(list)
Y = defaultdict(list)
for i in range(N):
  X[x[i]].append(i)
  Y[y[i]].append(i)

#xが同じ値のものをunion
for v in X.values():
  if len(v)==1:
    continue
  for i in v[1:]:
    G.union(v[0],i)
  
#yが同じ値のものをunion   
for v in Y.values():
  if len(v)==1:
    continue
  for i in v[1:]:
    G.union(v[0],i)

#同じグループに存在するx,y値
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])

#同じrootの格子点が全て追加される　rootごとにdisjoint
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)

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.readline
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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)]
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
  #print(num_x[uf.find_root(i)], num_y[uf.find_root(i+MAX)])

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

print(ans - N)

Submission status: Accepted

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

Submission status: Accepted

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


# x座標または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)

Submission status: Accepted

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


# x座標または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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict


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 = defaultdict(set)
Dy = defaultdict(set)
for i in range(N):
    j = G.find(i)
    Dx[j].add(P[i][1])
    Dy[j].add(P[i][2])
ans = -N
for j in Dx:
    ans += len(Dx[j]) * len(Dy[j])
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3
sys.setrecursionlimit(int(1e+7))  # スタック上限

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    XY = ii2nnn(N)
    M = int(1e+5) + 5

    # 二部グラフ
    to = [[] for _ in range(M*2)]
    cnt = [0] * (M*2)
    visited = [False] * (M*2)

    # 二部グラフを構築
    for x, y in XY:
        y += M
        to[x].append(y)
        to[y].append(x)

    cnt = [0, 0]
    def bfs(n):
        q = deque()
        q.append(n)
        while q:
            i = q.popleft()
            if visited[i]:
                continue
            visited[i] = True
            cnt[i // M] += 1
            for j in to[i]:
                q.append(j)

    # 二部グラフを走査
    ans = 0
    for i in range(M*2):
        if visited[i]:
            continue
        cnt[0] = 0
        cnt[1] = 0
        bfs(i)
        ans += cnt[0] * cnt[1]
    
    ans -= N  # 既にある点は操作数に含まれない
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

V = 100005
N = int(input())

lines = [[] for _ in range(V * 2)]
visited = [False] * V * 2

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


for i in range(N):
	x, y = [int(x) for x in input().split()]
	y += V
	lines[x].append(y)
	lines[y].append(x)

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

ans -= N
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N=int(input())
mod=100010
visit=[0]*(2*mod)
table=[[] for i in range(2*mod)]
for i in range(N):
    x,y=map(int,input().split())
    y+=mod
    visit[x]=1
    visit[y]=1
    table[x].append(y)
    table[y].append(x)
H=deque()
num=0
for i in range(mod):
    if visit[i]==1:
        X=0
        Y=0
        H.append(i)
        visit[i]=0
        while H:
            pt=H.popleft()
            if pt>mod:
                Y+=1
            else:
                X+=1
            for x in table[pt]:
                if visit[x]==1:
                    visit[x]=0
                    H.append(x)
        #print(X,Y)
        num+=X*Y
print(num-N)

Submission status: Accepted

Solution code:
def get_group(x):
    g = group[x]
    if g == x:
        return x
    group[g] = re = get_group(g)
    return re

def unite(x, y):
    gx = get_group(x)
    gy = get_group(y)
    if gx != gy:
        dx = depth[gx]
        dy = depth[gy]
        if dy > dx:
            gx, gy = gy, gx
        group[gy] = gx
        if dx == dy:
            depth[gx] += 1

n = int(input())
group = {}
depth = {}
edge = []
for _ in range(n):
    x, y = map(int, input().split())
    group.setdefault(x, x)
    group.setdefault(-y, -y)
    depth.setdefault(x, 1)
    depth.setdefault(-y, 1)
    edge += [[x, -y]]

for x, y in edge:
    unite(x, y)

cnt = {}
for k in group.keys():
    g = get_group(k)
    cnt.setdefault(g, [0, 0])
    if k > 0:
        cnt[g][0] += 1
    else:
        cnt[g][1] += 1

ans = 0
for cx, cy in cnt.values():
    ans += cx * cy
print(ans - n)

Submission status: Accepted

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

def dfs(x, al):
    global cntx, cnty
    if (al, x) in used:
        return
    used.add((al, x))
    if al == 0:
        cntx += 1
    else:
        cnty += 1
    for xy in to[al][x]:
        dfs(xy, 1 - al)
    return

n = int(input())
to = [{}, {}]
for _ in range(n):
    x, y = map(int, input().split())
    to[0].setdefault(x, [])
    to[1].setdefault(y, [])
    to[0][x] += [y]
    to[1][y] += [x]
used = set()
ans = 0
for x in to[0].keys():
    if (0, x) in used: continue
    cntx = 0
    cnty = 0
    dfs(x, 0)
    ans += cntx * cnty
print(ans - n)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

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

        return self.p[x]

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

    def unite(self, x, y):
        u = self.find_root(x)
        v = self.find_root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def get_size(self, x):
        return self.size[self.find_root(x)]

n = int(input())
xy = [tuple(int(x) for x in input().split()) for _ in range(n)]

sx = set()
sy = set()

for x, y in xy:
    sx.add(x)
    sy.add(y)

dx = dict()
dy = dict()

for i, x in enumerate(sx):
    dx[x] = i

len_x = len(sx)
m = len(sx) + len(sy)

for i, y in enumerate(sy):
    dy[y] = i + len_x


uft = UnionFind(m)

for x, y in xy:
    uft.unite(dx[x], dy[y])

mx = [0] * m
my = [0] * m
for i in range(len_x):
    mx[uft.find_root(i)] += 1
for i in range(len_x, m):
    my[uft.find_root(i)] += 1

ans = 0
for i in range(m):
    ans += mx[i] * my[i]

print(ans - n)

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(20000)


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


class Group:
    
    def __init__(self):
        self.n = 0
        self.x = 0
        self.y = 0
        self.xy = {}
        
    def new_cor_n(self):
        return self.x * self.y - self.n
        

def grouping(group, x, xcor, ycor):
    x_list = []
    group.x += 1
    for y in xcor[x][0]:
        if (x, y) not in group.xy:
            group.n += 1
            group.xy[(x, y)] = None
        if ycor[y][1]:
            continue
        ycor[y][1] = True
        group.y += 1
        for x_ in ycor[y][0]:
            if (x_, y) not in group.xy:
                group.n += 1
                group.xy[(x_, y)] = None
            if xcor[x_][1]:
                continue
            xcor[x_][1] = True
            x_list.append(x_)
    return x_list

if N <= 2:
    print(0)
else:
    xcor, ycor = {}, {}
    for xi, yi in COR:
        if xi in xcor:
            xcor[xi][0].append(yi)
        else:
            xcor[xi] = [[yi], False]
        if yi in ycor:
            ycor[yi][0].append(xi)
        else:
            ycor[yi] = [[xi], False]
    group_list = []
    for i, v in xcor.items():
        if v[1]:
            continue
        group = Group()
        group_list.append(group)
        xcor[i][1] = True
        x_list = [i]
        while True:
            new_x_list = []
            for x in x_list:
                new_x_list += grouping(group, x, xcor, ycor)
            if new_x_list == []:
                break
            x_list = new_x_list
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    n = I()
    xy = [LI() for _ in range(n)]
    xd = {}
    yd = {}

    xi = 0
    yi = 0
    for x,y in xy:
        if x not in xd:
            xd[x] = xi
            xi += 1
        if y not in yd:
            yd[y] = yi
            yi += 1

    uf = UnionFind(xi+yi+n)
    ii = xi + yi
    for i in range(n):
        x,y = xy[i]
        uf.union(xd[x], ii + i)
        uf.union(xi + yd[y], ii + i)

    dx = collections.defaultdict(set)
    dy = collections.defaultdict(set)
    for i in range(n):
        x,y = xy[i]
        ui = uf.find(ii + i)
        dx[ui].add(x)
        dy[ui].add(y)

    r = -n
    for k,xv in dx.items():
        yv = dy[k]
        r += len(xv) * len(yv)

    return r


print(main())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
max_n = 10**5
ans = 0
n = int(input())

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.sizea = [1 if _ < n//2 else 0 for _ in range(n)]
        self.sizeb = [0 if _ < n//2 else 1 for _ in range(n)]
        self.sizec = [1 for _ in range(n)]
        self.rank = [0] * (n)
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def is_root(self, x):
        if self.par[x] == x:
            return True
        else:
            return False
    
    def union(self, 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.sizea[x] += self.sizea[y]
            self.sizeb[x] += self.sizeb[y]
            self.sizec[x] += self.sizec[y]
        else:
            self.sizec[x] += 1          

    def get_size(self, x):
        x = self.find(x)
        return self.sizea[x],self.sizeb[x],self.sizec[x]

uf = UnionFind(2*max_n)

for _ in range(n):
  x,y = map(int, input().split())
  x -= 1
  y += max_n - 1
  uf.union(x, y)

for i in range(max_n):
  if uf.is_root(i):
    a,b,c = uf.get_size(i)
    if a*b > 1:
      ans += a*b -(c-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

class UnionFind:
    def __init__(self, n):
        self.root = [i for i in range(n)]
        self.rank = [0] * n

    def find(self, x):
        if self.root[x] == x:
            return x
        else:
            y = self.find(self.root[x])
            self.root[x] = y
            return self.root[x]

    def unite(self, x, y):
        if self.is_same(x, y):
            return
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] < self.rank[ry]:
            self.root[rx] = ry
        else:
            self.root[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

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

def main():
    input = sys.stdin.readline
    V = 10**5  # max size of x
    N = int(input())
    uft = UnionFind(2*V)
    for _ in range(N):
        x, y = map(int, input().split())
        x -= 1
        y += V - 1
        uft.unite(x, y)

    cnt_x = defaultdict(lambda: 0)
    cnt_y = defaultdict(lambda: 0)
    for i in range(2*V):
        root = uft.find(i)
        if i < V:  # node of x coordinate.
            cnt_x[root] += 1
        else:
            cnt_y[root] += 1

    ans = 0
    for root in cnt_x.keys():
        ans += cnt_x[root] * cnt_y[root]

    return ans - N


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

Submission status: Accepted

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

def main():
    input = sys.stdin.readline
    V = 10**5  # max size of x
    N = int(input())
    bgraph = [[] for _ in range(2*V)]
    for _ in range(N):
        x, y = map(int, input().split())
        x -= 1
        y += V - 1
        bgraph[x].append(y)
        bgraph[y].append(x)

    def dfs(i):
        if visited[i]:
            return cnt
        visited[i] = True
        cnt[i//V] += 1
        for j in bgraph[i]:
            dfs(j)
        return cnt

    visited = [False] * (2*V)
    ans = 0
    for i in range(V):
        if visited[i]:
            continue
        cnt = [0, 0]
        cnt = dfs(i)
        ans += cnt[0] * cnt[1]

    ans -= N
    return ans


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

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()