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: Wrong Answer

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
n = int(input())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
unionfind = UnionFind(n)
x_d = defaultdict(set)
y_d = defaultdict(set)
for i in range(n):
    x_d[data[i][0]].add(i)
    y_d[data[i][1]].add(i)

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

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
n = int(input())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
unionfind = UnionFind(n)
x_d = defaultdict(set)
y_d = defaultdict(set)
for i in range(n):
    x_d[data[i][0]].add(i)
    y_d[data[i][1]].add(i)

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

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
x_d = defaultdict(int)
y_d = defaultdict(int)
for i in range(n):
    x_d[data[i][0]] += 1
    y_d[data[i][1]] += 1
ans = 0
for i in range(n):
    ans += (x_d[data[i][0]] - 1) * (y_d[data[i][1]] - 1)
print(ans)

Submission status: Wrong Answer

Solution code:
from networkx import*
def main():
    g=Graph()
    for a in[*open(x:=0)][1:]:
        a,b=map(int,a.split())
        g.add_edge(a,b+.5)
    for c in connected_components(g):
        s=g.subgraph(c)
        #a,b=map(len,bipartite.sets(s))
        x+=-s.size()
    print(x)
main()

Submission status: Wrong Answer

Solution code:
from networkx import*
def main():
    g=Graph()
    for a in[*open(x:=0)][1:]:
        a,b=map(int,a.split())
        g.add_edge(a,7**6+b)
    for c in connected_components(g):
        s=g.subgraph(c)
        #a,b=map(len,bipartite.sets(s))
        #x+=a*b-len(s.edges)
    print(x)
main()

Submission status: Wrong Answer

Solution code:
from networkx import*
def main():
    g=Graph()
    for a in[*open(x:=0)][1:]:
        a,b=map(int,a.split())
        g.add_edge(a,7**6+b)
    for c in connected_components(g):
        #a,b=map(len,bipartite.sets(s:=g.subgraph(c)))
        #x+=a*b-len(s.edges)
        None
    print(x)
main()

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

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

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

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

Submission status: Wrong Answer

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

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

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

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

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

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

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

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

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

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

Submission status: Wrong Answer

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

def main():
    MAXS = 100005
    N = int(input())
    X = [[] for _ in range(MAXS)]
    Y = [[] for _ in range(MAXS)]
    for _ in range(N):
        x,y = map(int,input().split())
        X[x].append(y)
        Y[y].append(x)
    
    used_x = [0] * MAXS
    used_y = [0] * MAXS
    ans = -N
    for i in range(MAXS):
        if used_x[i]:
            continue
        used_x[i] = 1
        max_wide = len(X[i])
        max_height = 1
        stack = [(x,0)]
        while stack:
            v,typ = stack.pop()
            if typ == 0:
                for y in X[v]:
                    if used_y[y]:
                        continue
                    used_y[y] = 1
                    if Y[y]:
                        max_height = max(max_height,len(Y[y]))
                        stack.append((y,1))
            else:
                for x in Y[v]:
                    if used_x[x]:
                        continue
                    used_x[x] = 1
                    if X[x]:
                        max_wide = max(max_wide,len(X[x]))
                        stack.append((x,0))
        ans += max_wide * max_height

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
d = defaultdict(list)
candidate_x = set()

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

used = [False]*(200000+1)
ans = 0

for x in candidate_x:
    q = [x]
    size = 0
    cx, cy = 0, 0

    while q:
        a = q.pop()
        if a<=100000:
            cx += 1
        else:
            cy += 1
        used[a] = True
        for b in d[a]:
            if not used[b]:
                size += 1
                q.append(b)
    ans += cx*cy-size

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
d = defaultdict(list)
candidate_x = set()
candidate_y = set()

for _ in range(N):
    x, y = map(int, input().split())
    y += 10**5
    candidate_x.add(x)
    candidate_y.add(y)
    d[x].append(y)
    d[y].append(x)

used = [False]*(200000+1)
ans = 0

for x in candidate_x:
    q = [x]
    size = 0
    cx, cy = 1, 0

    while q:
        a = q.pop()
        used[a] = True
        for b in d[a]:
            if not used[b]:
                size += 1
                if b<=100000:
                    cx += 1
                else:
                    cy += 1
                q.append(b)
    ans += cx*cy-size

for y in candidate_y:
    q = [y]
    size = 0
    cx, cy = 0, 1

    while q:
        a = q.pop()
        used[a] = True
        for b in d[a]:
            if not used[b]:
                size += 1
                if b<=100000:
                    cx += 1
                else:
                    cy += 1
                q.append(b)

    ans += cx*cy-size

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
d = defaultdict(list)
candidate_x = set()

