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
input = sys.stdin.readline

from collections import deque

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

x_list = {}
y_list = {}
for i in range(1,10**5+1):
    x_list[i] = set()
    y_list[i] = set()

for i in range(n):
    x,y = xy[i]
    x_list[x].add(i)
    y_list[y].add(i)

remain = set(range(n))
ans = 0
while(len(remain) > 0):
    d = deque()
    d.append(remain.pop())
    num = 0
    xs = set()
    ys = set()
    while(len(d) > 0):
        tmp = d.pop()
        x,y = xy[tmp]
        num += 1
        xs.add(x)
        ys.add(y)
        while(len(x_list[x]) > 0):
            j = x_list[x].pop()
            if( j in remain):
                d.append(j)
                remain.remove(j)
        while(len(y_list[y]) > 0):
            j = y_list[y].pop()
            if(j in remain):
                d.append(j)
                remain.remove(j)

    ans += len(xs) * len(ys) - num

print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
XY = [lr() for _ in range(N)]
V = list(range(2 * 10**5 + 1)) # 1-indexed X coordinate、Y coordinateの順番

# Aでxの根を求める
def find(A,x):
    p = A[x]
    if p == x: return x
    a = find(A,p)
    A[x] = a
    return a
# Aでxとyの属する集合の併合
def union(A, x, y):
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[by] = bx # 根をbxに統一

for x, y in XY:
    y += 10**5
    if find(V, x) != find(V, y):
        union(V, x, y)

set_V = [set() for _ in range(2 * 10**5 + 1)] # 1-indexed
for x, y in XY:
    root = find(V, x)
    set_V[root] |= set([x, y+10**5])

set_V = [x for x in set_V if x]
answer = 0
for z in set_V:
    z = sorted(list(z))
    cnt_x = bisect_left(z, 10 ** 5 + 1)
    cnt_y = len(z) - cnt_x
    answer += cnt_x * cnt_y

answer -= N
print(answer)
# 48

Submission status: Accepted

Solution code:
#  --*-coding:utf-8-*--

def dsMakeSet(ds, x):
    ds[x] = x


def dsFind(ds, x):
    if ds[x] == x:
        return x

    x0 = x
    while ds[x] != x:
        x = ds[x]

    ds[x0] = x
    return x


def dsUnion(ds, x, y):
    xRoot = dsFind(ds, x)
    yRoot = dsFind(ds, y)
    
    if xRoot != yRoot:
        ds[yRoot] = xRoot
        return True

    return False



N = int(input())
Q = {}

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

    X = ('x', x)
    Y = ('y', y)

    if not (X in Q):
        dsMakeSet(Q, X)

    if not (Y in Q):
        dsMakeSet(Q, ('y', y))
    
    dsUnion(Q, X, Y)

R = {}

for q in Q:
    root = dsFind(Q, q)
    
    if not(root in R):
        R[root] = [0, 0]

    r = R[root]
    if q[0] == 'x':
        r[0] += 1
    else:
        r[1] += 1

s = 0
for r in R.values():
    s += r[0]*r[1]

