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:
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 i in range(m+1):
    rx[uf.find(i)] += 1
    ry[uf.find(i+m)] += 1
t = 0
for i in range(2*m+1):
    t += rx[i] * ry[i]
print(t-N-1)

Submission status: Wrong Answer

Solution code:
import sys
# input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

xedges = [[] for _ in range(100001)]
yedges = [[] for _ in range(100001)]
xvisited = [False for _ in range(100001)]
yvisited = [False for _ in range(100001)]

def dfs(i, xy):
  if xy == 0:
    xvisited[i] = True
  else:
    yvisited[i] = True
  xc, yc, ec = (xy+1)%2, xy%2, 0
  if xy == 0:
    ec += len(xedges[i])
    for toy in xedges[i]:
      if not yvisited[toy]:
        _xc, _yc, _ec = dfs(toy, 1)
        xc += _xc
        yc += _yc
        ec += _ec
  else :
    ec += len(yedges[i])
    for tox in yedges[i]:
      if not xvisited[tox]:
        _xc, _yc, _ec = dfs(tox, 0)
        xc += _xc
        yc += _yc
        ec += _ec
  return xc, yc, ec

def main():
  n = int(input())
  for _ in range(n):
    x, y = map(int, input().split())
    xedges[x].append(y)
    yedges[y].append(x)


  ans = 0
  for i in range(1, 100001):
    if not xvisited[i] and len(xedges[i]) != 0:
      xc, yc, ec = dfs(i, 0)
      ans = xc*yc-ec//2
    elif not yvisited[i] and len(yedges[i]) != 0:
      xc, yc, ec = dfs(i, 1)
      ans = xc*yc-ec//2

  print(ans)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**5)
v = 100005
visited = [False]*(2*v)
count = [0, 0]

