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:
N = int(input().strip())

X = {}
Y = {}

for _ in range(N):
  x, y = map(int, input().strip().split())
  if x not in X: X[x] = set()
  if y not in Y: Y[y] = set()
  X[x].add(y)
  Y[y].add(x)

count = 0

for x, y_set in X.items():
  for y in y_set:
    tmp = set(y_set)
    x_set = Y[y]
    if len(x_set) < 2: continue

    for _x in x_set:
      if _x == x: continue
      _y_set = X[_x]
      if len(_y_set) < 2: continue
      count += len(_y_set - tmp)
      tmp |= _y_set

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input().strip())

X = {}
Y = {}

for _ in range(N):
  x, y = map(int, input().strip().split())
  if x not in X: X[x] = set()
  if y not in Y: Y[y] = set()
  X[x].add(y)
  Y[y].add(x)

count = 0

for x, y_set in X.items():
  for y in y_set:
    y_set = set(y_set)
    x_set = Y[y]
    if len(x_set) < 2: continue

    for _x in x_set:
      if _x == x: continue
      _y_set = X[_x]
      if len(_y_set) < 2: continue
      count += len(_y_set - y_set)
      y_set |= _y_set

print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x]) # contruction
        return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        self.par[x] = y

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


n = int(input())

uf = UnionFind(n)
xs = []
ys = []
x_dict = {}
y_dict = {}
for i in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)

    if x in x_dict:
        uf.unite(i, x_dict[x])

    if y in y_dict:
        uf.unite(i, y_dict[y])

    x_dict[x] = uf.find(i)
    y_dict[y] = uf.find(i)

print(uf.par)
xi = defaultdict(list)
yi = defaultdict(list)
for i in range(n):
    xi[uf.find(x_dict[xs[i]])].append(xs[i])
    yi[uf.find(y_dict[ys[i]])].append(ys[i])

ans = 0
for k in xi.keys():
    ans += len(set(xi[k])) * len(set(yi[k])) - len(xi[k])

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input().strip())

X = {}
Y = {}

for _ in range(N):
  x, y = map(int, input().strip().split())
  if x not in X: X[x] = set()
  if y not in Y: Y[y] = set()
  X[x].add(y)
  Y[y].add(x)

count = 0

for x, y_set in X.items():
  for y in list(y_set):
    x_set = Y[y]
    if len(x_set) < 2: continue

    for _x in x_set:
      if _x == x: continue
      _y_set = X[_x]
      if len(_y_set) < 2: continue
      count += len(_y_set - y_set)
      y_set |= _y_set

print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x]) # contruction
        return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        self.par[x] = y

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


n = int(input())

uf = UnionFind(n)
xs = []
ys = []
x_dict = {}
y_dict = {}
for i in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)

    if x in x_dict:
        uf.unite(i, x_dict[x])
    elif y in y_dict:
        uf.unite(i, y_dict[y])

    x_dict[x] = uf.find(i)
    y_dict[y] = uf.find(i)

xi = defaultdict(list)
yi = defaultdict(list)
for i in range(n):
    xi[uf.find(x_dict[xs[i]])].append(xs[i])
    yi[uf.find(y_dict[ys[i]])].append(ys[i])

ans = 0
for k in xi.keys():
    ans += len(set(xi[k])) * len(set(yi[k])) - len(xi[k])

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input().strip())

X = {}
Y = {}

for _ in range(N):
  x, y = map(int, input().strip().split())
  if x not in X: X[x] = set()
  if y not in Y: Y[y] = set()
  X[x].add(y)
  Y[y].add(x)

count = 0

for x, y_set in X.items():
  for y in list(y_set):
    for _x in Y[y]:
      if _x == x: continue
      _y_set = X[_x]
      if len(_y_set) < 2: continue
      count += len(_y_set - y_set)
      y_set |= _y_set

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input().strip())

X = {}
Y = {}

for _ in range(N):
  x, y = map(int, input().strip().split())
  if x not in X: X[x] = set()
  if y not in Y: Y[y] = set()
  X[x].add(y)
  Y[y].add(x)

