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:
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())
N = int(input())
xtoy = [-1]*(10**5+1)
uf = UnionFind(10**5+1)
xy = []
for i in range(N):
    x,y = map(int,input().split())
    if xtoy[x] == -1:
        xtoy[x] = y
    xy.append((x,y))
for x,y in xy:
    uf.union(y,xtoy[x])
ans = -N
for i in range(10**5+1):
    if xtoy[i] != -1:
        ans += uf.size(xtoy[i])
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
from operator import itemgetter
input = sys.stdin.readline

def main():
    n = int(input())
    p = [list(map(int, input().split()))+[i] for i in range(n)]
    tree = [[] for _ in range(n)]
    
    p.sort()
    for i in range(n-1):
        if p[i][0] == p[i+1][0]:
            tree[p[i][2]].append(p[i+1][2])
            tree[p[i+1][2]].append(p[i][2])

    p.sort(key=itemgetter(1))
    for i in range(n-1):
        if p[i][1] == p[i+1][1]:
            tree[p[i][2]].append(p[i+1][2])
            tree[p[i+1][2]].append(p[i][2])

    p.sort(key=itemgetter(2))

    
    already = [False]*n
    ans = -n
    for i in range(n):
        if already[i]:
            continue
        already[i] = True
        not_yet = deque([i])
        key_x = {p[i][0]}
        key_y = {p[i][1]}
        while not_yet:
            key = not_yet.popleft()
            for v in tree[key]:
                if already[v]:
                    continue
                already[v] = True
                key_x.add(p[v][0])
                key_y.add(p[v][1])
                not_yet.append(v)
        ans += len(key_x)*len(key_y)
    
    print(ans)
        
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys


sys.setrecursionlimit(10 ** 6)


def main():
    N = int(input())
    V = 100005
    to = defaultdict(list)
    for _ in range(N):
        X, Y = map(int, input().split())
        Y += V
        to[X].append(Y)
        to[Y].append(X)
    visited = [0] * (2 * V)
    cnt = [0] * 2  # cnt = [cnt of X, cnt of Y]

    def dfs(v):
        if visited[v] == 1:
            return
        visited[v] = 1
        cnt[v // V] += 1
        for nv in to[v]:
            dfs(nv)

    ans = 0
    for v in range(2 * V):
        if visited[v] == 1:
            continue
        cnt = [0] * 2
        dfs(v)
        ans += cnt[0] * cnt[1]
    ans -= N

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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()}

(n,), *q = [[*map(int,o.split())] for o in open(0)]
MAX = 10 ** 5 + 1
UF = UnionFind(2 * MAX)
for x, y in q:
    UF.union(x, y + MAX)
cnt_x = [0] * (2 * MAX)
cnt_y = cnt_x[:]
for i in range(MAX):
    cnt_x[UF.find(i)] += 1
    cnt_y[UF.find(i + MAX)] += 1
print(sum(X * Y for X, Y in zip(cnt_x, cnt_y)) - n)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    """
    二部グラフに変換，x,yそれぞれのグループにわけ，座標の値を点で，点の情報を辺で表す．
    連結成分の中で全部辺を繋ぐ
    """
    ################
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        重いかも！　　members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        重いかも！　all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        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())

    ################
    
    M=10**5
    N=I()
    
    uf=UnionFind(2*M)
    for i in range(N):
        x,y=MI()
        x-=1
        y-=1
        y+=M
        uf.union(x,y)#辺を張る
        
    from collections import defaultdict
    ddx = defaultdict(int)
    ddy = defaultdict(int)
    
    for i in range(M):
        root=uf.find(i)
        ddx[root]+=1
        
        root=uf.find(i+M)
        ddy[root]+=1
        
    ans=-N
    
    roots=uf.roots()

    
    for v in roots:
        x=ddx[v]
        y=ddy[v]
        ans+=x*y
        
    print(max(ans,0))
    
    
    

main()

Submission status: Accepted

Solution code:
n=int(input())