def dfs(a):
    visited[a] = True
    count[a//v] += 1
    for i in vertex[a]:
        if not visited[i]:
            dfs(i)

input = sys.stdin.readline
N = int(input())
vertex = [[] for _ in range(v*2)]
for _ in range(N):
    x, y=map(int, input().split())
    y += v
    vertex[x].append(y)
    vertex[y].append(x)

ans = 0
for i in range(v):
    if not visited[i]:
        count = [0, 0]
        dfs(i)
        ans += count[0]*count[1]

print(ans-N)


print(vertex[1])

Submission status: Wrong Answer

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

xdict=dict()
ydict=dict()

for i in range(N):
  xdict[xy[i][0]]=[]
  ydict[xy[i][1]]=[]
for i in range(N):
  xdict[xy[i][0]].append(xy[i][1])
  ydict[xy[i][1]].append(xy[i][0])

activex=dict()
activex_next=dict()
for i in range(N):
  activex[xy[i][0]]=1

activey=dict()
activey_next=dict()
for i in range(N):
  activey[xy[i][1]]=0

  
judge=1  
num=0
times=0
while judge==1:
  judge=0
  for i in range(N):
    activex_next[xy[i][0]]=0
    activey_next[xy[i][1]]=0
  for x, ylist in xdict.items():
    if times==0 or activex[x]==1: #1
      if len(ylist)>=2: #[1,2,3,4,5]
        for y in ylist: #2
          if times==0 or activey[y]==1: #1
            xlist=ydict[y] #[1]
            for targetx in xlist: #1
              for targety in ylist: #[1,2,3,4,5]
                if not targety in xdict[targetx]:
                  xdict[targetx].append(targety)
                  ydict[targety].append(targetx)
                  judge=1
                  num+=1
                  activex_next[targetx]=1
                  activey_next[targety]=1
    times+=1
                  
    activex=activex_next.copy() 
    activey=activey_next.copy() 
print(num)

Submission status: Wrong Answer

Solution code:
num_lines = int(input())
if num_lines<1 or num_lines>10**5:
	print ('Illegal')
	exit()
a=[]
for i in range(num_lines):
	x,y=map(int,input().split(" "))
	if x<1  or y>10**5 or y<1 or y <=0 or y>10**5:
		print ('Illegal')
		exit()
	a.append([x,y])
a.sort()
s=0
for i in range(num_lines):
	for j in range(i+1,num_lines):
		if(a[i][0]==a[j][0]):
			s+=1
		else:
			break
print (s)

Submission status: Wrong Answer

Solution code:
def qfind(q,p,s,e):
	l=int((s+e)/2)
	
	if q[l]==p:
		if(l<=s or q[l-1]!=p):
			return l
		else:
			return qfind(q,p,s,l-1)
	elif q[l]>p:
		if l<=s:
			return -1
		else:
			return qfind(q,p,s,l-1)
	else:
		if l>=e:
			return -1
		else:
			return qfind(q,p,l+1,e)

num_lines = int(input())
if num_lines<1 or num_lines>10**5:
	print ('Illegal')
	exit()
a=[]
for i in range(num_lines):
	x,y=map(int,input().split(" "))
	if x<1  or y>10**5 or y<1 or y <=0 or y>10**5:
		print ('Illegal')
		exit()
	a.append([x,y])
a.sort()
s=0
for i in range(num_lines):
	for j in range(i+1,num_lines):
		if(a[i][0]==a[j][0]):
			for m in range(num_lines):
				if a[m][0]!=a[i][0]:
					if a[m][1]==a[i][1]:
						id=qfind(a,[a[m][0],a[j][1]],0,num_lines-1)
						if id<0:
							s+=1
#							print(a[i],a[j],a[m],[a[m][0],a[j][1]])
					elif a[m][1]==a[j][1]:
						id=qfind(a,[a[m][0],a[i][1]],0,num_lines-1)
						if id<0:
							s+=1
#							print(a[i],a[j],a[m],[a[m][0],a[i][1]])
		else:
			break;
print (s)

Submission status: Wrong Answer

Solution code:
def qfind(q,p,s,e):
	l=int((s+e)/2)
	
	if q[l][0]==p:
		if(l<=s or q[l-1][0] !=p):
			return l
		else:
			return qfind(q,p,s,l-1)
	elif q[l][0]>p:
		if l<=s:
			return -1
		else:
			return qfind(q,p,s,l-1)
	else:
		if l>=e:
			return -1
		else:
			return qfind(q,p,l+1,e)

num_lines = int(input())
if num_lines<1 or num_lines>10**5:
	print ('Illegal')
	exit()
a=[]
b=[]
for i in range(num_lines):
	x,y=map(int,input().split(" "))
	if x<1  or y>10**5 or y<1 or y <=0 or y>10**5:
		print ('Illegal')
		exit()
	a.append([x,y])
	b.append([y,x])
a.sort()
b.sort()
s=0
for i in range(num_lines):
	for j in range(i+1,num_lines):
		if(a[i][0]==a[j][0]):
			id=qfind(b,a[i][1],0,num_lines-1)
			if id >= 0:
				for m in range(id,num_lines):
					if b[m][0]!=b[id][0]:
						break;
					if not([b[m][1],a[j][1]] in a):
						s+=1
#						print(a[i],a[j],[b[m][1],b[m][0]],[b[m][1],a[j][1]])
			id=qfind(b,a[j][1],0,num_lines-1)
			if id >= 0:
				for m in range(id,num_lines):
					if b[m][0]!=b[id][0]:
						break;
					if not([b[m][1],a[i][1]] in a):
#						print(a[i],a[j],[b[m][1],b[m][0]],[b[m][1],a[i][1]])
						s+=1
		else:
			break;
print (s)

Submission status: Wrong Answer

Solution code:
N = int(input())
xl = []
yl = []
for i in range(N):
    x,y = map(int,input().split())
    xl.append(x)
    yl.append(y)
xlen = len(set(xl))
ylen = len(set(yl))
if N==2:
    print(0)
else:
    print(xlen*ylen-N)

Submission status: Wrong Answer

Solution code:
def append_p(p, xpeers_s, ypeers_s):
  x = p[X]
  if not x in xpeers_s:
    xpeers_s[x] = []
  xpeers_s[x].append(p)

  y = p[Y]
  if not y in ypeers_s:
    ypeers_s[y] = []
  ypeers_s[y].append(p)
  
  
X = 0
Y = 1
n = int(input())
p_set = set(tuple(int(v) for v in input().split()) for _ in range(n))
xpeers_s = {}
ypeers_s = {}
for p in p_set:
  append_p(p, xpeers_s, ypeers_s)

#print(p_set)
#print(xpeers_s)
#print(ypeers_s)
#print("")
ans = 0
for _rep in range(10):
#while True:
  repeat = False
  p_set_new = set()
  for p in p_set:
    x = p[X]
    y = p[Y]
    if (x in xpeers_s) and (y in ypeers_s):
      xpeers = xpeers_s[x]
      ypeers = ypeers_s[y]
      #print(xpeers, ypeers)
      for xpeer in xpeers:
        for ypeer in ypeers:
          dpeer = (ypeer[X], xpeer[Y])
          #print(xpeer, ypeer)
          if not dpeer in p_set:
            ans += 1
            repeat = True
            p_set_new.add(dpeer)
            
  #print("repeat={}, ans={}".format(repeat, ans))
  p_set |= p_set_new
  for p_new in p_set_new:
    #print(p_new)
    append_p(p_new, xpeers_s, ypeers_s)
  if not repeat:
    break
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

x = [0 for _ in range(N)]
y = [0 for _ in range(N)]

for i in range(N):
  s = input().split()
  x[i] = int(s[0])
  y[i] = int(s[1])

xd = {}
yd = {}

for i in range(N):
  xd[x[i]] = xd.get(x[i], 0) + 1
  yd[y[i]] = yd.get(y[i], 0) + 1

ans = 0
for i in range(N):
  ans += (xd[x[i]]-1) * (yd[y[i]]-1)

print(ans)

Submission status: Wrong Answer

Solution code:
# import sys
# sys.setrecursionlimit(20000)


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


class Group:
    
    def __init__(self):
        self.n = 0
        self.x = []
        self.y = []
        
    def new_cor_n(self):
        return len(self.x) * len(self.y) - self.n
        

def grouping(group, x, xcor, ycor):
    x_list = []
    group.x.append(x)
    for y in xcor[x][0]:
        group.n += 1
        if ycor[y][1]:
            continue
        ycor[y][1] = True
        group.y.append(y)
        for x_ in ycor[y][0]:
            group.n += 1
            if xcor[x_][1]:
                continue
            xcor[x_][1] = True
            x_list.append(x_)
    return x_list

if False:
    print(0)
else:
    xcor, ycor = {}, {}
    for xi, yi in COR:
        if xi in xcor:
            xcor[xi][0].append(yi)
        else:
            xcor[xi] = [[yi], False]
        if yi in ycor:
            ycor[yi][0].append(xi)
        else:
            ycor[yi] = [[xi], False]
    group_list = []
    for i, v in xcor.items():
        if v[1]:
            continue
        group = Group()
        group_list.append(group)
        xcor[i][1] = True
        x_list = [i]
        while True:
            new_x_list = []
            for x in x_list:
                new_x_list += grouping(group, x, xcor, ycor)
            if new_x_list == []:
                break
            x_list = new_x_list
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)

