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):
from collections import defaultdict
n = int(input())
dx = defaultdict(list)
dy = defaultdict(list)
pts = []
for _ in range(n):
    x, y = map(int, input().split())
    dx[x].append(y)
    dy[y].append(x)
    pts.append((x, y))

vx, vy = set(), set()
cnt = 0
for x, y in pts:
    sx, sy = [x], [y]
    xs, ys = set(), set()
    while sx or sy:
        while sx:
            x = sx.pop()
            if x not in xs:
                xs.add(x)
                for y in dx[x]:
                    if y not in ys:
                        sy.append(y)
        while sy:
            y = sy.pop()
            if y not in ys:
                ys.add(y)
                for x in dy[y]:
                    if x not in xs:
                        sx.append(x)
    vx.update(dx)
    vy.update(dy)
    cnt += len(dx) * len(dy)
print(cnt - len(pts))

n = int(input())
dx = defaultdict(list)
dy = defaultdict(list)
pts = set()
for _ in range(n):
    x, y = map(int, input().split())
    dx[x].append(y)
    dy[y].append(x)
    pts.add((x, y))

vx, vy = set(), set()
cnt = 0
for x, y in pts:
    if x in vx or y in vy: continue
    sx, sy = [x], [y]
    xs, ys = set(), set()
    while sx or sy:
        while sx:
            x = sx.pop()
            if x not in xs:
                xs.add(x)
                for y in dx[x]:
                    if y not in ys:
                        sy.append(y)
        while sy:
            y = sy.pop()
            if y not in ys:
                ys.add(y)
                for x in dy[y]:
                    if x not in xs:
                        sx.append(x)
    vx.update(xs)
    vy.update(ys)
    cnt += len(xs) * len(ys)
print(cnt - len(pts))

n = int(input())
dot = {}
dotset = set()
for i in range(n):
    x, y = map(int, input().split())
    dot[i] = (x, y)
    dotset.add((x, y))

v = set()

cnt = 0
for i, f in dot:
    a, b = f
    for j, g in dot:
        if i == j: continue
        c, d = g
        if a == c or b == d: continue
        f1 = (a, d) in dotset
        f2 = (c, b) in dotset
        if f1 and not f2:
            cnt += 1
            dotset.add((c, b))
        if not f1 and f2:
            cnt += 1
            dotset.add((a, d))
print(cnt)

from collections import defaultdict
n = int(input())
dx = defaultdict(list)
dy = defaultdict(list)
pts = set()
for _ in range(n):
    x, y = map(int, input().split())
    dx[x].append(y)
    dy[y].append(x)
    pts.add((x, y))

vx, vy = set(), set()
cnt = 0
for x, y in pts:
    if x in vx or y in vy: continue
    sx, sy = [x], [y]
    xs, ys = set(), set()
    while sx or sy:
        while sx:
            x = sx.pop()
            if x not in xs:
                xs.add(x)
                for y in dx[x]:
                    if y not in ys:
                        sy.append(y)
        while sy:
            y = sy.pop()
            if y not in ys:
                ys.add(y)
                for x in dy[y]:
                    if x not in xs:
                        sx.append(x)
    vx.update(xs)
    vy.update(ys)
    cnt += len(xs) * len(ys)
print(cnt - len(pts))

Verdicts: Wrong Answer

Runtime Error

Runtime Error

Accepted