class UnionFind():
    def __init__(self,num):
        self.n = num         #class内変数nに、外部から入力した値numを代入
        self.parents = [-1 for i in range(self.n)]
          #parentsは要素の親(1こ上のやつ)番号0~n-1を格納、自分が最親なら-(要素数)を格納(初期値は-1)

    #xの最親は誰？
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x]) #再帰して1番上までいってる
                #調べながらparentsの値を更新してる！（経路圧縮）
            return self.parents[x]

    #結合せよ
    #xの親とyの親をくっつける
    def union(self,x,y):
        xx=self.find(x)  #xxはxの最親
        yy=self.find(y)  #yyはyの最親
        if xx==yy:
            return     #同じ屋根の下にあった場合は何もしない
        else:
            size_xx=abs(self.parents[xx]) #xが含まれる木のサイズ
            size_yy=abs(self.parents[yy]) #yが含まれる木のサイズ
            if size_xx>size_yy:
                xx,yy=yy,xx  #yyの方が大きい木、ってことにする

            self.parents[yy]+=self.parents[xx] #大きい木のサイズ更新
            self.parents[xx]=yy   #サイズが小さい木を大きい木に接ぐ

    #xの属する木の大きさ（まあunionでも使ったけど）
    def size(self,x):
        xx=self.find(x)
        return abs(self.parents[xx])

    #xとyはこの空の続く場所にいますか　いつものように笑顔でいてくれますか　今はただそれを願い続ける
    def same(self,x,y):
        return 1 if self.find(x)==self.find(y) else 0

    #xと　同じ木にいる　メンバーは？
    def members(self,x):
        xx=self.find(x)
        return [i for i in range(self.n) if self.find(i)==xx]
             #ifの条件式に漏れたら無視

    #最親だけを並べあげる
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x < -1]
        #いやこれは天才すぎる、basisのenumerate.py参照

    #すべての最親について、メンバーを辞書で
    def all_group_members(self):
        return {r:self.members(r) for r in self.roots()}

    #グループ分けどうなりましたか、２重リストで
    def state_grouping(self):
        return list(self.all_group_members().values())

    #出力用
    def __str__(self):
        return "\n".join("{}: {}".format(r,self.members(r)) for r in self.roots())
        #"\n"はただの改行コード
        #str(辞書)を改行しながら表示する
        #print(インスタンス)で__str__に飛ぶ
        #出力過程で、membersで全要素にfindをしてる→逐一経路圧縮されてる！

uf=UnionFind(2*10**5)
ans=0
#uf.union(0,1)
#print(uf.parents)
for i in range(n):
    x,y=map(int,input().split())
    x-=1;y-=1;y+=10**5
    uf.union(x,y)
for p in uf.roots():
    l=uf.members(p) #メンバーズ
    tem= len([i for i in l if i>=10**5])
    ans+= (len(l)-tem)*tem
    #print(l , tem)