print(s - N)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n, t, s):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n + 1)
        self.sizex = [1] * t + [0] * s
        self.sizey = [0] * t + [1] * s

    # 検索
    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 sizeof(self, x):
        return self.sizex[self.find(x)] * self.sizey[self.find(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.par[x] = y
            self.sizex[y] += self.sizex[x]
            self.sizey[y] += self.sizey[x]
        else:
            self.par[y] = x
            self.sizex[x] += self.sizex[y]
            self.sizey[x] += self.sizey[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


def coordinate_compression(arr):
    return {v: k for k, v in enumerate(sorted(set(arr)))}


n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())
dx = coordinate_compression(x)
dy = coordinate_compression(y)
uf = UnionFind(len(dx) + len(dy), len(dx), len(dy))
for i in range(n):
    uf.unite(dx[x[i]], dy[y[i]] + len(dx))
s = set()
ans = 0
for i in range(len(dx)):
    p = uf.find(i)
    if p in s:
        continue
    ans += uf.sizeof(i)
    s.add(p)
print(ans - n)

Submission status: Accepted

Solution code:
# reference -> https://atcoder.jp/contests/abc131/submissions/10358162
import sys
sys.setrecursionlimit(100000)

# 再帰的に連結部分の辺の数を求める
# 同じ辺を2回ずつ数えるので、最終的には2で割る
def solve(x, x_set, y_set, x2y, y2x):
  num_e = 0
  if x in x2y:
    x_set.add(x)
    yl = x2y.pop(x)
    num_e += len(yl)
    for y in yl:
      num_e += solve(y, y_set, x_set, y2x, x2y)
  return num_e


N = int(input())
X2Y = {}
Y2X = {}
for i in range(N):
  x, y = map(int, input().split())
  if x in X2Y:
    X2Y[x].append(y)
  else:
    X2Y[x] = [y]
  if y in Y2X:
    Y2X[y].append(x)
  else:
    Y2X[y] = [x]


ans = 0
while X2Y:
    x = next(iter(X2Y)) # まだスタートに選んでいないxを取り出す
    x_set = set() # 上のxと連結であるxの集合
    y_set = set() # 上のxと連結であるyの集合
    num_e = solve(x, x_set, y_set, X2Y, Y2X)
    ans += len(x_set)*len(y_set) - num_e//2

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xtoy = {}
ytox = {}
for x, y in xy:
    if x not in xtoy:
        xtoy[x] = [y]
    else:
        xtoy[x].append(y)
    if y not in ytox:
        ytox[y] = [x]
    else:
        ytox[y].append(x)

def doit(x, xs, ys, xtoy, ytox):
    ret = 0
    if x in xtoy:
        xs.add(x)
        yl = xtoy.pop(x)
        ret += len(yl)
        for y in yl:
            ret += doit(y, ys, xs, ytox, xtoy)
    return ret

ret = 0
while len(xtoy) > 0:
    x = next(iter(xtoy))
    xs = set()
    ys = set()
    num = doit(x, xs, ys, xtoy, ytox)
    ret += len(xs) * len(ys) - num // 2

print(ret)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
s = set()
res = 0

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

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

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]

uf = UnionFind(2 * 10 ** 5)

for _ in range(N):
  u, v = map(int, input().split())
  s.add(u)
  uf.Unite(u, v + 10 ** 5)

ss = set()
c = [0] * (2 * 10 ** 5 + 1)
for x in s:
  y = uf.Find_Root(x)
  ss.add(y)
  c[y] += 1
for x in ss:
  t = uf.Count(x)
  xc = c[x]
  yc = t - xc
  res += xc * yc
print(res - N)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,size):
        self.table=[-1]*size
    def root(self,x):
        while self.table[x]>=0:
            x=self.table[x]
        return x
    def unite(self,x,y):
        s1=self.root(x)
        s2=self.root(y)
        if s1!=s2:
            if self.table[s1]>self.table[s2]:
                s1,s2=s2,s1
            self.table[s1]+=self.table[s2]
            self.table[s2]=s1
        return
    def same(self,x,y):
        return self.root(x)==self.root(y)
    def size(self,x):
        return -self.table[self.root(x)]
n,*z=map(int,open(0).read().split())
u=UnionFind(10**5*2+1)
for x,y in zip(*[iter(z)]*2):
    u.unite(x,10**5+y)
d=[[0,set(),set()]for _ in range(10**5*2+1)]
for x,y in zip(*[iter(z)]*2):
    t=d[u.root(x)]
    t[0]+=1
    t[1].add(x)
    t[2].add(y)
