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:
# 二部ぐらふ、知らなかった
from collections import defaultdict


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)

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


N = int(input())
U = UnionFind(2*10**5)
for i in range(N):
    x, y = map(int, input().split())
    U.union(x, y+10**5)
ans = 0
Roots = U.roots()
D = {x: [] for x in Roots}
for i in range(2*10**5+1):
    D[U.find(i)].append(i)
for x in Roots:
    ss = D[x]
    sx = 0
    sy = 0
    for c in ss:
        if c <= 10**5:
            sx += 1
        else:
            sy += 1
    ans += sx*sy
ans -= N
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
n = int(input())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
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())
unionfind = UnionFind(n)
x_d = defaultdict(set)
y_d = defaultdict(set)
for i in range(n):
    x_d[data[i][0]].add(i)
    y_d[data[i][1]].add(i)

for i in range(n):
    x, y = data[i]
    if len(x_d[x]) > 1 and len(y_d[y]) > 1:
        for j in x_d[x]:
            unionfind.union(i, j)
        for j in y_d[y]:
            unionfind.union(i, j)

point = [[] for i in range(n)]
for i in range(n):
    if unionfind.size(i) <= 2:
        continue
    else:
        point[unionfind.find(i)].append(i)
ans = 0
for i in range(n):
    if len(point[i]) > 2 :
        x_s = set()
        y_s = set()
        for j in point[i]:
            x, y = data[j]
            x_s.add(x)
            y_s.add(y)
        ans += len(x_s) * len(y_s) - len(point[i])
print(ans)

Submission status: Accepted

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    # xとyに分けるとなんか二部グラフが見えてくる
    # 違うんか。。
    def bfs(V,used,s=0):
        W = {}
        W[s] = 1
        que = deque([s])
        while(que):
            now = que.pop()
            used[now] = True
            ne = W[now]*(-1)
            for v in V[now]:
                if v not in W:
                    W[v] = ne
                    que.append(v)
                elif W[v]!=ne:
                    return False
        return W,used
    y_shift = 10**5 + 1
    N = I()
    V = defaultdict(set)
    for _ in range(N):
        x, y = LI()
        y += y_shift
        V[x].add(y)
        V[y].add(x)

    ans = 0
    used = defaultdict(lambda:False)
    for i in V.keys():
        if used[i]:
            continue
        W,used = bfs(V,used,i)
        x = 0
        for w in W.values():
            if w==1:
                x += 1
        y = len(W)-x
        #print(W,x,y)
        ans += x*y
    ans = max(0,ans-N)
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    MAXS = 100005
    N = int(input())
    X = [set() for _ in range(MAXS)]
    Y = [set() for _ in range(MAXS)]
    for _ in range(N):
        x,y = map(int,input().split())
        X[x].add(y)
        Y[y].add(x)
    
    used_x = [0] * MAXS
    used_y = [0] * MAXS
    ans = -N
    for i in range(MAXS):
        if used_x[i]:
            continue
        used_x[i] = 1
        if not X[i]:
            continue
        max_height = set(X[i])
        max_width = {i}
        stack = [(i,0)]
        while stack:
            v,typ = stack.pop()
            if typ == 0:
                for y in X[v]:
                    if used_y[y]:
                        continue
                    used_y[y] = 1
                    if Y[y]:
                        max_width |= Y[y]
                        stack.append((y,1))
            else:
                for x in Y[v]:
                    if used_x[x]:
                        continue
                    used_x[x] = 1
                    if X[x]:
                        max_height |= X[x]
                        stack.append((x,0))
        ans += len(max_width) * len(max_height)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import product
sys.setrecursionlimit(10**8)


INF = float("inf")


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

    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 compress(X, Y):
    dx = list(sorted(set(X)))
    dx_inv = {x: i for i, x in enumerate(dx)}
    dy = list(sorted(set(Y)))
    dy_inv = {y: i for i, y in enumerate(dy)}
    return (dx, dy), (dx_inv, dy_inv)


def main():
    N = int(input())
    X = [0]*N
    Y = [0]*N
    for i in range(N):
        X[i], Y[i] = map(int, input().split())

    (decx, decy), (encx, ency) = compress(X, Y)

    H = len(decx)
    uf = UnionFind(len(decx) + len(decy))

    for i in range(N):
        x, y = encx[X[i]], ency[Y[i]]+H
        # print(x, y)
        uf.union(x, y)

    dx = {}
    for i in range(len(decx)):
        key = uf.find(i)
        if key not in dx:
            dx[key] = 1
        else:
            dx[key] += 1
    dy = {}
    for i in range(H, H+len(decy)):
        key = uf.find(i)
        if key not in dy:
            dy[key] = 1
        else:
            dy[key] += 1
    # print(dx, dy)
    # print(uf.all_group_members())
    ans = 0
    for key in dx:
        if key in dy:
            ans += dy[key]*dx[key]
    print(ans-N)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
D = 100000
d = {i:[] for i in range(1, 2*D+1)}
cd = set()
used = [0]*(2*D+1)
ans = 0

for _ in range(N):
    x, y = map(int, input().split())
    y += D
    cd.add(x)
    d[x].append(y)
    d[y].append(x)

for x in cd:
    if used[x]:continue
    q = [x]
    used[x] = 1
    cx, sx = 0, 0

    while q:
        a = q.pop()
        if a<=D:
            cx += 1
        sx += 1
        for b in d[a]:
            if used[b]:continue
            used[b] = 1
            q.append(b)
    ans += cx*(sx-cx)

print(ans-N)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
d = defaultdict(list)
cd = set()
D = 100000
used = [0]*(2*D+1)
ans = 0

for _ in range(N):
    x, y = map(int, input().split())
    y += D
    cd.add(x)
    d[x].append(y)
    d[y].append(x)

for x in cd:
    if used[x]:continue
    q = [x]
    used[x] = 1
    cx, sx = 0, 0

    while q:
        a = q.pop()
        if a<=D:
            cx += 1
        sx += 1
        for b in d[a]:
            if used[b]:continue
            used[b] = 1
            q.append(b)
    ans += cx*(sx-cx)

print(ans-N)

Submission status: Accepted

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

# 連結成分ごとに
# x,yの二部グラフを完全二部グラフにする
# cnt(x)*cnt(y)-既存の辺数の総和

# 最後にN引けばよい

Submission status: Accepted

Solution code:
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):  # xとy+Mのsetの方が確認する数は減る?
        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()

# 連結成分ごとに
# x,yの二部グラフを完全二部グラフにする
# cnt(x)*cnt(y)-既存の辺数の総和

# 最後にN引けばよい

Submission status: Accepted

Solution code:
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)
        # ans += (sz - x) * x - (sz - 1) # sz-1は木に限られるのでWA

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


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)

Submission status: Accepted

Solution code:
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  # root2に結合
            self.size[root2] += self.size[root1]
        else:
            self.parent[root2] = root1  # 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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
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()

Submission status: Accepted

Solution code:
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
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    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
        #[x座標, 軸の方向]
        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()

Submission status: Accepted

Solution code:
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
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

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

Submission status: Accepted

Solution code:
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() # dfsをやりたいのでpopleftではなく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()