print(ans-n)
#

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.components = n  # 連結成分の数

    def root(self, x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            self.p[x] = y
            self.components -= 1
    
    def same(self, x,y):
        return (self.root(x) == self.root(y))

N = int(input())
MAX = 100010
UF = UnionFind(2*MAX)

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


cnt_x, cnt_y = [0]*(2*MAX), [0]*(2*MAX)

for i in range(MAX):
    cnt_x[UF.root(i)] += 1

for i in range(MAX,2*MAX):
    cnt_y[UF.root(i)] += 1

print(sum([cnt_x[i]*cnt_y[i] for i in range(2*MAX)]) - N)

Submission status: Accepted

Solution code:
n = int(input())

pos_max = 100000

dic = dict()

for _ in range(n):
    x, y = map(int, input().split())
    y += pos_max
    if not x in dic:
        dic[x] = set()
    if not y in dic:
        dic[y] = set()
    dic[x].add(y)
    dic[y].add(x)
checked = set()

count = 0
for x in dic:
    if x in checked:
        continue
    checked.add(x)

    member = {x}
    next_items = {x}
    while next_items:
        v = next_items.pop()
        member |= dic[v]
        next_items |= dic[v] - checked
        checked |= dic[v]
    x_n = sum(w <= pos_max for w in member)
    y_n = sum(w >  pos_max for w in member)
    count += x_n * y_n
print(count - n)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
xy = map(int, read().split())
XY = zip(xy, xy)

max_num = 10 ** 5
delta = 10 ** 5 + 10

graph = [[] for _ in range(max_num + delta + 1)]

for x, y in XY:
    graph[x].append(delta + y)
    graph[delta + y].append(x)

x_used = [False] * (max_num + 1)
y_used = [False] * (max_num + 1)


def dfs(idx):
    x_res = 0
    y_res = 0
    edgenum = 0
    stack = []
    stack.append(idx)
    if idx >= delta:
        y_used[idx % delta] = True
    else:
        x_used[idx] = True
    while stack:
        v = stack.pop()
        if v >= delta:
            # if y_used[v % delta]:
            #     continue
            # y_used[v % delta] = True
            y_res += 1
        else:
            # if x_used[v]:
            #     continue
            # x_used[v] = True
            x_res += 1
        for u in graph[v]:
            if u >= delta:
                if y_used[u % delta]:
                    continue
                y_used[u % delta] = True
            else:
                if x_used[u]:
                    continue
                x_used[u] = True
            edgenum += 1
            stack.append(u)
    res = x_res * y_res
    return res


ans = 0
for i in range(max_num + 1):
    if x_used[i]:
        continue
    temp = dfs(i)
    ans += temp

for i in range(max_num + 1):
    if y_used[i]:
        continue
    i += delta
    temp = dfs(i)
    ans += temp

print(ans - n)

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################

# Binary Indexed Tree
# Bit.add(i,x)    : add x at i-th value
# Bit.sum(i)      : get sum up to i-th value



show_flg=False
show_flg=True

ans=0


n=I()
g=defaultdict(list)
a=set()

for i in range(n):
    s,t=LI()
    g[-s].append(t)
    g[t].append(-s)
    a.add(-s)
    a.add(t)

cn=[]
v={i:0 for i in a}
for i in a:
    if v[i]:
        continue
    x,y=0,0
    
    v[i]=1
    q=[i]
    while q:
        c=q.pop()
        if c<0:
            x+=1
        else:
            y+=1
        for nb in g[c]:
            if v[nb]==0:
                v[nb]=1
                q.append(nb)
    cn+=(x,y),

ans=sum(i*j for i,j in cn)-n
print(ans)

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################

# Binary Indexed Tree
# Bit.add(i,x)    : add x at i-th value
# Bit.sum(i)      : get sum up to i-th value



show_flg=False
show_flg=True

ans=0

n=I()
g=defaultdict(list)
a=set()

for i in range(n):
    s,t=LI()
    g[-s].append(t)
    g[t].append(-s)
    a.add(-s)
    a.add(t)

cn=[]
v={i:0 for i in a}
for i in a:
    if v[i]:
        continue
    x,y=0,0
    
    if i<0:
        x+=1
    else:
        y+=1
    
    v[i]=1
    q=[i]
    while q:
        c=q.pop()
        for nb in g[c]:
            if v[nb]==0:
                v[nb]=1
                q.append(nb)
                if nb<0:
                    x+=1
                else:
                    y+=1
    cn+=(x,y),

ans=sum(i*j for i,j in cn)-n
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
M = 10**5

n = int(input())
G = [[] for _ in range(2*M+1)]
for _ in range(n):
  x, y = map(int, input().split())
  G[x].append(y+M)
  G[y+M].append(x)
seen = [False]*(2*M+1)
def dfs(v):
  stack = [v]
  seen[v] = True
  cnt_x, cnt_y = 0, 0
  while stack:
    v = stack.pop()
    if v <= M:
      cnt_x += 1
    else:
      cnt_y += 1
    for nv in G[v]:
      if seen[nv]:
        continue
      seen[nv] = True
      stack.append(nv)
  return cnt_x*cnt_y
ans = 0
for i in range(2*M+1):
  if not seen[i]:
    ans += dfs(i)
ans -= n
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    ################
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        重いかも！　　members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        重いかも！　all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        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())
        
    ################

    """
    解説放送のように，グラフを考える．
    X座標を表す点を10**5個
    Y座標を表す点を10**5個用意．
    座標を点，点をグラフの辺として表す
    """

    N=I()
    M=10**5
    XY=[0]*(2*M)
    uf=UnionFind(2*M)
    for i in range(N):
        x,y=MI()
        x-=1
        y-=1
        y+=M
        XY[x]+=1
        XY[y]+=1
        uf.union(x,y)
    
    #　各根要素に対して，xの要素数，yの要素数，入出する辺の本数をメモ
    from collections import defaultdict
    ddx = defaultdict(int)
    ddy = defaultdict(int)
    dde = defaultdict(int)
    
    for i in range(2*M):
        root=uf.find(i)
        if i<M:
            ddx[root]+=1
        else:
            ddy[root]+=1
        dde[root]+=XY[i]
        
    ans=0
    
    for k,v in dde.items():
        temp=ddx[k]*ddy[k]-v//2
        ans+=temp
        
    print(ans)
    
    
    

main()

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
# from bisect import bisect_left, bisect_right
# from itertools import combinations, permutations, product
# from heapq import heappush, heappop
# from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N = ri()
to = defaultdict(list)
V = 100005
X = []
for i in range(N):
	x, y = rl()
	X.append(x)
	y += V
	to[x].append(y)
	to[y].append(x)

ans = 0
visited = {}
for x in X:
	if x in visited: continue
	nx, ny = 0, 0
	queue = deque()
	queue.append(x)
	visited[x] = 1
	while queue:
		n = queue.pop()
		if n < V:
			nx += 1
		else:
			ny += 1
		for m in to[n]:
			if m in visited:
				continue
			visited[m] = 1
			queue.append(m)
	ans += nx*ny
print(ans-N)

Submission status: Accepted

Solution code:
N = int(input())

