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
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

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

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

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

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

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

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

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

        # 双方にくっつけられる場合
        if x in x_to_index and y in y_to_index:
            s = uf.root(x_to_index[x])
            t = uf.root(y_to_index[y])
            xs, ys = potential[s]
            xt, yt = potential[t]
            # くっつけても意味が無い場合
            if s == t:
                uf.unite(i, s)
                potential[uf.root(i)] = [xs, ys]
            # くっつけると意味がある場合
            else:
                uf.unite(i, s)
                uf.unite(i, t)
                potential[uf.root(i)] = [xs + xt, ys + yt]
        # 片方にくっつけられる場合
        elif x in x_to_index:
            s = uf.root(x_to_index[x])
            xs, ys = potential[s]
            uf.unite(i, s)
            potential[uf.root(i)] = [xs, ys + 1]
        elif y in y_to_index:
            t = uf.root(y_to_index[y])
            xt, yt = potential[t]
            uf.unite(i, t)
            potential[uf.root(i)] = [xt + 1, yt]

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

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

    print(res)
resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

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

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

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

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

idx2 = defaultdict(int)

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

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

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

color = [0]*M
S = 0

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

print(S-N)

Submission status: Accepted

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

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

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

ans = ans - N
print(ans)

Submission status: Accepted

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

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

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


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

Submission status: Accepted

