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:
def main():
    N = int(input())
    X, Y = {}, {}
    for _ in range(N):
        x, y = map(int, input().split())
        if x not in X:
            X[x] = set()
        X[x].add(y)
        if y not in Y:
            Y[y] = set()
        Y[y].add(x)
    processed = set()
    r = 0
    while X:
        x, ys = X.popitem()
        tx = set([x])
        ty = set()
        mx, my = set(), set(ys)
        while mx or my:
            while my:
                y = my.pop()
                mx |= Y.pop(y, set())
            tx |= mx
            while mx:
                x = mx.pop()
                my |= X.pop(x, set())
            ty |= my
        r += len(tx) * len(ty)
    return r - N

print(main())

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    X, Y = {}, {}
    for _ in range(N):
        x, y = map(int, input().split())
        if x not in X:
            X[x] = set()
        X[x].add(y)
        if y not in Y:
            Y[y] = set()
        Y[y].add(x)
    processed = set()
    r = 0
    for x, ys in X.items():
        if x in processed:
            continue
        tx = set([x])
        ty = set(ys)
        for y in ys:
            xs = Y[y]
            for xx in xs:
                processed.add(xx)
                tx.add(xx)
                ty |= X[xx]
        r += len(tx) * len(ty)
    return r - N

print(main())

Submission status: Wrong Answer

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

N = int(input())
x_set = [set() for _ in range(10**5+1)]
y_list = [[] for _ in range(10**5+1)]
for _ in range(N):
    x, y = map(int, input().split())
    x_set[y].add(x)
    y_list[x].append(y)
ans = 0
for x in range(10**5+1):
    xs = set()
    cnt = 0
    for y in y_list[x]:
        xs |= x_set[y]
        cnt += len(x_set[y])
    for y in y_list[x]:
        x_set[y] |= xs
    ans += len(xs) * len(y_list[x]) - cnt
print(ans)

Submission status: Wrong Answer

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

N = int(input())
x_set = [set() for _ in range(10**5+1)]
y_list = [[] for _ in range(10**5+1)]
y_cnt = [0] * (10**5+1)
for _ in range(N):
    x, y = map(int, input().split())
    x_set[y].add(x)
    y_list[x].append(y)
    y_cnt[y] += 1
ans = 0
for x in range(10**5+1):
    xs = set()
    cnt = 0
    for y in y_list[x]:
        xs |= x_set[y]
        cnt += y_cnt[y]
    for y in y_list[x]:
        y_cnt[y] = len(xs)
    ans += len(xs) * len(y_list[x]) - cnt
print(ans)

Submission status: Wrong Answer

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

N = int(input())
x_set = [set() for _ in range(10**5+1)]
y_list = [[] for _ in range(10**5+1)]
y_cnt = [0] * (10**5+1)
for _ in range(N):
    x, y = map(int, input().split())
    x_set[y].add(x)
    y_list[x].append(y)
    y_cnt[y] += 1
ans = 0
for x in range(10**5+1):
    xs = set()
    cnt = 0
    for y in y_list[x]:
        xs |= x_set[y]
        cnt += y_cnt[y]
    ans += len(xs) * len(y_list[x]) - cnt
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
n = int(input())
xy = [list(map(int,input().split())) for i in range(n)]
graph = [[] for i in range(2*10**5+1)]
ans = 0
for x,y in xy:
  y += 10**5
  graph[x].append(y)
  graph[y].append(x)
  ans -= 1
vis = [0 for i in range(2*10**5+1)]
for i in range(1,2*10**5+1):
  if vis[i]:
    continue
  stack = [i]
  nx = 0
  ny = 0
  while stack:
    x = stack.pop()
    if x > 10**5:
      ny += 1
    else:
      nx += 1
    vis[x] = 1
    for y in graph[x]:
      if not vis[y]:
        stack.append(y)
  ans += nx*ny
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

xx = [[] for _ in range(10 ** 5)]
yy = [[] for _ in range(10 ** 5)]

for j in range(n):
    x, y = [int(i) - 1 for i in input().split()]
    xx[x].append(j)
    yy[y].append(j)