count = 0

for x, y_set in X.items():
  for y in y_set:
    y_set = set(y_set)
    for _x in Y[y]:
      if _x == x: continue
      count += len(X[_x] - y_set)
      y_set |= X[_x]

print(count)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x]) # contruction
        return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        self.par[x] = y

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


n = int(input())

uf = UnionFind(n)
xs = []
ys = []
x_dict = {}
y_dict = {}
for i in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)

    if x in x_dict:
        uf.unite(i, x_dict[x])
    elif y in y_dict:
        uf.unite(i, y_dict[y])

    x_dict[x] = uf.find(i)
    y_dict[y] = uf.find(i)

xi = defaultdict(list)
yi = defaultdict(list)
for i in range(n):
    xi[x_dict[xs[i]]].append(xs[i])
    yi[y_dict[ys[i]]].append(ys[i])

ans = 0
for k in xi.keys():
    ans += len(set(xi[k])) * len(set(yi[k])) - len(xi[k])

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input().strip())

X = {}

for _ in range(N):
  x, y = map(int, input().strip().split())
  if x not in X: X[x] = set()
  X[x].add(y)

count = 0

keys = list(X.keys())
for i in keys:
  for j in keys:
    if i == j: continue
    if len(X[i] & X[j]) == 0: continue
    count += len(X[j] - X[i])
    X[i] |= X[j]

print(count)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return tuple(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, XY):
    g = defaultdict(list)
    for x, y in XY:
        g[(0, x)].append((1, y))
        g[(1, y)].append((0, x))

    ans = 0
    while g:
        for k in g:
            q = [g[k]][0]
            break
        done = set()
        while q:
            v = q.pop()
            for u in g[v]:
                if v[0] == 1:
                    e = (u, v)
                else:
                    e = (v, u)
                if e not in done:
                    q.append(u)
                    done.add(e)
        xn = set()
        yn = set()
        for v, u in done:
            for i, z in (v, u):
                if i == 0:
                    xn.add(z)
                elif i == 1:
                    yn.add(z)
        ans += (len(xn) * len(yn)) - len(done)
        for v, u in done:
            g.pop(v, None)
            g.pop(u, None)

    return ans