print(sum(len(x)*len(y)-a for a,x,y in d))

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():
    N=I()
    XY=LLIN(N)
    MAX_XY = 10**5+1
    uf=UnionFind((MAX_XY)*2)
    get_root, unite, nodes=uf.get_root, uf.unite, uf.nodes
    
    """ 
    http://drken1215.hatenablog.com/entry/2019/06/23/004700
    ・二部グラフにして
    ・連結成分ごとに
    ・完全二部グラフにするように辺を追加する(この二部グラフの辺(x,y)はグリッド上の点(x,y)に対応する)
    """
    

    for x,y in XY:
        unite(x,y+MAX_XY)
    
    cnt_x = defaultdict(int)
    cnt_y = defaultdict(int)
    
    for x in range(MAX_XY):
        cnt_x[ get_root(x) ] += 1
    for y in range(MAX_XY,2*MAX_XY):
        cnt_y[ get_root(y) ] += 1
    
    ans = 0
    #rootが根の連結成分に含まれる(X座標の数)*(Y座標の数)だけ辺がある(もとからあるものは後で引く)
    for root in range(2*MAX_XY):
        ans += cnt_x[root] * cnt_y[root]
    
    ans -= N #もとからN個の辺はある
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import defaultdict

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)
        # あるノードを根とする集合に属するノード数
        self.size = [1] * (n+1)
        # あるノードを根とする集合が木かどうか
        self.tree = [True] * (n+1)

    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 union(self, x, y):
        """ 併合 """
        # 根を探す
        x = self.find(x)
        y = self.find(y)

        # 木かどうかの判定用
        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def is_same(self, x, y):
        """ 同じ集合に属するか判定 """
        return self.find(x) == self.find(y)

    def get_size(self, x=None):
        if x is not None:
            """ あるノードの属する集合のノード数 """
            return self.size[self.find(x)]
        else:
            """ 集合の数 """
            res = set()
            for i in range(self.n+1):
                res.add(self.find(i))
            # グループ0の分を引いて返却
            return len(res) - 1
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

MAX = 10 ** 5
N = INT()
uf = UnionFind(MAX * 2)
edges = []
for i in range(N):
    x, y = MAP()
    edges.append((x, y))
    uf.union(x, y+MAX)

# 連結成分Sが持つ辺の数i,xの頂点数j,yの頂点数k
# D[S] = (i, j, k)
D = defaultdict(lambda: [0, 0, 0])
# 辺の集計
for x, y in edges:
    D[uf.find(x)][0] += 1
# 頂点の集計
for x in range(1, MAX+1):
    y = x + MAX
    D[uf.find(x)][1] += 1
    D[uf.find(y)][2] += 1

ans = 0
# 各連結成分についての、追加できる辺の数を合計する
for edgecnt, xcnt, ycnt in D.values():
    # 追加できる辺の数 = 完全2部グラフの辺数 - 既にある辺の数
    ans += xcnt * ycnt - edgecnt
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq
sys.setrecursionlimit(100000)

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
class union_find:
    def __init__(self, n):
        self.N = n
        self._parent = [i for i in range(self.N)]
        self._mem = [1] * self.N
        self.compo = self.N

    def parent(self, a):
        if self._parent[a] == a:
            return a
        self._parent[a] = self.parent(self._parent[a])
        return self._parent[a]

    def united(self,a, b):
        return self.parent(a) == self.parent(b)
    
    def unite(self,a, b):
        a = self.parent(a)
        b = self.parent(b)
        if(a == b): return False
        if self._mem[a] > self._mem[b]: a, b = b, a
        self._parent[a] = b
        self._mem[b] += self._mem[a]
        self.compo -= 1
        return True
    
    def is_root(self,a):
        return a == self._parent[a]
    def mem_cnt(self,a):
        return self._mem[self.parent(a)]
    def dump(self):
        print(self._parent)