Submission status: Wrong Answer

Solution code:
# import sys
# sys.setrecursionlimit(20000)


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


class Group:
    
    def __init__(self):
        self.n = 0
        self.x = []
        self.y = []
        
    def new_cor_n(self):
        if self.n == 0:
            return 0
        return len(self.x) * len(self.y) - self.n
        

def grouping(group, x, xcor, ycor):
    x_list = []
    group.x.append(x)
    for y in xcor[x][0]:
        if ycor[y][1]:
            continue
        group.n += 1
        ycor[y][1] = True
        group.y.append(y)
        for x_ in ycor[y][0]:
            if xcor[x_][1]:
                continue
            group.n += 1
            xcor[x_][1] = True
            x_list.append(x_)
    return x_list

if N <= 2:
    print(0)
else:
    xcor, ycor = {}, {}
    for xi, yi in COR:
        if xi in xcor:
            xcor[xi][0].append(yi)
        else:
            xcor[xi] = [[yi], False]
        if yi in ycor:
            ycor[yi][0].append(xi)
        else:
            ycor[yi] = [[xi], False]
    group_list = []
    for i, v in xcor.items():
        if v[1]:
            continue
        group = Group()
        group_list.append(group)
        xcor[i][1] = True
        x_list = [i]
        while True:
            new_x_list = []
            for x in x_list:
                new_x_list += grouping(group, x, xcor, ycor)
            if new_x_list == []:
                break
            x_list = new_x_list
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)

Submission status: Wrong Answer

Solution code:
# import sys
# sys.setrecursionlimit(20000)


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


class Group:
    
    def __init__(self):
        self.n = 0
        self.x = []
        self.y = []
        
    def new_cor_n(self):
        return len(self.x) * len(self.y) - self.n
        