def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    print(slv(N, XY))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != gy and gx != 0 and gy != 0:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        if len(xys) < 4:
            ans += len(xys) - 1
            continue
        nx = 0
        for xy in xys:
            if xy > 0:
                nx += 1
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx == 0 or gy == 0:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
        elif gx != gy:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
    ans = -N
    for xys in g2xy.values():
        if len(xys) < 4:
            continue
        nx = 0
        for xy in xys:
            if xy > 0:
                nx += 1
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = [None] * 100001
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx == gy != None:
            continue
        elif gx is not None is not gy:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        nx = sum(xy > 0 for xy in xys)
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y += 10 ** 5
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != 0 and gy != 0:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        m, p = 0, 0
        for xy in xys:
            if xy >= 10 ** 5:
                m += 1
            else:
                p += 1
        ans += m * p
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y += 10 ** 5
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != 0 and gy != 0:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        m, p = 0, 0
        for xy in xys:
            if xy < 0:
                m += 1
            else:
                p += 1
        ans += m * p
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        gx = xy2g[x]
        gy = xy2g[-y]
        if gx != 0 and gy != 0:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gx] |= {x, -y}
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[-y] = g
            g2xy[g] |= {x, -y}
    ans = -N
    for xys in g2xy.values():
        m, p = 0, 0
        for xy in xys:
            if xy < 0:
                m += 1
            else:
                p += 1
        ans += m * p
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        gx = xy2g[x]
        gy = xy2g[-y]
        if gx != 0 and gy != 0:  # merge
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[-y] = g
            g2xy[g] |= {x, -y}
    ans = -N
    for xys in g2xy.values():
        m, p = 0, 0
        for xy in xys:
            if xy < 0:
                m += 1
            else:
                p += 1
        ans += m * p
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        gx = xy2g[x]
        gy = xy2g[-y]
        if gx != 0 and gy != 0:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[-y] = g
            g2xy[g] |= {x, -y}
    ans = -N
    for xys in g2xy.values():
        m, p = 0, 0
        for xy in xys:
            if xy < 0:
                m += 1
            else:
                p += 1
        ans += m * p
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    x2g = defaultdict(int)
    y2g = defaultdict(int)
    g2y = defaultdict(set)
    g2x = defaultdict(set)
    for x, y in xy:
        gx = x2g[x]
        gy = y2g[y]
        if gx > 0 and gy > 0:  # merge
            if len(g2x[gx]) + len(g2y[gx]) < len(g2x[gy]) + len(g2y[gy]):
                gx, gy = gy, gx
            for x0 in g2x[gy]:
                x2g[x0] = gx
            for y0 in g2y[gy]:
                y2g[y0] = gx
            g2y[gx] |= g2y[gy]
            g2x[gx] |= g2x[gy]
            g2y[gy].clear()
            g2x[gy].clear()
        else:
            g = gx or gy or x
            x2g[x] = g
            y2g[y] = g
            g2x[g].add(x)
            g2y[g].add(y)
    ans = -N
    for g in g2x.keys():
        ans += len(g2x[g]) * len(g2y[g])
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    x2g = defaultdict(int)
    y2g = defaultdict(int)
    g2y = defaultdict(set)
    g2x = defaultdict(set)
    for x, y in xy:
        gx = x2g[x]
        gy = y2g[y]
        if gx > 0 and gy > 0:  # merge
            if len(g2x[gx]) + len(g2y[gx]) < len(g2x[gy]) + len(g2y[gy]):
                gx, gy = gy, gx
            for x0 in g2x[gy]:
                x2g[x0] = gx
            for y0 in g2y[gy]:
                y2g[y0] = gx
            g2y[gx] |= g2y[gy]
            g2x[gx] |= g2x[gy]
            g2y[gy].clear()
            g2x[gy].clear()
        else:
            gx = gx or gy or x
        x2g[x] = gx
        y2g[y] = gx
        g2x[gx].add(x)
        g2y[gx].add(y)
    ans = -N
    for g in g2x.keys():
        if g2x[g]:
            ans += len(g2x[g]) * len(g2y[g])
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    x2g = defaultdict(int)
    y2g = defaultdict(int)
    g2y = defaultdict(set)
    g2x = defaultdict(set)
    for x, y in xy:
        gx = x2g[x]
        gy = y2g[y]
        if gx > 0 and gy > 0:  # merge
            if len(g2x[gx]) + len(g2y[gx]) < len(g2x[gy]) + len(g2y[gy]):
                gx, gy = gy, gx
            for x0 in g2x[gy]:
                x2g[x0] = gx
            for y0 in g2y[gy]:
                y2g[y0] = gx
            g2y[gx] |= g2y[gy]
            g2x[gx] |= g2x[gy]
            g2y[gy] = set()
            g2x[gy] = set()
        else:
            gx = gx or gy or x
        x2g[x] = gx
        y2g[y] = gx
        g2x[gx].add(x)
        g2y[gx].add(y)
    ans = -N
    for g in g2x.keys():
        if g2x[g]:
            ans += len(g2x[g]) * len(g2y[g])
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))#親ノード
        self.size = [1]*n #グループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        while self.parent[x] != x:
            x, self.parent[x] = self.parent[x], self.parent[self.parent[x]]
        return x 
 
    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]: 
            self.size[y] += self.size[x] #yの要素数を更新
            self.parent[x] = y #xをyにつなぐ
        else:
            self.size[x] += self.size[y] #xの要素数を更新
            self.parent[y] = x #yをxにつなぐ
        return True
 
    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return self.size[self.root(x)]

n = int(input())
xy = [[int(i) for i in input().split()] for j in range(n)] 

UF = UnionFind(n)