for _ in range(N):
    x, y = map(int, input().split())
    candidate_x.add(x)
    y += 10**5
    d[x].append(y)
    d[y].append(x)

used = [False]*(200000+1)
ans = 0

for x in candidate_x:
    q = [x]
    size = 0
    cx, cy = 1, 0

    while q:
        a = q.pop()
        used[a] = True
        for b in d[a]:
            if not used[b]:
                size += 1
                if b<=100000:
                    cx += 1
                else:
                    cy += 1
                q.append(b)

    ans += cx*cy-size

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque
    import sys
    input = sys.stdin.readline

    M = 10 ** 5

    N = int(input())

    g = tuple(set() for _ in range(M * 2))
    for _ in range(N):
        x, y = (int(x) - 1 for x in input().split())  # 一律に移動
        g[x].add(y + M)
        g[y + M].add(x)

    visited = [0] * (M * 2)
    ans = 0
    for s in range(M * 2):
        if visited[s]: continue
        visited[s] = 1
        dq = deque()
        dq.append(s)

        sz = 0
        x = 0
        while dq:
            v = dq.popleft()
            sz += 1
            if v < M:
                x += 1
            for u in g[v]:
                if visited[u]: continue
                visited[u] = 1
                dq.append(u)
        ans += (sz - x) * x - (sz - 1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n = int(input())
l = []
d1 = defaultdict(set)
d2 = defaultdict(set)
for i in range(n):
    x,y =map(int,input().split())
    d1[x].add(y)
    d2[y].add(x)
    l.append((x,y))
l.sort()
s = set(l)

l2 = sorted(l,key=lambda x:x[1])

for i in range(n-1):
    if l[i][0]==l[i+1][0]:
        
        y1 = l[i][1]
        y2 = l[i+1][1]
        
        for j in d2[y1]:
            d2[y2].add(j)
            s.add((j,y2))
        for j in d2[y2]:
            d2[y1].add(j)
            s.add((j,y1))
for i in range(n-1):
    if l2[i][1]==l2[i+1][1]:
        
        x1 = l[i][0]
        x2 = l[i+1][0]
        
        for j in d1[x1]:
            d1[x2].add(j)
            s.add((x2,j))
        for j in d1[x2]:
            d1[x1].add(j)
            s.add((x1,j))

print(len(s)-n)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n = int(input())
l = []
d1 = defaultdict(set)
d2 = defaultdict(set)
for i in range(n):
    x,y =map(int,input().split())
    d1[x].add(y)
    d2[y].add(x)
    l.append((x,y))
l.sort()
s = set(l)

l2 = sorted(l,key=lambda x:x[1])

for i in range(n-1):
    if l[i][0]==l[i+1][0]:
        
        y1 = l[i][1]
        y2 = l[i+1][1]
        
        for j in d2[y1]:
            
            d2[y2].add(j)
            s.add((j,y2))
        for j in d2[y2]:
           
            d2[y1].add(j)
            s.add((j,y1))

print(len(s)-n)

Submission status: Wrong Answer

Solution code:
def dfs(v):
    cnt_edge = 0
    cnt = [0, 0]
    if v < OFFSET:
        cnt[0] += 1
    else:
        cnt[1] += 1
    visited[v] = True
    stack = [v]
    while stack:
        v = stack.pop()
        for nxt_v in graph[v]:
            if visited[nxt_v]:
                continue
            cnt_edge += 1
            if nxt_v < OFFSET:
                cnt[0] += 1
            else:
                cnt[1] += 1
            visited[nxt_v] = True
            stack.append(nxt_v)
    return cnt[0] * cnt[1] - cnt_edge

n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
OFFSET = 10 ** 5

graph = [[] for i in range(2 * OFFSET)]
for x, y in info:
    x -= 1
    y -= 1
    y += OFFSET
    graph[x].append(y)
    graph[y].append(x)

ans = 0
visited = [False] * (2 * OFFSET)
for v in range(2 * OFFSET):
    if visited[v]:
        continue
    else:
        ans += dfs(v)
print(ans)

Submission status: Wrong Answer

Solution code:
def dfs(v):
    cnt_edge = 0
    cnt = [0, 0]
    if v < 10 ** 5:
        cnt[0] += 1
    visited[v] = True
    stack = [v]
    while stack:
        v = stack.pop()
        for nxt_v in graph[v]:
            if visited[nxt_v]:
                continue
            cnt_edge += 1
            if nxt_v < 10 ** 5:
                cnt[0] += 1
            else:
                cnt[1] += 1
            visited[nxt_v] = True
            stack.append(nxt_v)
    return cnt[0] * cnt[1] - cnt_edge

n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
OFFSET = 10 ** 5

graph = [[] for i in range(2 * OFFSET)]
for x, y in info:
    x -= 1
    y -= 1
    y += OFFSET
    graph[x].append(y)
    graph[y].append(x)

ans = 0
visited = [False] * (2 * 10 ** 5)
for v in range(2 * 10 ** 5):
    if visited[v]:
        continue
    else:
        ans += dfs(v)
print(ans)

Submission status: Wrong Answer

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

from collections import defaultdict, Counter
xtoy = defaultdict(set)
for _x, _y in xy:
    xtoy[_x].add(_y)

y_counter = Counter([_xy[1] for _xy in xy])

ans = 0
for key in xtoy:
    ys = xtoy[key]
    l = len(ys)
    for y in ys:
        ans += (y_counter[y] - 1) * (l - 1)

print(ans)

Submission status: Wrong Answer

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

        # x を共有する index が存在する
        if x in x_to_index:
            j = x_to_index[x]
            y0 = potential[uf.root(j)][1]
            uf.unite(i, j)
            potential[uf.root(i)][1] = y0 + 1

        # y を共有する index が存在する
        if y in y_to_index:
            j = y_to_index[y]
            # x を共有するときに既に追加されている場合、y は増えていないので戻す
            if uf.is_connected(i, j):
                potential[uf.root(i)][1] -= 1
            # そうでない場合、x が追加される
            else:
                x0 = potential[uf.root(i)][0]
                x1 = potential[uf.root(j)][0]
                uf.unite(i, j)
                potential[uf.root(i)][0] = x0 + x1

        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: Wrong Answer

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

        # x を共有する index が存在する
        if x in x_to_index:
            uf.unite(x_to_index[x], i)
            potential[uf.root(i)][1] += 1 # y が追加される

        # y を共有する index が存在する
        if y in y_to_index:
            j = y_to_index[y]
            # x を共有するときに既に追加されている場合、y は増えていないので戻す
            if uf.is_connected(i, j):
                potential[uf.root(i)][1] -= 1
            # そうでない場合、x が追加される
            else:
                x0 = potential[uf.root(i)][0]
                x1 = potential[uf.root(j)][0]
                uf.unite(i, j)
                potential[uf.root(i)][0] = x0 + x1

        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: Wrong Answer

Solution code:
from collections import Counter
import sys

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

n, *xy = map(int, read().split())
X = list(map(int, xy[0::2]))
Y = list(map(int, xy[1::2]))
CX = Counter(X)
CY = Counter(Y)
total = 0
total += n
xcnt = 0
ycnt = 0
LX = set()
LY = set()
for key, value in CX.items():
    xcnt += 1
    if value == 1:
        LX.add(key)
for key, value in CY.items():
    ycnt += 1
    if value == 1:
        LY.add(key)
for i in range(n):
    x = X[i]
    y = Y[i]
    if x in LX and y in LY:
        xcnt -= 1
        ycnt -= 1
        total -= 1
print(xcnt * ycnt - total)

Submission status: Wrong Answer

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])
    cnt = 0
    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)
            cnt += 1
    ans += x * y - cnt

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
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 = [i]
    cnt = 0
    x = 0
    y = 0
    while node:
        s = node.pop()
        if s <= U:
            x += 1
        else:
            y += 1
        for t in edge[s]:
            if seen[t]:
                continue
            seen[t] = True
            node.append(t)
            cnt += 1
    ans += x * y - cnt

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
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 = [i]
    cnt = 0
    x = 0
    y = 0
    while node:
        s = node.pop()
        if s >= U:
            x += 1
        else:
            y += 1
        for t in edge[s]:
            if seen[t]:
                continue
            seen[t] = True
            node.append(t)
            cnt += 1
    ans += x * y - cnt

print(ans)

Submission status: Wrong Answer

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(R)
print(ans-n)

Submission status: Wrong Answer

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

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

setX, setY = set(), set()
xs, ys = dict(), dict()
useds = [0] * N
for i, (x, y) in enumerate(pts):
    if x not in xs:
        xs[x] = [i]
    elif len(xs[x]) == 1:
        xs[x].append(i)
        j = xs[x][0]
        setY.add(y)
        setY.add(pts[j][1])
        useds[i] = 1
        useds[j] = 1
    else:
        setY.add(y)
        useds[i] = 1

    if y not in ys:
        ys[y] = [i]
    elif len(ys[y]) == 1:
        ys[y].append(i)
        j = ys[y][0]
        setX.add(x)
        setX.add(pts[j][0])
        useds[i] = 1
        useds[j] = 1
    else:
        setX.add(x)
        useds[i] = 1

sizeX, sizeY = len(setX), len(setY)
numUsed = useds.count(1)

ans = sizeX*sizeY - numUsed
print(ans)