Solution code:
# https://drken1215.hatenablog.com/entry/2019/06/23/004700
# https://atcoder.jp/contests/abc131/submissions/7975278
# https://tjkendev.github.io/procon-library/python/union_find/union_find.html

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

    MX = 10 ** 5 + 10

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

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

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

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

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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://drken1215.hatenablog.com/entry/2019/06/23/004700
# https://tjkendev.github.io/procon-library/python/union_find/union_find.html

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

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

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

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

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

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

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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    def find(self, x):
        """
        xの属する木の根を返す
        このとき同時に経路圧縮して、探索途中のノードを全て根に繋ぎ直す
        """
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        """
        x, yのそれぞれ属する木Tx, Tyの根同士を繋ぐ
        このとき木の要素数が小さい方を大きい方に繋ぐ（rankではなくsizeを用いる）
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        """
        xの属する木の要素数を返す
        根の親を要素数の(-1)倍で定めておいたおかげでO(1)で取得可能
        """
        return -self.parents[self.find(x)]

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

    def members(self, x):
        """
        xの属する木の要素を列挙する
        """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """
        連結成分の代表元のリストを返す
        """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """
        連結成分の個数を返す
        """
        return len(self.roots())

    def all_group_members(self):
         """
         連結成分およびそれぞれの代表元をまとめた辞書を返す
         代表元がキーになってる
         """
         return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        """
        連結成分およびその代表元を出力
        """
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



def main():

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

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

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

    # UnionFind()の都合上頂点は0-indexedの番号列で管理したいので
    # 頂点に対して連番づけを行う
    d = defaultdict(int)
    num = 0
    for x in vertex_x:
        d[(0, x)] = num
        num += 1
    x_num = num
    for y in vertex_y:
        d[(1, y)] = num
        num += 1

    # ここからメイン
    uftree = UnionFind(num)
    for x, y in edge:
        uftree.union(d[(0, x)], d[(1, y)])

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



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
# UnionFind
class UnionFind():
    def __init__(self, n):
        self.nodes=[-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

    def get_root(self, x):
        # nodes[x]が負ならxが根
        if self.nodes[x] < 0:
            return x
        # 根に直接つなぎ直しつつ、親を再帰的に探す
        else:
            self.nodes[x]=self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        # 根が同じなら変わらない
        # if root_x == root_y:
        # pass
        if root_x != root_y:
            # 大きい木の方につないだほうが計算量が減る
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root

def main():
    MAX_XY = 10**5
    N=I()
    XY=LLIN_(N)
    uf=UnionFind(2*MAX_XY)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes
    
    for x,y in XY:
        unite(x,y+MAX_XY)
    x_cnt = defaultdict(int)
    y_cnt = defaultdict(int)
    for x in range(MAX_XY):
        x_cnt[get_root(x)] += 1
    for y in range(MAX_XY,2*MAX_XY):
        y_cnt[get_root(y)] += 1
    
    ans = 0
    for x in range(MAX_XY):
        if(get_root(x)==x):
            ans += x_cnt[x]*y_cnt[x]
        y = x+MAX_XY
        if(get_root(y)==y):
            ans += x_cnt[y]*y_cnt[y]
    ans-=N
    print(ans)
if __name__ == '__main__':
    main()

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.component = 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.component -= 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)]

    def getComponent(self) :
        return self.component

N = int(input())
R = 10**5 + 10
IXY = []

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

X = [[] for _ in range(R)]
Y = [[] for _ in range(R)]
for i, x, y in IXY:
    X[x].append(i)
    Y[y].append(i)

tree = UnionFind(N)

for x in X:
    for fr, to in zip(x, x[1:]):
        tree.union(fr, to)
for y in Y:
    for fr, to in zip(y, y[1:]):
        tree.union(fr, to)

G = [[0, set(), set()] for _ in range(N)]
for i, x, y in IXY:
    r = tree.root(i)
    G[r][0] += 1
    G[r][1].add(x)
    G[r][2].add(y)

ans = 0
for grp in G:
    if grp[0] < 3:
        continue
    x = len(grp[1])
    y = len(grp[2])
    A = x * y
    ans += max(0, A - grp[0])
print(ans)

Submission status: Accepted

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        """ N個のノードのUnion-Find木を作成する """
        # 親の番号を格納する。自分が親だった場合は、自分の番号になり、それがそのグループの番号になる
        self._parent = [n for n in range(0, N)]
        # グループのサイズ（個数）
        self._size = [1] * N

    def find_root(self, x):
        """ xの木の根(xがどのグループか)を求める """
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x]) # 縮約
        return self._parent[x]

    def unite(self, x, y):
        """ xとyの属するグループを併合する """
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        # 小さい方を大きい方に併合させる（木の偏りが減るので）
        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        """ xが属するグループのサイズ（個数）を返す """
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        """ xとyが同じ集合に属するか否か """
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        """ グループ数を計算して返す """
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

import sys

input=sys.stdin.readline

N=int(input())
uf=UnionFindVerSize(10**5+1)
X=[[] for i in range(0,10**5+1)]
Y=[[] for i in range(0,10**5+1)]
for i in range(0,N):
    x,y=map(int,input().split())
    X[x].append(y)
    Y[y].append(x)

for i in range(0,10**5+1):
    if len(Y[i])>1:
        for j in range(1,len(Y[i])):
            uf.unite(Y[i][0],Y[i][j])

xgroup=[(uf.find_root(i),i) for i in range(0,10**5+1)]
xgroup.sort()
ans=0
stack=[xgroup[0][1]]
g=xgroup[0][0]
for i in range(1,10**5+1):
    if xgroup[i][0]==g:
        stack.append(xgroup[i][1])
    else:
        yco=[]
        for j in range(0,len(stack)):
            yco+=X[stack[j]]
        yco=set(yco)
        ans+=len(stack)*len(yco)
        stack=[xgroup[i][1]]
        g=xgroup[i][0]
yco=[]
for j in range(0,len(stack)):
    yco+=X[stack[j]]
yco=set(yco)
ans+=len(stack)*len(yco)
print(ans-N)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    X, Y = {}, {}
    for _ in range(N):
        x, y = map(int, input().split())
        if x not in X:
            X[x] = set()
        X[x].add(y)
        if y not in Y:
            Y[y] = set()
        Y[y].add(x)
    r = 0
    while X:
        x, ys = X.popitem()
        tx = set([x])
        ty = set(ys)
        mx, my = set(), set(ys)
        while mx or my:
            while my:
                y = my.pop()
                mx |= Y.pop(y, set())
            tx |= mx
            while mx:
                x = mx.pop()
                my |= X.pop(x, set())
            ty |= my
        r += len(tx) * len(ty)
    return r - N

print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

N = int(input())
a = [-1] * (10**5+1)
uf = UnionFind(10**5+1)
xs = [set() for _ in range(10**5+1)]
for _ in range(N):
    x, y = map(int, input().split())
    if a[x] == -1:
        a[x] = y
    else:
        uf.unite(a[x], y)
    xs[y].add(x)

root = defaultdict(set)
for y in range(10**5+1):
    root[uf.find(y)] |= xs[y]
ans = 0
for y in range(10**5+1):
    ans += len(root[uf.find(y)]) - len(xs[y])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
n = int(input())
xy = [list(map(int,input().split())) for i in range(n)]
graph = [[] for i in range(2*10**5+1)]
ans = 0
for x,y in xy:
  y += 10**5
  graph[x].append(y)
  graph[y].append(x)
  ans -= 1
vis = [0 for i in range(2*10**5+1)]
for i in range(1,2*10**5+1):
  if vis[i]:
    continue
  stack = [i]
  nx = 0
  ny = 0
  while stack:
    x = stack.pop()
    if x > 10**5:
      ny += 1
    else:
      nx += 1
    vis[x] = 1
    for y in graph[x]:
      if not vis[y]:
        stack.append(y)
        vis[y] = 1
  ans += nx*ny
print(ans)

Submission status: Accepted

Solution code:
n = int(input())


class Vector:
    def __init__(self, a):
        self.a = a

    def __add__(self, b):
        c = []
        for i, j in zip(self.a, b.a):
            c.append(i + j)
        return Vector(c)


class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n
        self.rank = [1] * n
        self.count = [Vector([1, 0] if i % 2 == 0 else [0, 1])
                      for i in range(n)]

    def get_root(self, i):
        while self.parent[i] != -1:
            i = self.parent[i]
        return i

    def is_same_tree(self, i, j):
        return self.get_root(i) == self.get_root(j)

    def merge(self, i, j):
        i = self.get_root(i)
        j = self.get_root(j)
        if i == j:
            return

        if self.rank[i] > self.rank[j]:
            self.parent[j] = i
            self.rank[i] = max(self.rank[i], self.rank[j] + 1)
            self.count[i] += self.count[j]
        else:
            self.parent[i] = j
            self.rank[j] = max(self.rank[j], self.rank[i] + 1)
            self.count[j] += self.count[i]


uf = UnionFind(2 * 10 ** 5)
for _ in range(n):
    x, y = [int(i) - 1 for i in input().split()]
    uf.merge(2 * x, 2 * y + 1)

ans = 0
for i, j in zip(uf.count, uf.parent):
    if j == -1:
        a = i.a
        ans += a[0] * a[1]
print(ans - n)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.p = [e for e in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        u = self.find_set(u)
        v = self.find_set(v)

        if u == v:
            return

        if self.rank[u] > self.rank[v]:
            self.p[v] = u
            self.size[u] += self.size[v]
        else:
            self.p[u] = v
            self.size[v] += self.size[u]
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def update_p(self):
        for u in range(self.n):
            self.find_set(u)

    def get_size(self, u):
        return self.size[self.find_set(u)]


n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
MAX = 10 ** 5

uf = UnionFind(MAX * 2)

for x, y in xy:
    x -= 1
    y -= 1
    uf.unite(x, y + MAX)

x_size = [0] * MAX * 2
y_size = [0] * MAX * 2
for i in range(MAX * 2):
    root = uf.find_set(i)
    if i < MAX:
        x_size[root] += 1
    else:
        y_size[root] += 1

ans = -n
for i in range(MAX * 2):
    ans += x_size[i] * y_size[i]

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(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 same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
    
uf=unionfind(n)
import collections
dx=collections.defaultdict(int)
dy=collections.defaultdict(int)
l=[list(map(int,input().split())) for i in range(n)]
for i,j in enumerate(l,1):
    x,y=j
    if dx[x]:
        uf.unite(dx[x],i)
    else:
        dx[x]=i
    if dy[y]:
        uf.unite(dy[y],i)
    else:
        dy[y]=i
dx=collections.defaultdict(set)
dy=collections.defaultdict(set)
for i,j in enumerate(l,1):
    x,y=j
    dx[uf.find(i)].add(x)
    dy[uf.find(i)].add(y)
ans=0
for i,j in dx.items():
    ans+=len(j)*len(dy[i])-uf.count(i)
print(ans)

Submission status: Accepted

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.ps[x] > self.ps[y]:
            x, y = y, x
        self.ps[x] += self.ps[y]
        self.ps[y] = x
        return True

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

    def size(self, x):
        x = self.find(x)
        return -self.ps[x]

n = int(input())
v = 10**5 + 5
uf = UnionFind(v*2 + 10)
for _ in range(n):
  x, y = map(int, input().split())
  uf.unite(x, y+v)
d = dict()
for i in range(v*2):
  if uf.size(i) > 1:
    p = uf.find(i)
    if p not in d:
      d[p] = [0, 0]
    d[p][i > v] += 1
print(sum(x*y for x,y in d.values()) - n)

Submission status: Accepted

Solution code:
import bisect
import heapq
import sys
import queue


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


class V:
    def __init__(self, f):
        self.f = f
        self.v = None

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n)

    def get(self):
        return self.v


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def f(x, X, VX):
    visit_node = [set(), set()]
    visit_link = set()

    q = queue.Queue()
    q.put((0, x))
    while not q.empty():
        p, s = q.get()
        if s in visit_node[p]:
            continue

        visit_node[p].add(s)
        VX[p][s] = True
        for t in X[p][s]:
            l = (s, t) if p == 0 else (t, s)
            if l in visit_link:
                continue
            visit_link.add(l)

            if t in visit_node[1 - p]:
                continue
            q.put((1 - p, t))

    return len(visit_node[0]) * len(visit_node[1]) - len(visit_link)


def main():
    N = int(input())
    X = {}
    Y = {}

    for _ in range(N):
        x, y = read_values()
        x -= 1
        y -= 1
        X.setdefault(x, set()).add(y)
        Y.setdefault(y, set()).add(x)

    VX = [False] * (10 ** 5)
    VY = [False] * (10 ** 5)

    res = 0
    for x in X.keys():
        if VX[x]:
            continue

        res += f(x, [X, Y], [VX, VY])

    for y in Y.keys():
        if VY[y]:
            continue

        res += f(y, [Y, X], [VY, VX])

    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

n = int(input())
m = 10**5
G = [[] for i in range(2*m)]
for i in range(n):
    x,y = map(int, input().split())
    x,y = x-1, y-1
    G[x].append(m+y)
    G[m+y].append(x)

from collections import deque
used = [0]*(2*m)
def dfs(i):
    q = deque([i])
    x = 0
    y = 0
    edge = 0
    while q:
        cur = q.pop()
        if used[cur]:
            continue
        used[cur] = 1
        if cur<m:
            x += 1
        else:
            y += 1
        edge += len(G[cur])
        for to in G[cur]:
            if used[to] == 0:
                q.append(to)
    return x*y-edge//2

ans = 0
for i in range(2*m):
    if used[i]:
        continue
    ans += dfs(i)
print(ans)

Submission status: Accepted

Solution code:
# 長方形の4点のうち3点が必要なので自明からほど遠い
# x,yを2部グラフ、格子を辺とみなす
# 連結成分ごとに張られる......
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

mx =0
my = 0
for i in range(n):
    mx = max(mx,xy[i][0])
    my = max(my,xy[i][1])

*p, = range(mx+my+1)
rank = [1]*(mx+my+1)

for i in range(n):
    xy[i][1] += mx

def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    rx = rank[px]; ry = rank[py]
    if ry < rx:
        p[py] = px
    elif rx < ry:
        p[px] = py
    else:
        p[py] = px
        rank[px] += 1
    return 1

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

xp = [0]*(mx+my+1)
yp = [0]*(mx+my+1)

for i in range(mx+my+1):
    if i<=mx:
        xp[root(i)]+=1#p[i]では不十分
    else:
        yp[root(i)]+=1
ans = 0
for i in range(mx+my+1):
    ans += xp[i]*yp[i]
ans -= n
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xy = {}
for i in range(n):
  x,y = map(int,input().split())
  xy[x] = xy.get(x,[]) + [y]
d = {}
for x in xy:
  v0 = xy[x][0]
  while d.get(v0,v0) != v0:
    v0 = d[v0]
  for v in xy[x]:
    v1 = d.get(v,v)
    while d.get(v1,v1) != v1:
      v1 = d[v1]
    d[v1] = v0
for y in d:
  yp = d[y]
  y2 = [y]
  while yp != d[yp]:
    y2 += [yp]
    yp = d[yp]
  for y3 in y2:
    d[y3] = yp
e = {}
for y in d:
  e[d[y]] = e.get(d[y],0)+1
ans = 0
for x in xy:
  ans += e[d[xy[x][0]]] - len(xy[x])
print(ans)