xval = dict()
yval = dict()
for i,(x,y) in enumerate(xy):
    if y in yval:
        UF.merge(i,yval[y])
    else:
        yval[y] = i

    if x in xval:
        UF.merge(i,xval[x])
    else:
        xval[x] = i


xcon = dict()
ycon = dict()
for i,pi in enumerate(UF.parent):
    x,y = xy[i]
    if pi in xcon:
        xcon[pi].add(x)
    else:
        xcon[pi] = {x}

    if pi in ycon:
        ycon[pi].add(y)
    else:
        ycon[pi] = {y}
        

ans = -n
#print(xcon,ycon)
for key, val in xcon.items():
    ans += len(val) * len(ycon[key])


#print(xval,yval)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    x2g = defaultdict(int)
    y2g = defaultdict(int)
    g2y = defaultdict(set)
    g2x = defaultdict(set)
    for x, y in xy:
        gx = x2g[x]
        gy = y2g[y]
        if gx > 0 and gy > 0:  # merge
            if len(g2x[gx]) + len(g2y[gx]) < len(g2x[gy]) + len(g2y[gy]):
                gx, gy = gy, gx
            for x in g2x[gy]:
                x2g[x] = gx
            for y in g2y[gy]:
                y2g[y] = gx
            g2y[gx] |= g2y[gy]
            g2x[gx] |= g2x[gy]
            g2y[gy] = set()
            g2x[gy] = set()
        else:
            gx = gx or gy or x
        x2g[x] = gx
        y2g[y] = gx
        g2x[gx].add(x)
        g2y[gx].add(y)
    ans = -N
    for g in g2x.keys():
        if g2x[g]:
            ans += len(g2x[g]) * len(g2y[g])
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    x2g = defaultdict(int)
    y2g = defaultdict(int)
    g2y = defaultdict(set)
    g2x = defaultdict(set)
    for x, y in xy:
        gx = x2g[x]
        gy = y2g[y]
        if gx > 0 and gy > 0:  # merge
            if len(g2x[gx]) + len(g2y[gx]) < len(g2x[gy]) + len(g2y[gy]):
                gx, gy = gy, gx
            for x in g2x[gy]:
                x2g[x] = gx
            for y in g2y[gy]:
                y2g[y] = gx
            g2y[gx] |= g2y[gy]
            g2x[gx] |= g2x[gy]
            g2y[gy] = set()
            g2x[gy] = set()
        else:
            gx = gx or gy or x
            x2g[x] = gx
            y2g[y] = gx
        g2x[gx].add(x)
        g2y[gx].add(y)
    ans = -N
    for g in g2x.keys():
        if g2x[g]:
            ans += len(g2x[g]) * len(g2y[g])
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))#親ノード
        self.size = [1]*n #グループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        while self.parent[x] != x:
            x, self.parent[x] = self.parent[x], self.parent[self.parent[x]]
        return x 
 
    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]: 
            self.size[y] += self.size[x] #yの要素数を更新
            self.parent[x] = y #xをyにつなぐ
        else:
            self.size[x] += self.size[y] #xの要素数を更新
            self.parent[y] = x #yをxにつなぐ
        return True
 
    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return self.size[self.root(x)]

n = int(input())
xy = [[int(i) for i in input().split()] for j in range(n)] 

UF = UnionFind(n)

xval = dict()
yval = dict()
for i,(x,y) in enumerate(xy):
    if y in yval:
        UF.merge(i,yval[y])
    else:
        yval[y] = i

    if x in xval:
        UF.merge(i,xval[x])
    else:
        xval[x] = i

xcon = dict()
ycon = dict()
for i,pi in enumerate(UF.parent):
    x,y = xy[i]
    if pi in xcon:
        xcon[pi].add(x)
    else:
        xcon[pi] = {x}

    if pi in ycon:
        ycon[pi].add(y)
    else:
        ycon[pi] = {y}
        

ans = -n
#print(xcon,ycon)
for key, val in xcon.items():
    ans += len(val)*(len(ycon[key]))


#print(xval,yval)

print(ans)