def grouping(group, x, xcor, ycor):
    x_list = []
    group.x.append(x)
    for y in xcor[x][0]:
        if ycor[y][1]:
            continue
        group.n += 1
        ycor[y][1] = True
        group.y.append(y)
        for x_ in ycor[y][0]:
            if xcor[x_][1]:
                continue
            group.n += 1
            xcor[x_][1] = True
            x_list.append(x_)
    return x_list

if N <= 2:
    print(0)
else:
    xcor, ycor = {}, {}
    for xi, yi in COR:
        if xi in xcor:
            xcor[xi][0].append(yi)
        else:
            xcor[xi] = [[yi], False]
        if yi in ycor:
            ycor[yi][0].append(xi)
        else:
            ycor[yi] = [[xi], False]
    group_list = []
    for i, v in xcor.items():
        if v[1]:
            continue
        group = Group()
        group_list.append(group)
        xcor[i][1] = True
        x_list = [i]
        while True:
            new_x_list = []
            for x in x_list:
                new_x_list += grouping(group, x, xcor, ycor)
            if new_x_list == []:
                break
            x_list = new_x_list
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)

Submission status: Wrong Answer

Solution code:
n=int(input())
xys=[list(map(int,input().split()))for i in range(n)]
x = [0]*(10**5+3)
y = [0]*(10**5+3)
for i in range(n):
    x[xys[i][0]]+=1
    y[xys[i][1]]+=1
cntx = 0
cnty = 0
for i in range(10**5+2):
    cntx += max(0,x[i]-1)
    cnty += max(0,y[i]-1)
print(cntx*cnty)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    xy = [LI() for _ in range(n)]
    xd = collections.defaultdict(set)
    yd = collections.defaultdict(set)

    for x,y in xy:
        xd[x].add(y)
        yd[y].add(x)

    r = 0
    for x,v in xd.items():
        c = 0
        s = set()
        for y in v:
            c += len(yd[y] - v)
            s |= yd[y]
        r += len(s - v)

    return r


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    xy = [LI() for _ in range(n)]
    xd = collections.defaultdict(set)
    yd = collections.defaultdict(set)

    for x,y in xy:
        xd[x].add(y)
        yd[y].add(x)

    r = 0
    for x,v in xd.items():
        c = 0
        for y in v:
            c += len(yd[y] - v)
        r += c

    return r


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    xy = [LI() for _ in range(n)]
    xd = collections.defaultdict(set)
    yd = collections.defaultdict(set)

    for x,y in xy:
        xd[x].add(y)
        yd[y].add(x)

    r = 0
    for x,v in xd.items():
        c = 0
        s = set()
        for y in v:
            c += len(yd[y])
            s |= yd[y]
        r += len(v) * len(s) - c

    return r