def main():
    N = ri()
    X = [0] * N
    Y = [0] * N
    for i in range(N):
        X[i], Y[i] = rip()
    
    uf = union_find(N)
    di = dict()
    for i in range(N):
        if not X[i] in di: di[X[i]] = i
        uf.unite(i, di[X[i]])
    di.clear()
    for i in range(N):
        if not Y[i] in di: di[Y[i]] = i
        uf.unite(i, di[Y[i]])

    hx = [set() for i in range(N)]
    hy = [set() for i in range(N)]
    for i in range(N):
        hx[uf.parent(i)].add(X[i])
        hy[uf.parent(i)].add(Y[i])
    
    tot = 0
    for i in range(N):
        tot += len(hx[i]) * len(hy[i])
    
    print(tot - N)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
class UnionFind:
    def __init__(self, num):
        self.table = [-1 for _ in range(num)]

    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

N = int(input())
dx = defaultdict(list)
dy = defaultdict(list)
xy = []

for i in range(N):
    x,y = map(int,input().split())
    dx[x].append(i)
    dy[y].append(i)
    xy.append([x,y])

u = UnionFind(N)

for x in dx:
    i = dx[x][0]
    for j in dx[x]:
        u.union(i,j)

for y in dy:
    i = dy[y][0]
    for j in dy[y]:
        u.union(i,j)

dx = defaultdict(list)
dy = defaultdict(list)

for i in range(N):
    dx[u.find(i)].append(xy[i][0])
    dy[u.find(i)].append(xy[i][1])

ans = -N
for i in dx:
    ans += len(set(dx[i]))*len(set(dy[i]))

print(ans)

Submission status: Accepted

Solution code:

def wantp(n):

    q = []
    while p[n] != n:
        q.append(n)
        n = p[n]

    for i in q:
        p[i] = n

    return n

N = int(input())

oXYi = []
XYi = []
YXi = []

for i in range(N):

    x,y = map(int,input().split())
    oXYi.append([x,y,i])
    XYi.append([x,y,i])
    YXi.append([y,x,i])

p = [i for i in range(N)]
rank = [1] * N

XYi.sort()
YXi.sort()


li = -1
for i in range(N):

    if XYi[i][0] != XYi[li][0]:
        li = i

    else:
        ti = XYi[i][2]
        tli = XYi[li][2]
        ip = wantp(ti)
        lip = wantp(tli)

        if ip != lip:
        
            if rank[ip] < rank[lip]:
                p[ip] = lip
            elif rank[ip] > rank[lip]:
                p[lip] = ip
            else:
                p[lip] = ip
                rank[ip] += 1

li = -1
for i in range(N):

    if YXi[i][0] != YXi[li][0]:
        li = i

    else:
        ti = YXi[i][2]
        tli = YXi[li][2]
        ip = wantp(ti)
        lip = wantp(tli)
        
        if ip != lip:
        
            if rank[ip] < rank[lip]:
                p[ip] = lip
            elif rank[ip] > rank[lip]:
                p[lip] = ip
            else:
                p[lip] = ip
                rank[ip] += 1       

ndic = {}
xkazu = {}
ykazu = {}

for i in range(N):

    np = wantp(i)
    if np not in ndic:
        ndic[np] = 1
    else:
        ndic[np] += 1

    if np not in xkazu:
        xkazu[np] = {}
        ykazu[np] = {}

    xkazu[np][oXYi[i][0]] = 1
    ykazu[np][oXYi[i][1]] = 1

ans = 0

for i in ndic:
    ans += len(xkazu[i]) * len(ykazu[i]) - ndic[i]

print (ans)

Submission status: Accepted

Solution code:
class UnionFind:
    # 初期化
    def __init__(self, n):
        # 根なら-size, 子なら親の頂点
        self.par = [-1] * n
        # 木の高さ
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 異なる集合に属する場合のみ併合
        if x != y:
            # 高い方をxとする。
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            # 同じ高さの時は高さ+1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # yの親をxとし、xのサイズにyのサイズを加える
            self.par[x] += self.par[y]
            self.par[y] = x

    # 同集合判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.par[self.find(x)]


import operator