class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n
        self.rank = [1] * n
        self.count = [1] * n

    def get_root(self, i):
        while self.parent[i] != -1:
            i = self.parent[i]
        return i

    def is_same_tree(self, i, j):
        return self.get_root(i) == self.get_root(j)

    def merge(self, i, j):
        i = self.get_root(i)
        j = self.get_root(j)
        if i == j:
            return

        if self.rank[i] > self.rank[j]:
            self.parent[j] = i
            self.rank[i] = max(self.rank[i], self.rank[j] + 1)
            self.count[i] += self.count[j]
        else:
            self.parent[i] = j
            self.rank[j] = max(self.rank[j], self.rank[i] + 1)
            self.count[j] += self.count[i]

uf = UnionFind(n)

for i in xx + yy:
    if not i:
        continue
    for j in i:
        uf.merge(i[0], j)
ans = 0
for i, j in zip(uf.parent, uf.count):
    if i == -1:
        ans += j * (j - 1) // 2

for i in xx + yy:
    j = len(i)
    ans -= j * (j - 1) // 2
print(ans)

Submission status: Wrong Answer

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

x_pnt = {}
y_pnt = {}
for xi, yi in xy:
    x_pnt.setdefault(str(xi), [])
    y_pnt.setdefault(str(yi), [])
    x_pnt[str(xi)].append(yi)
    y_pnt[str(yi)].append(xi)

x_line = set([])
for key, val in y_pnt.items():
    if len(val) >= 2:
        for x in val: x_line.add(x)

y_line = set([])
for key, val in x_pnt.items():
    if len(val) >= 2:
        for y in val: y_line.add(y)


ans = len(x_line) * len(y_line)
for x in x_line:
    ans -= len(x_pnt[str(x)])

# print("#", x_pnt, x_line)
# print("#", y_pnt, y_line)
print(ans)

Submission status: Wrong Answer

Solution code:
# 長方形の4点のうち3点が必要なので自明からほど遠い
# x,yを2部グラフ、格子を辺とみなす
# 連結成分ごとに張られる......
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

mx =0
my = 0
for i in range(n):
    mx = max(mx,xy[i][0])
    my = max(my,xy[i][1])

*p, = range(mx+my+1)
rank = [1]*(mx+my+1)

for i in range(n):
    xy[i][1] += mx

def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    rx = rank[px]; ry = rank[py]
    if ry < rx:
        p[py] = px
    elif rx < ry:
        p[px] = py
    else:
        p[py] = px
        rank[px] += 1
    return 1

for x,y in xy:
    unite (x,y)

xp = [0]*(mx+my+1)
yp = [0]*(mx+my+1)

for i in range(mx+my+1):
    if i<=mx:
        xp[p[i]]+=1
    else:
        yp[p[i]]+=1
ans = 0
for i in range(mx+my+1):
    ans += xp[i]*yp[i]
ans -= n