print(main())

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
max_n = 10**5
ans = 0
n = int(input())

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.sizea = [1 if _ < n//2 else 0 for _ in range(n)]
        self.sizeb = [0 if _ < n//2 else 1 for _ in range(n)]
        self.sizec = [1 for _ in range(n)]
        self.rank = [0] * (n)
        
    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 is_root(self, x):
        if self.par[x] == x:
            return True
        else:
            return False
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.sizea[x] += self.sizea[y]
            self.sizeb[x] += self.sizeb[y]
            self.sizec[x] += self.sizec[y]

    def get_size(self, x):
        x = self.find(x)
        return self.sizea[x],self.sizeb[x],self.sizec[x]

uf = UnionFind(2*max_n)

for _ in range(n):
  x,y = map(int, input().split())
  x -= 1
  y += max_n - 1
  uf.union(x, y)

for i in range(max_n):
  if uf.is_root(i):
    a,b,c = uf.get_size(i)
    if a > 1 and b > 1:
      ans += a*b -(c-1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
max_n = 10**5
ans = 0
n = int(input())

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.sizea = [1 if _ < n//2 else 0 for _ in range(n)]
        self.sizeb = [0 if _ < n//2 else 1 for _ in range(n)]
        self.sizec = [1 for _ in range(n)]
        self.rank = [0] * (n)
        
    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 is_root(self, x):
        if self.par[x] == x:
            return True
        else:
            return False
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.sizea[x] += self.sizea[y]
            self.sizeb[x] += self.sizeb[y]
            self.sizec[x] += self.sizec[y]

    def get_size(self, x):
        x = self.find(x)
        return self.sizea[x],self.sizeb[x],self.sizec[x]

uf = UnionFind(2*max_n)

for _ in range(n):
  x,y = map(int, input().split())
  x -= 1
  y += max_n - 1
  uf.union(x, y)

for i in range(max_n):
  if uf.is_root(i):
    a,b,c = uf.get_size(i)
    if a*b > 1:
      ans += a*b -(c-1)
print(ans)

Submission status: Wrong Answer

Solution code:
# import sys
# sys.setrecursionlimit(20000)

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


class Group:
    
    def __init__(self):
        self.n = 0
        self.x = []
        self.y = []
        
    def new_cor_n(self):
        return len(self.x) * len(self.y) - self.n
        
    
def grouping(group, x, xcor, ycor):
    x_list = []
    group.x.append(x)
    for y in xcor[x][0]:
        if ycor[y][1]:
            continue
        group.n += 1
        ycor[y][1] = True
        group.y.append(y)
        for x_ in ycor[y][0]:
            if xcor[x_][1]:
                continue
            group.n += 1
            xcor[x_][1] = True
            x_list.append(x_)
    return x_list

if N <= 2:
    print(0)
else:
    xcor, ycor = {}, {}
    for xi, yi in COR:
        if xi in xcor:
            xcor[xi][0].append(yi)
        else:
            xcor[xi] = [[yi], False]
        if yi in ycor:
            ycor[yi][0].append(xi)
        else:
            ycor[yi] = [[xi], False]
    group_list = []
    for i, v in xcor.items():
        if v[1]:
            continue
        group = Group()
        group_list.append(group)
        xcor[i][1] = True
        x_list = [i]
        while True:
            new_x_list = []
            for x in x_list:
                new_x_list += grouping(group, x, xcor, ycor)
            if new_x_list == []:
                break
            x_list = new_x_list
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

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


class Group:
    
    def __init__(self):
        self.n = 0
        self.x = []
        self.y = []
        
#     def insertx(self, x):
#         self.x[x] = None

#     def inserty(self, y):
#         self.y[y] = None
        
    def new_cor_n(self):
        if self.n == 0:
            return 0
        return len(self.x) * len(self.y) - self.n

    def join(self, group):
        self.n += group.n
        for x in group.x:
            self.x[x] = None
        for y in group.y:
            self.y[y] = None
        group.n = 0

def grouping_y(group, y, xcor, ycor):
    ycor[y][1] = True
    group.y.append(y)
    for x in ycor[y][0]:
        if xcor[x][1]:
            continue
        group.n += 1
        grouping_x(group, x, xcor, ycor)
        
def grouping_x(group, x, xcor, ycor):
    xcor[x][1] = True
    group.x.append(x)
    for y in xcor[x][0]:
        if ycor[y][1]:
            continue
        group.n += 1
        grouping_y(group, y, xcor, ycor)
    
if N <= 2:
    print(0)
else:
    xcor, ycor = {}, {}
    for xi, yi in COR:
        if xi in xcor:
            xcor[xi][0].append(yi)
        else:
            xcor[xi] = [[yi], False]
        if yi in ycor:
            ycor[yi][0].append(xi)
        else:
            ycor[yi] = [[xi], False]
    group_list = []
    for x, v in xcor.items():
        if v[1]:
            continue
        group = Group()
        group_list.append(group)
        grouping_x(group, x, xcor, ycor)
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)

Submission status: Wrong Answer

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


class Group:
    
    def __init__(self, x, y):
        self.n = 1
        self.x = {x: None}
        self.y = {y: None}
        
    def insertx(self, x):
        self.x[x] = None
        self.n += 1

    def inserty(self, y):
        self.y[y] = None
        self.n += 1
        
    def new_cor_n(self):
        if self.n == 0:
            return 0
        return len(self.x) * len(self.y) - self.n

    def join(self, group):
        self.n += group.n
        for x in group.x:
            self.x[x] = None
        for y in group.y:
            self.y[y] = None
        group.n = 0

if N <= 2:
    print(0)
else:
    xg, yg = {}, {}
    group_list = []
    for xi, yi in COR:
        if xi in xg:
            group1 = xg[xi]
            if yi in yg:
                group2 = yg[yi]
                if group2 is group1:
                    pass
                else:
                    for xk in group2.x:
                        xg[xk] = group1
                    for yk in group2.y:
                        yg[yk] = group1
                    group1.join(group2)
                    group1.n += 1
            else:
                yg[yi] = group1
                group1.inserty(yi)
        elif yi in yg:
            group = yg[yi]
            xg[xi] = group
            group.insertx(xi)
        else:
            new_group = Group(xi, yi)
            xg[xi] = new_group
            yg[yi] = new_group
            group_list.append(new_group)
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)

Submission status: Wrong Answer

Solution code:
N = int(input())
points = []
for i in range(0, N):
    points.append(list(map(int, input().split(' '))))
X = dict()
Y = dict()
count = 0
for p in points:
    if p[0] not in X.keys():
        X[p[0]] = []
    X[p[0]].append(p[1])
    if p[1] not in Y.keys():
        Y[p[1]] = []
    Y[p[1]].append(p[0])
while len(X.items()) > 0:
    item = list(X.items())[0]
    del X[item[0]]
    stack = [item]
    point_dict = {'x': [], 'y': []}
    is_X = True
    while len(stack) > 0:
        item = stack.pop(0)
        if is_X:
            point_dict['x'].append(item[0])
            for i in item[1]:
                if i in Y.keys():
                    stack.append((i, Y[i]))
                    del Y[i]
            is_X = False
        else:
            point_dict['y'].append(item[0])
            for i in item[1]:
                if i in X.keys():
                    stack.append((i, X[i]))
                    del X[i]
            is_X = True
    count += len(point_dict['x']) * len(point_dict['y'])

print(count - len(points))

Submission status: Wrong Answer

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

class Union:
  def __init__(s, n):
    s.N = n
    s.L = [-1] * n

  def root(s, x):
    if s.L[x] < 0:
      return x, -s.L[x]
    return s.root(s.L[x])

  def merge(s, x, y):
    a, ar = s.root(x)
    b, br = s.root(y)
    if a == b:
      return True
    if ar < br:
      s.L[b] -= ar
      s.L[a] = b
    else:
      s.L[a] -= br
      s.L[b] = a
    return False

  def getList(s):
    D = []
    DN = [0] * N
    for i in range(N):
      if s.L[i] < 0:
        DN[i] = len(D)
        D.append([])
    for i in range(N):
      D[DN[s.root(i)[0]]].append(i)
    return D

M = 10**5 + 1
xL = [-1] * M
yL = [-1] * M
uni = Union(N)

for i in range(N):
  x = xy[i][0]
  y = xy[i][1]
  if xL[x] != -1:
    uni.merge(xL[x], i)
  elif yL[y] != -1:
    uni.merge(yL[y], i)
  xL[x] = i
  yL[y] = i

L = uni.getList()
ans = 0
for t in L:
  xL = [0] * M
  yL = [0] * M
  xN = 0
  yN = 0
  for i in t:
    x, y = xy[i]
    if xL[x] == 0:
      xL[x] = 1
      xN += 1
    if yL[y] == 0:
      yL[y] = 1
      yN += 1
  if xN >= 2 and yN >= 2:
    ans += xN * yN - len(t)

print(ans)

Submission status: Wrong Answer

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


class Group:
    
    def __init__(self, x, y):
        self.n = 1
        self.x = {x: None}
        self.y = {y: None}
        
    def insert(self, x, y):
        self.x[x] = None
        self.y[y] = None
        self.n += 1
    
    def new_cor_n(self):
        if self.n == 0:
            return 0
        return len(self.x) * len(self.y) - self.n

    def join(self, group):
        self.n += group.n
        for x, y in zip(group.x, group.y):
            self.x[x] = None
            self.y[y] = None
        group.n = 0

if N <= 2:
    print(0)
else:
    xg, yg = {}, {}
    group_list = []
    for xi, yi in COR:
        if xi in xg:
            group1 = xg[xi]
            if yi in yg:
                group2 = yg[yi]
                if group2 is group1:
                    pass
                else:
                    for xk in group2.x:
                        xg[xk] = group1
                    for yk in group2.y:
                        yg[yk] = group1
                    group1.join(group2)
            yg[yi] = group1
            group1.insert(xi, yi)
        elif yi in yg:
            group = yg[yi]
            xg[xi] = group
            group.insert(xi, yi)
        else:
            new_group = Group(xi, yi)
            xg[xi] = new_group
            yg[yi] = new_group
            group_list.append(new_group)
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)