n = int(input())
z = [list(map(int, input().split())) for i in range(n)]

for i in range(n):
    z[i].append(i)

u = UnionFind(n)
z.sort()
for i in range(1,n):
    if z[i][0]==z[i-1][0]:
        u.unite(z[i][2],z[i-1][2])

z.sort(key=operator.itemgetter(1))
for i in range(1,n):
    if z[i][1]==z[i-1][1]:
        u.unite(z[i][2],z[i-1][2])

l = [[]for i in range(n)]

z.sort(key=operator.itemgetter(2))
for i in range(n):
    l[u.find(i)].append(z[i])

ans = 0
for i in range(n):
    if l[i]!=[]:
        x = set()
        y = set()
        for a in l[i]:
            if a[0] not in x:
                x.add(a[0])
            if a[1] not in y:
                y.add(a[1])
        ans += len(x)*len(y)-len(l[i])
print(ans)

Submission status: Accepted

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

def find_parent(i):
    aaa=0
    while True:
        if parent[i]<0:
            aaa=i
            break
        else:
            i=parent[i]
    return aaa

def connect(A,B):
    A=find_parent(A)
    B=find_parent(B)
    if A!=B:
        p_A,p_B=parent[A],parent[B]
        if p_A<p_B:
            parent[A]+=p_B
            parent[B]=A
            child[A].append(B)
        else:
            parent[B]+=p_A
            parent[A]=B
            child[B].append(A)

n=int(input())
x_max=0
y_max=0
xy=[]
for _ in range(n):
    x,y=map(int,input().split())
    x_max=max(x_max,x)
    y_max=max(y_max,y)
    xy.append([x,y])
data=[[] for _ in range(x_max+1)]
parent=[-1]*(x_max+1)
child=[[] for i in range(x_max+1)]
lst=[0]*(y_max+1)
for x,y in xy:
    data[x].append(y)
    if lst[y]==0:
        lst[y]=x
    else:
        connect(lst[y],x)

lsls=[]
for i in range(1,x_max+1):
    if parent[i]>=0:
        continue
    if not data[i]:
        continue
    que=[i]
    h=[i]
    while que:
        u=que.pop()
        for v in child[u]:
            que.append(v)
            h.append(v)
    lsls.append(h)

ans=0
for u in lsls:
    L=len(u)
    flag=[0]*(y_max+1)
    cnt=0
    count=0
    for v in u:
        for w in data[v]:
            count+=1
            if flag[w]==0:
                flag[w]=1
                cnt+=1
    ans+=L*cnt-count