print(ans)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, n, t, s):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n + 1)
        self.sizex = [1] * t + [0] * s
        self.sizey = [0] * t + [1] * s

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def sizeof(self, x):
        return self.sizex[self.find(x)] * self.sizey[self.find(x)]

    # 併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.sizex[y] += self.sizex[x]
            self.sizey[y] += self.sizey[x]
        else:
            self.par[y] = x
            self.sizex[x] += self.sizex[y]
            self.sizey[x] += self.sizey[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


def coordinate_compression(arr):
    return {v: k for k, v in enumerate(sorted(set(arr)))}


n = int(input())
x = [0] * n
y = [0] * n
for i in range(n):
    x[i], y[i] = map(int, input().split())
dx = coordinate_compression(x)
dy = coordinate_compression(y)
uf = UnionFind(len(dx) + len(dy), len(dx), len(dy))
for i in range(n):
    uf.unite(dx[x[i]], dy[y[i]] + len(dx))
s = set()
ans = 0
for i in range(len(dx)):
    p = uf.find(i)
    if p in s:
        continue
    ans += uf.sizeof(i)
    s.add(p)
print(ans - n)

Submission status: Wrong Answer

Solution code:
#最大も何も一意では
n = int(input())
p = [tuple(map(int, input().split( ))) for _ in range(n)]
x = set([p[i][0] for i in range(n)])
y = set([p[i][1] for i in range(n)])

print(len(x)*len(y)-n)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
y = set()
x = set()
if N < 3:
  print(0)
  exit(0)
for _ in range(N):
  u, v = map(int, input().split())
  y.add(u)
  x.add(v)
print(len(y) * len(x) - N)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    # 初期化
    def __init__(self, n):
        # 根なら-size, 子なら親の頂点
        self.par = [-1] * n
        # 木の高さ
        self.rank = [0] * n

    # 検索
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        # 異なる集合に属する場合のみ併合
        if x != y:
            # 高い方をxとする。
            if self.rank[x] < self.rank[y]:
                x,y = y,x
            # 同じ高さの時は高さ+1
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # yの親をxとし、xのサイズにyのサイズを加える
            self.par[x] += self.par[y]
            self.par[y] = x

    # 同集合判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.par[self.find(x)]


import operator

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

for i in range(n):
    z[i].append(i)

u = UnionFind(n)
z.sort()
for i in range(1,n):
    if z[i][0]==z[i-1][0]:
        u.unite(z[i][2],z[i-1][2])

z.sort(key=operator.itemgetter(1))
for i in range(1,n):
    if z[i][1]==z[i-1][1]:
        u.unite(z[i][2],z[i-1][2])

l = [[]for i in range(10**5)]

for i in range(n):
    l[u.find(i)].append(z[i])

ans = 0
for i in range(n):
    if l[i]!=[]:
        x = set()
        y = set()
        for a in l[i]:
            if a[0] not in x:
                x.add(a[0])
            if a[1] not in y:
                y.add(a[1])
        ans += len(x)*len(y)-len(l[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,os,math
from collections import Counter, defaultdict, deque, OrderedDict
import bisect
from sys import stdin, stdout
from itertools import repeat
import Queue


# sys.stdin = open('input')
# n, k = map(int, raw_input().split())
# da = map(int, raw_input().split())
# db = map(int, raw_input().split())


def main():
    n = map(int, raw_input().split())[0]
    G = defaultdict(list)
    bfs = []
    for i in range(n):
        a, b = map(int, raw_input().split())
        b += 100000
        G[a].append(b)
        G[b].append(a)
        bfs.append(a)

    vs = set()
    ans = 0
    for i in bfs:
        if i in vs:
            continue
        x, y = 0, 0
        vs.add(i)
        q = deque()
        q.append(i)
        while q:
            now = q.popleft()
            if now > 100000:
                y += 1
            else:
                x += 1
            for adj in G[now]:
                if adj not in vs:
                    # print adj
                    vs.add(adj)
                    q.append(adj)
        # print x, y
        ans += x*y - (x+y-1)
    print ans




main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    for i in range(3):
        if s[i] == s[i + 1]:
            print("Bad")
            return
    print("Good")
    return

#B
def B():
    n, l = LI()
    lis = [l + i for i in range(n)]
    s = sum(lis)
    a = inf
    for i in lis:
        if abs(a) > abs(i):
            a = i
    print(s-a)
    return

#C
def C():
    def gcd(a, b):
        a, b = max(a, b), min(a, b)
        while b:
            a, b = b, a % b
        return a
    def lcm(a, b):
        return a * b // gcd(a, b)
    a, b, c, d = LI()
    x = b // c - (a-1) // c
    y = b // d - (a-1) // d
    z = b // lcm(c , d) - (a-1) // lcm(c , d)
    print(b-a+1-(x+y-z))
    return

#D
def D():
    n = II()
    ab = LIR(n)
    ab.sort(key=lambda x: x[1])
    now = 0
    for a, b in ab:
        now += a
        if now <= b:
            continue
        print("No")
        return
    print("Yes")
    return

#E
def E():
    n, k = LI()
    if k > (n - 1) * (n - 2) / 2:
        print(-1)
        return
    d = (n - 1) * (n - 2) // 2 - k
    a = [[] for i in range(n)]
    for i in range(n):
        if i != 1:
            a[i].append(1)
            a[1].append(i)
    l = 0
    m = 2
    while d > 0:
        a[l].append(m)
        m += 1
        d -= 1
        if m == n:
            l += 1
            m = l + 1
            if l == 1:
                l = 2
                m = 3
    aa = 0
    ans = []
    for num,i in enumerate(a):
        for l in i:
            if num < l:
                aa += 1
                ans.append((num+1,l+1))
    print(aa)
    for x, y in ans:
        print(x, y)
    return

#F
def F():
    n = II()
    xy = LIR(n)
    d = defaultdict(list)
    par = defaultdict(int)
    for _, y in xy:
        par[y] = y
    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]
    
    def unite(x, y):
        x = root(x)
        y = root(y)
        if x == y:
            return False
        if x > y: x, y = y, x
        par[y] = x
        return True
    
    setx = set()
    for x, y in xy:
        d[x].append(y)
    for key, value in d.items():
        p = value[0]
        for v in value[1:]:
            unite(p, v)
    ans1 = defaultdict(int)
    ans2 = defaultdict(int)
    ans3 = defaultdict(int)
    ans = 0
    for x, y in xy:
        root(y)
    for x, y in xy:
        if par[y] != y:
            ans3[y] += 1
            ans3[par[y]] += 1
    for _, value in d.items():
        if ans3[value[0]]:
            ans1[value[0]] += 1
        else:
            ans += len(value)
    for _, value in par.items():
        if ans3[value]:
            ans2[value] += 1
        else:
            continue
    for key,value in ans1.items():
        ans += ans2[key] * value
    print(ans-n)
    return

#Solve
if __name__ == '__main__':
    F()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    for i in range(3):
        if s[i] == s[i + 1]:
            print("Bad")
            return
    print("Good")
    return

#B
def B():
    n, l = LI()
    lis = [l + i for i in range(n)]
    s = sum(lis)
    a = inf
    for i in lis:
        if abs(a) > abs(i):
            a = i
    print(s-a)
    return

#C
def C():
    def gcd(a, b):
        a, b = max(a, b), min(a, b)
        while b:
            a, b = b, a % b
        return a
    def lcm(a, b):
        return a * b // gcd(a, b)
    a, b, c, d = LI()
    x = b // c - (a-1) // c
    y = b // d - (a-1) // d
    z = b // lcm(c , d) - (a-1) // lcm(c , d)
    print(b-a+1-(x+y-z))
    return

#D
def D():
    n = II()
    ab = LIR(n)
    ab.sort(key=lambda x: x[1])
    now = 0
    for a, b in ab:
        now += a
        if now <= b:
            continue
        print("No")
        return
    print("Yes")
    return

#E
def E():
    n, k = LI()
    if k > (n - 1) * (n - 2) / 2:
        print(-1)
        return
    d = (n - 1) * (n - 2) // 2 - k
    a = [[] for i in range(n)]
    for i in range(n):
        if i != 1:
            a[i].append(1)
            a[1].append(i)
    l = 0
    m = 2
    while d > 0:
        a[l].append(m)
        m += 1
        d -= 1
        if m == n:
            l += 1
            m = l + 1
            if l == 1:
                l = 2
                m = 3
    aa = 0
    ans = []
    for num,i in enumerate(a):
        for l in i:
            if num < l:
                aa += 1
                ans.append((num+1,l+1))
    print(aa)
    for x, y in ans:
        print(x, y)
    return

#F
def F():
    n = II()
    xy = LIR(n)
    d = defaultdict(list)
    par = defaultdict(int)
    for _, y in xy:
        par[y] = y
    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]
    
    def unite(x, y):
        x = root(x)
        y = root(y)
        if x == y:
            return False
        if x > y: x, y = y, x
        par[y] = x
        return True
    
    setx = set()
    for x, y in xy:
        d[x].append(y)
    for key, value in d.items():
        p = value[0]
        for v in value[1:]:
            unite(p, v)
    ans1 = defaultdict(int)
    ans2 = defaultdict(int)
    for x, y in xy:
        root(y)
    for _, value in d.items():
        ans1[value[0]] += 1
    for _, value in par.items():
        ans2[value] += 1
    ans = 0
    for key,value in ans1.items():
        ans += ans2[key] * value
    print(ans-n)
    return

#Solve
if __name__ == '__main__':
    F()

Submission status: Wrong Answer

Solution code:
class UF():
  def __init__(self, N):
    self._parent=[n for n in range(0, N)]
    self._size=[1] * N

  def find_root(self, x):
    if self._parent[x]==x:return x
    self._parent[x]=self.find_root(self._parent[x])
    return self._parent[x]

  def unite(self, x, y):
    gx=self.find_root(x)
    gy=self.find_root(y)
    if gx==gy:return

    if self._size[gx]<self._size[gy]:
      self._parent[gx]=gy
      self._size[gy]+=self._size[gx]
    else:
      self._parent[gy]=gx
      self._size[gx]+=self._size[gy]

  def size(self, x):
    return self._size[self.find_root(x)]

  def samegroup(self, x, y):
    return self.find_root(x)==self.find_root(y)

  def groupnum(self):
    N=len(self._parent)
    ans=0
    for i in range(N):
      if self.find_root(i)==i:
        ans+=1
    return ans

import sys
input=sys.stdin.readline
n=int(input())
UF=UF(2*10**5)
for i in range(n):
  x,y=map(int,input().split())
  UF.unite(x-1+10**5,y-1)

ct=[[0,0] for i in range(2*10**5)]
for i in range(2*10**5):
  if i<10**5:
    ct[UF._parent[i]][0]+=1
  else:
    ct[UF._parent[i]][1]+=1
ans=0
for i in range(2*10**5):
  ans+=ct[i][0]*ct[i][1]
print(ans-n)

Submission status: Wrong Answer

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


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1] * (n + 1)
        self.rnk = [0] * (n + 1)

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

    def unite(self, x, y):
        x = self.find_root(x)
        y = self.find_root(y)
        if x == y:
            return
        elif self.rnk[x] > self.rnk[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def size(self, x):
        return -self.root[self.find_root(x)]


def main():
    N = int(input())
    xy_list = []
    x_list = []
    y_list = []
    for i in range(N):
        x, y = map(int, input().split())
        xy_list.append((x, y))
        x_list.append(x)
        y_list.append(y)

    x_list = list(set(x_list))
    y_list = list(set(y_list))
    x_list.sort()
    y_list.sort()
    dictX = {}
    dictY = {}
    for i, x in enumerate(x_list):
        dictX[x] = i
    for i, y in enumerate(y_list):
        dictY[y] = i

    xy_c = [[] for _ in range(len(x_list))]
    for x, y in xy_list:
        xc, yc = dictX[x], dictY[y]
        xy_c[xc].append(yc)

    UF = UnionFind(len(y_list) + 1)
    for i in range(len(x_list)):
        j_list = xy_c[i]
        if len(j_list) > 1:
            j0 = j_list[0]
            for j in range(1, len(j_list)):
                UF.unite(j0, j)

    ans = 0
    for i in range(len(x_list)):
        j0 = xy_c[i][0]
        ans += UF.size(j0) - len(xy_c[i])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, = [int(x) for x in input().split(" ")]
dx = [set() for x in range(10**5+1)]
dy = [set() for x in range(10**5+1)]

class UnionFindNode:
    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1
        self.member_num_ = 1
        self.x_num = 0

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
                root.member_num_ = root.member_num_ + unite_root.member_num_
                root.x_num = max(root.x_num, unite_root.x_num)
            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                unite_root.member_num_ = root.member_num_ + unite_root.member_num_
                unite_root.x_num = max(root.x_num, unite_root.x_num)

for i in range(n):
    x, y = [int(x) for x in input().split(" ")]
    dx[x].add(y)
    dy[y].add(x)

node_list = [UnionFindNode(i) for i in range(len(dy))]

for xi, dxx in enumerate(dx):
    b = None
    for y in dxx:
        if b == None:
            b = y
            continue
        node_list[y].unite(node_list[b])
    if len(dxx) != 0:
        node_list[y].root().x_num += 1

r = 0
for node in node_list:
    d = node.x_num * node.member_num_
    r += d
print(r-n)

Submission status: Wrong Answer

Solution code:
n, = [int(x) for x in input().split(" ")]
dx = [set() for x in range(10**5+1)]
dy = [set() for x in range(10**5+1)]

class UnionFindNode:
    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.rank_ = 1
        self.member_num_ = 1
        self.x_num = 0

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
                root.member_num_ = root.member_num_ + unite_root.member_num_
                root.x_num = max(root.x_num, unite_root.x_num)
            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                unite_root.member_num_ = root.member_num_ + unite_root.member_num_
                unite_root.x_num = max(root.x_num, unite_root.x_num)

for i in range(n):
    x, y = [int(x) for x in input().split(" ")]
    dx[x].add(y)
    dy[y].add(x)

node_list = [UnionFindNode(i) for i in range(len(dy))]

for xi, dxx in enumerate(dx):
    b = None
    for y in dxx:
        if b == None:
            node_list[y].root().x_num += 1
            b = y
            continue
        node_list[y].unite(node_list[b])

r = 0
for node in node_list:
    d = node.x_num * node.member_num_
    r += d
print(r-n)

Submission status: Wrong Answer

Solution code:
n = int(input())
p = [list(map(int, input().split())) for _ in range(n)]
adj = [[] for _ in range(200000)]
for x, y in p:
	adj[x-1].append(y+99999)
	adj[y+99999].append(x-1)

visited = [False for _ in range(200000)]

def dfs(orig):
	stack = [orig]
	edges = len(adj[orig])
	if orig < 100000:
		x_num, y_num = 1, 0
	else:
		x_num, y_num = 0, 1

	while stack:
		v = stack.pop()
		for w in adj[v]:
			if visited[w] == False:
				visited[w] = True
				if w < 100000:
					x_num += 1
				else:
					y_num += 1
				edges += len(adj[w])
				stack.append(w)
	return x_num * y_num - (edges // 2)

ans = 0
for i in range(2*n):
	if visited[i] == False and adj[i]:
		visited[i] = True
		ans += dfs(i)
print(ans)

Submission status: Wrong Answer

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

X = {}
count_x = {}
Y = {}
count_y = {}
answer = 0
for i in range(N):
    if not P[i][0] in X:
        X[P[i][0]] = 1
        count_x[P[i][0]] = 1
    else:
        count_x[P[i][0]] += 1
    if not P[i][1] in Y:
        Y[P[i][1]] = 1
        count_y[P[i][1]] = 1
    else:
        count_y[P[i][1]] += 1
for i in range(N):
    answer += (count_x[P[i][0]] - 1) * (count_y[P[i][1]] - 1)
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

N = int(input())

lis = [0] * N

for n in range(N):
    lis[n] = list(map(int, input().split()))
grid = np.array(lis)

if N <= 2:
    print(0)
    sys.exit()

grid_y = grid.T[1]

count = 0
ans = 0

for i in range(1, 100001):
    if len(grid[np.where(grid.T[0] == i)]) >= 2:
        first = len(grid[np.where(grid.T[0] == i)]) - 1
        for item in grid[np.where(grid.T[0] == i)].T[1]:
            count += len(grid[np.where(item == grid_y)]) - 1
        ans += count * first

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from math import *
from heapq import *

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0 for i in range(n)]
        self.size = [1 for i in range(n)]

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

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

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

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

N = int(input())
m = 10**5
uf = UnionFind(2*m+1)
for i in range(N):
    x, y = map(int, input().split())
    uf.unite(x, y+m)
rx, ry = [0] * (2*m+1), [0] * (2*m+1)
for x in range(m+1):
    rx[uf.find(x)] += 1
for y in range(m, 2*m+1):
    ry[uf.find(y)] += 1
t = 0
for i in range(2*m+1):
    t += rx[i] * ry[i]
print(t-N-1)