Problem: 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.

Submission attempts (in order):
import sys

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

n, *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:
            
            #     continue
            
            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
ok_flag = 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)


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:
            
            #     continue
            
            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)


Verdicts: Wrong Answer

Accepted