print(ans)

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    xy=[list(map(int,input().split())) for _ in [0]*n]
    ixy=[[i,x,y] for i,(x,y) in enumerate(xy)]
    class unionfind():
        #size:要素数,tree：unionfind木
        def __init__(self,size):#self,要素数
            self.size=size
            self.tree_root=list(range(self.size))
            self.tree_depth=[1]*self.size
        
        #rootを探す
        def root(self,index):
            temp_list=[]
            temp=self.tree_root[index]
            while index!=temp:
                temp_list.append(index)
                index=temp
                temp=self.tree_root[index]
            for i in temp_list:
                self.tree_root[i]=index
            return index
        
        #結合
        def unite(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            if r1!=r2:
                d1,d2=self.tree_depth[r1],self.tree_depth[r2]
                if d1<=d2:
                    self.tree_root[r1]=r2
                    self.tree_depth[r2]=max(d1+1,d2)
                else:
                    self.tree_root[r2]=r1
                    self.tree_depth[r1]=max(d2+1,d1)
    
        #同じか判定
        def same(self,index1,index2):
            r1=self.root(index1)
            r2=self.root(index2)
            return r1==r2
    
        #連結成分の個数
        def component(self):
            return len({self.root(i) for i in range(self.size)})

    u=unionfind(n)
    ixy.sort(key=lambda x:x[1])
    for i in range(n-1):
        if ixy[i][1]==ixy[i+1][1]:
            u.unite(ixy[i][0],ixy[i+1][0])
    ixy.sort(key=lambda x:x[2])
    for i in range(n-1):
        if ixy[i][2]==ixy[i+1][2]:
            u.unite(ixy[i][0],ixy[i+1][0])
    tate=[set() for _ in [0]*n]
    yoko=[set() for _ in [0]*n]
    cnt=[0]*n
    for i in range(n):
        r=u.root(i)
        tate[r].add(xy[i][0])
        yoko[r].add(xy[i][1])
        cnt[r]+=1
    print(sum([len(tate[i])*len(yoko[i])-cnt[i] for i in range(n)]))
main()

Submission status: Accepted

Solution code:
class UnionFindTree:
    """Disjoint-Set Data Structure
       Union-Find Tree
       complexity:
          init: O(n)
          find, unite, same: O(alpha(n))
       used in SRM505 div.2 900, ATC001 A, DSL1A(AOJ)
    """
    def __init__(self, n):
        self.par = list(range(n))  # parent
        self.rank = [0] * n  # depth of tree

    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 unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N = int(input())
M = 10 ** 5
uft = UnionFindTree(2 * M)

for _ in range(N):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    uft.unite(x, y + M)
x_dict, y_dict = dict(), dict()
for x in range(M):
    par_x = uft.find(x)
    x_dict[par_x] = x_dict.get(par_x, 0) + 1
for y in range(M, 2 * M):
    par_y = uft.find(y)
    y_dict[par_y] = y_dict.get(par_y, 0) + 1
ans = -N
for r in x_dict.keys():
    ans += x_dict.get(r, 0) * y_dict.get(r, 0)
print(ans)

Submission status: Accepted

Solution code:
class UnionFindTree:
    """Disjoint-Set Data Structure
       Union-Find Tree
       complexity:
          init: O(n)
          find, unite, same: O(alpha(n))
       used in SRM505 div.2 900, ATC001 A, DSL1A(AOJ)
    """
    def __init__(self, n):
        self.par = list(range(n))  # parent
        self.rank = [0] * n  # depth of tree

    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 unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N = int(input())
M = 10 ** 5
uft = UnionFindTree(N + 2 * M)

for i in range(N):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    uft.unite(i, x + N)
    uft.unite(i, y + N + M)
x_dict, y_dict = dict(), dict()
for x in range(N, M + N):
    par_x = uft.find(x)
    x_dict[par_x] = x_dict.get(par_x, 0) + 1
for y in range(N + M, N + 2 * M):
    par_y = uft.find(y)
    y_dict[par_y] = y_dict.get(par_y, 0) + 1
ans = -N
for r in x_dict.keys():
    ans += x_dict.get(r, 0) * y_dict.get(r, 0)
print(ans)

Submission status: Accepted

Solution code:
import sys,os,math
from collections import Counter, defaultdict, deque, OrderedDict
import bisect
from sys import stdin, stdout
from itertools import repeat
import Queue


# sys.stdin = open('input')
# n, k = map(int, raw_input().split())
# da = map(int, raw_input().split())
# db = map(int, raw_input().split())


def main():
    n = map(int, raw_input().split())[0]
    G = defaultdict(list)
    bfs = []
    for i in range(n):
        a, b = map(int, raw_input().split())
        b += 100000
        G[a].append(b)
        G[b].append(a)
        bfs.append(a)

    vs = set()
    ans = 0
    for i in bfs:
        if i in vs:
            continue
        x, y = 0, 0
        t = 0
        vs.add(i)
        q = deque()
        q.append(i)
        while q:
            now = q.popleft()
            if now > 100000:
                y += 1
            else:
                x += 1
            for adj in G[now]:
                t += 1
                if adj not in vs:
                    # print adj
                    vs.add(adj)
                    q.append(adj)
        # print x, y, t/2
        ans += x*y - t/2
    print ans




main()