X = [[] for _ in range(10**5)]
Y = [[] for _ in range(10**5)]

P = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

for i in range(N):
    x, y = P[i]
    X[x].append(y)
    Y[y].append(x)

x_used = [0 for _ in range(10**5)]
y_used = [0 for _ in range(10**5)]
res = 0

for i in range(10**5):
    if x_used[i]:
        continue
    stack = [(0, i)]
    x_cnt = 1
    x_used[i] = 1
    y_cnt = 0
    edge = 0
    while stack:
        axis, node = stack.pop()
        if axis == 0:
            for adj in X[node]:
                edge += 1
                if y_used[adj]:
                    continue
                y_cnt += 1
                y_used[adj] = 1
                stack.append((1, adj))
        else:
            for adj in Y[node]:
                if x_used[adj]:
                    continue
                x_cnt += 1
                x_used[adj] = 1
                stack.append((0, adj))
    res += x_cnt * y_cnt - edge

print(res)

Submission status: Accepted

Solution code:
N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N)]

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

M = 10**5
uf = UnionFind(2*M)
for x,y in XY:
    a,b = x-1,y-1+M
    if uf.is_same(a,b): continue
    uf.unite(a,b)
for i in range(2*M):
    uf.root(i)

rt = []
for i in range(2*M):
    rt.append(uf.root(i))
from collections import Counter
xr = Counter(rt[:M])
yr = Counter(rt[M:])

ans = 0
for k,v in xr.items():
    ans += yr[k] * v
ans -= N
print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

dic={}
for i in range(n):
    x,y=xy[i]
    if (0,x) in dic:
        dic[(0,x)].append(y)
    else:
        dic[(0,x)]=[y]
    x,y=y,x
    if (1,x) in dic:
        dic[(1,x)].append(y)
    else:
        dic[(1,x)]=[y]
# print(dic)

lst=[[0]*(10**5+1) for i in range(2)]

ans=0
for x,y in xy:
    if lst[0][x]==1:
        continue
    lst[0][x]=1
    d=deque([(0,x)])
    xcnt,ycnt=0,0
    cnt=0
    while d:
        # print(d)
        now=d.popleft()
        if now[0]==0:
            xcnt+=1
        else:
            ycnt+=1
        for j in dic[now]:
            cnt+=1
            if lst[1-now[0]][j]==0:
                lst[1-now[0]][j]=1
                d.append((1-now[0],j))
    # print(xcnt,ycnt,cnt)
    ans+=xcnt*ycnt-cnt//2
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
V = set()
E = {}

for _ in range(N):
  x,y = map(int, input().split())
  y += 100010
  V.add(x)
  V.add(y)
  if x not in E:
    E[x] = [y]
  else:
    E[x].append(y)
  if y not in E:
    E[y] = [x]
  else:
    E[y].append(x)

#print(V)
#print(E)
## DFS
visited = [ False ] * 200020
willSearch = [ False ] * 200020
Q = deque()
ans = 0
for v in V:
  if visited[v]:
    continue

  Q.append(v)
  xcount, ycount = 0,0
  edge_count = 0
  while len(Q) > 0:
    now = Q.pop()
    visited[now] = True

    if now > 100005:
      ycount += 1
    else:
      xcount += 1
      
    for nxt in E[now]:
      edge_count += 1
      if visited[nxt] or willSearch[nxt]:
        continue
      #print(v,now,nxt)

      willSearch[nxt] = True

      Q.append(nxt)
  #print(v,xcount, ycount, edge_count)
  ans += xcount * ycount
  ans -= edge_count // 2
  
print(ans)

Submission status: Accepted

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

def dfs(G, F, crr, pre, ret, st):
    F[crr] = False
    if crr < 10**5:
        ret[0] += 1
    else:
        ret[1] += 1
    for nxt in G[crr]:
        if nxt == pre:
            continue
        p, q = crr, nxt
        if q < p:
            p, q = q, p
        if not (p, q) in st:
            st.add((p, q))
            ret[2] += 1
        if F[nxt]:
            dfs(G, F, nxt, crr, ret, st)

def main():
    n = int(input())
    G = [[] for _ in range(2 * 10**5)]
    for _ in range(n):
        x, y = map(int, input().split())
        x, y = x-1, y-1 + 10**5
        G[x].append(y)
        G[y].append(x)
    F = [True]*(2* 10**5)
    ans = 0
    st = set()
    for i in range(2 * 10**5):
        if F[i] and len(G[i]) > 0:
            tmp = [0]*3
            dfs(G, F, i, -1, tmp, st)
            ans += tmp[0] * tmp[1] - tmp[2]
    print(ans)

if __name__ == "__main__":
    main()