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())
MAX = 10**5
adj = [[[] for u in range(MAX+1)] for t in range(2)]
vis = [[False for u in range(MAX+1)] for t in range(2)]
for i in range(n):
	x, y = map(int,input().split())
	adj[0][x].append(y)
	adj[1][y].append(x)

import sys
sys.setrecursionlimit(4*10**5+1)

def dfs(t,u): # Left, Right, Edges
	vis[t][u] = True

	ct = [0,0,0]
	ct[t] += 1
	for v in adj[t][u]:
		if not vis[t^1][v]:
			ct[2] += 1
			ctv = dfs(t^1,v)

			ct[0] += ctv[0]
			ct[1] += ctv[1]
			ct[2] += ctv[2]

	return ct

ans = 0
for u in range(1,MAX+1):
	if not vis[0][u]:
		L, R, M = dfs(0,u)
		ans += L*R-M

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
y_x = defaultdict(int)
x_y = defaultdict(int)
max_x = 0
min_x = 10**6
max_y = 0
min_y = 10**6
p = []
for _ in range(n):
    x, y = map(int, input().split())
    y_x[x] += 1
    x_y[y] += 1
    p.append((x, y))
    max_x = max(max_x, x)
    min_x = min(min_x, x)
    max_y = max(max_y, y)
    min_y = min(min_y, y)


ans = (max_x - min_x + 1) * (max_y - min_y + 1) - n
for i in range(n):
    x, y = p[i]
    if y_x[x] > 1 and x_y[y] > 1:
        print(ans)
        exit()
print(0)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

N = int(input())
vertex = set()
conn = [[] for _ in range(2*10**5 + 1)]
check = [False]*(2*10**5 + 1)
for i in range(N):
    x, y = [int(x) for x in input().split()]
    vertex.add(x)
    vertex.add(y + 10**5)
    conn[x].append(y + 10**5)
    conn[y + 10**5].append(x)

count = [0] * 2
def dfs(z):
    if check[z] == True:
        return
    check[z] = True
    if z <= 10**5:
        count[0] += 1
    else:
        count[1] += 1
    for w in conn[z]:
        dfs(w)

ans = 0
for z in vertex:
    if check[z] == False:
        count = [0]*2
        dfs(z)
        X, Y = count[0], count[1]
        ans += X * Y
ans -= N

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from operator import itemgetter
input = sys.stdin.readline

def main():
    n = int(input())
    p = [list(map(int, input().split()))+[i] for i in range(n)]
    tree = [[] for _ in range(n)]
    
    p.sort()
    for i in range(n-1):
        if p[i][0] == p[i+1][0]:
            tree[p[i][2]].append(p[i+1][2])
            tree[p[i+1][2]].append(p[i][2])
            
    p.sort(key=itemgetter(1))
    for i in range(n-1):
        if p[i][1] == p[i+1][1]:
            tree[p[i][2]].append(p[i+1][2])
            tree[p[i+1][2]].append(p[i][2])
    
    p.sort()
    
    already = [False]*n
    ans = -n
    for i in range(n):
        if already[i]:
            continue
        already[i] = True
        not_yet = deque([i])
        key_x = {p[i][0]}
        key_y = {p[i][1]}
        while not_yet:
            key = not_yet.popleft()
            for v in tree[key]:
                if already[v]:
                    continue
                already[v] = True
                key_x.add(p[v][0])
                key_y.add(p[v][1])
                not_yet.append(v)
        ans += len(key_x)*len(key_y)
    
    print(ans)
        
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy as copy
from operator import itemgetter
input = sys.stdin.readline

def main():
    n = int(input())
    p = [list(map(int, input().split()))+[i] for i in range(n)]
    tree = [[] for _ in range(n)]
    
    p.sort()
    for i in range(n-1):
        if p[i][0] == p[i+1][0]:
            tree[p[i][2]].append(p[i+1][2])
            tree[p[i+1][2]].append(p[i][2])
    
    q = copy(p)
    q.sort(key=itemgetter(1))

    for i in range(n-1):
        if q[i][1] == q[i+1][1]:
            tree[q[i][2]].append(q[i+1][2])
            tree[q[i+1][2]].append(q[i][2])
            
    ans = -n
    already = [False]*n
    
    for i in range(n):
        if already[i]:
            continue
        already[i] = True
        
        not_yet = [i]
        key_x = {p[i][0]}
        key_y = {p[i][1]}
        while not_yet:
            key = not_yet.pop()
            for v in tree[key]:
                if already[v]:
                    continue
                already[v] = True
                not_yet.append(v)
                key_x.add(p[v][0])
                key_y.add(p[v][1])
        
        ans += len(key_x)*len(key_y)

    print(ans)
        
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy as copy
from operator import itemgetter
input = sys.stdin.readline

def main():
    n = int(input())
    p = [list(map(int, input().split()))+[i+1] for i in range(n)]
    tree = [[] for _ in range(10**5)]
    
    p.sort()
    for i in range(n-1):
        if p[i][0] == p[i+1][0]:
            tree[p[i][2]-1].append(p[i+1][2]-1)
            tree[p[i+1][2]-1].append(p[i][2]-1)
    
    q = copy(p)
    q.sort(key=itemgetter(1))

    for i in range(n-1):
        if q[i][1] == q[i+1][1]:
            tree[q[i][2]-1].append(q[i+1][2]-1)
            tree[q[i+1][2]-1].append(q[i][2]-1)
            
    ans = -n
    already = [False]*n
    
    for i in range(n):
        if already[i]:
            continue
        already[i] = True
        
        not_yet = [i]
        key_x = {p[i][0]}
        key_y = {p[i][1]}
        while not_yet:
            key = not_yet.pop()
            for v in tree[key]:
                if already[v]:
                    continue
                already[v] = True
                not_yet.append(v)
                key_x.add(p[v][0])
                key_y.add(p[v][1])
        
        ans += len(key_x)*len(key_y)

    print(ans)
        
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy as copy
from operator import itemgetter
input = sys.stdin.readline
                
def compress(lis, n=2, last_sort=False):
    length = len(lis)
    first_value = -1
    for i in range(n):
        lis.sort(key=itemgetter(i))
        value = first_value
        index = 0
        for j in range(length):
            if lis[j][i] != value:
                index += 1
            value = lis[j][i]
            lis[j][i] = index
    
    if last_sort: lis.sort()
    return lis


def main():
    n = int(input())
    p = [list(map(int, input().split()))+[i+1] for i in range(n)]
    compress(p)
    tree = [[] for _ in range(n)]
    
    p.sort()
    for i in range(n-1):
        if p[i][0] == p[i+1][0]:
            tree[p[i][2]-1].append(p[i+1][2]-1)
            tree[p[i+1][2]-1].append(p[i][2]-1)
    
    q = copy(p)
    q.sort(key=itemgetter(1))
    
    for i in range(n-1):
        if q[i][1] == q[i+1][1]:
            tree[q[i][2]-1].append(q[i+1][2]-1)
            tree[q[i+1][2]-1].append(q[i][2]-1)   

    ans = -n
    already = [False]*n
    
    for i in range(n):
        if already[i]:
            continue
        already[i] = True
        
        not_yet = [i]
        key_x = {p[i][0]}
        key_y = {p[i][1]}
        while not_yet:
            key = not_yet.pop()
            for v in tree[key]:
                if already[v]:
                    continue
                already[v] = True
                not_yet.append(v)
                key_x.add(p[v][0])
                key_y.add(p[v][1])
        ans += len(key_x)*len(key_y)

    print(ans)
        
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
input = sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [-1]*(n+1)#それぞれの要素がどの要素の子であるか
        self.cycle = [i for i in range(n+1)]

    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 union(self, x, y):
        self.cycle[x], self.cycle[y] = self.cycle[y], self.cycle[x]
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        
        self.par[x] += self.par[y]
        self.par[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)#x,yが同じ集合に属するかどうか
    
    def size(self, x):
        return -self.par[self.find(x)]
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if root == self.find(i)]        

def compress(lis, n=2, last_sort=False):
    length = len(lis)
    first_value = -1
    for i in range(n):
        lis.sort(key=itemgetter(i))
        value = first_value
        index = 0
        for j in range(length):
            if lis[j][i] != value:
                index += 1
            value = lis[j][i]
            lis[j][i] = index
    
    if last_sort: lis.sort()
    return lis
                

def main():
    n = int(input())
    p = [list(map(int, input().split())) for _ in range(n)]
    
    compress(p, last_sort=True)
    
    key = [set() for _ in range(n+1)]
    for i in range(n):
        key[p[i][1]].add(p[i][0])
    
    union = UnionFind(n)
    for i in range(n-1):
        if p[i][0] == p[i+1][0]:
            union.union(p[i][1], p[i+1][1])
    
    already = [False]*(n+1)
    
    ans = 0
    for i in range(1, n+1):
        if already[i]:
            continue
        index = i
        table = [index]
        while True:
            already[index] = True
            index = union.cycle[index]
            if index == i:
                break
            table.append(index)
        judge = set()
        field = 0
        for v in table:
            judge = judge | key[v]
            field -= len(key[v])
        field += len(table)*len(judge)
        ans += field
        
    print(ans)
            
        
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
input = sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [-1]*(n+1)#それぞれの要素がどの要素の子であるか

    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        
        self.par[x] += self.par[y]
        self.par[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)#x,yが同じ集合に属するかどうか
    
    def size(self, x):
        return -self.par[self.find(x)]
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if root == self.find(i)]        

def compress(lis, n=2, last_sort=False):
    length = len(lis)
    first_value = -1
    for i in range(n):
        lis.sort(key=itemgetter(i))
        value = first_value
        index = 0
        for j in range(length):
            if lis[j][i] != value:
                index += 1
            value = lis[j][i]
            lis[j][i] = index
    
    if last_sort: lis.sort()
    return lis
                

def main():
    n = int(input())
    p = [list(map(int, input().split())) for _ in range(n)]
    
    compress(p, last_sort=True)
    
    key = [set() for _ in range(n+1)]
    for i in range(n):
        key[p[i][1]].add(p[i][0])
    
    member = [set() for i in range(n+1)]
    union = UnionFind(n)
    for i in range(n-1):
        if p[i][0] == p[i+1][0]:
            union.union(p[i][1], p[i+1][1])
            member[union.find(p[i][1])].add(p[i+1][1])
    
    ans = 0
    for i in range(1, n+1):
        if not member[i]:
            continue
        member[i].add(i)
        judge = set()
        field = 0
        for v in member[i]:
            judge = judge | key[v]
            field -= len(key[v])
        field += len(member[i])*len(judge)
        ans += field
        
    print(ans)
            
        
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
input = sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [-1]*(n+1)#それぞれの要素がどの要素の子であるか

    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        
        self.par[x] += self.par[y]
        self.par[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)#x,yが同じ集合に属するかどうか
    
    def size(self, x):
        return -self.par[self.find(x)]
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if root == self.find(i)]        

def compress(lis, n=2, last_sort=False):
    length = len(lis)
    first_value = -1
    for i in range(n):
        lis.sort(key=itemgetter(i))
        value = first_value
        index = 0
        for j in range(length):
            if lis[j][i] != value:
                index += 1
            value = lis[j][i]
            lis[j][i] = index
    
    if last_sort: lis.sort()
    return lis
                

def main():
    n = int(input())
    p = [list(map(int, input().split())) for _ in range(n)]
    
    compress(p, last_sort=True)
    
    key = [set() for _ in range(n+1)]
    for i in range(n):
        key[p[i][1]].add(p[i][0])
    
    member = [{i} for i in range(n+1)]
    union = UnionFind(n)
    for i in range(n-1):
        if p[i][0] == p[i+1][0]:
            union.union(p[i][1], p[i+1][1])
            member[union.find(p[i][1])].add(p[i+1][1])
    
    ans = 0
    already = [False]*(n+1)
    for i in range(1, n+1):
        if already[i]:
            continue
        table = member[i]
        judge = set()
        field = 0
        for v in table:
            already[v] = True
            judge = judge | key[v]
            field -= len(key[v])
        field += len(table)*len(judge)
        ans += field
        
    print(ans)
            
        
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
input = sys.stdin.readline


def compress(lis, n=2, last_sort=False):
    length = len(lis)
    first_value = -1
    for i in range(n):
        lis.sort(key=itemgetter(i))
        value = first_value
        index = 0
        for j in range(length):
            if lis[j][i] != value:
                index += 1
            value = lis[j][i]
            lis[j][i] = index
    
    if last_sort: lis.sort()
    return lis
                

def main():
    n = int(input())
    p = [list(map(int, input().split())) for _ in range(n)]
    
    compress(p, last_sort=True)
    
    key_x = set()
    ind, val = p[0]
    for i in range(1, n):
        if ind == p[i][0]:
            key_x.add(p[i][1])
            key_x.add(p[i-1][1])
        else:
            ind = p[i][0]
    
    p.sort(key=itemgetter(1))
    key_y = set()
    val, ind = p[0]
    for i in range(1, n):
        if ind == p[i][1]:
            key_y.add(p[i][0])
            key_y.add(p[i-1][0])
        else:
            ind = p[i][1]
    
    ans = len(key_x)*len(key_y)
    for i in range(n):
        if p[i][0] in key_x and p[i][1] in key_y:
            ans -= 1
    
    print(ans)
    
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
N=int(input())
G=[[] for i in range(200000)]
x,y=0,0
B=[0]*200000
for i in range(N):
  x,y=map(int,input().split())
  G[99999+y].append(x-1)
  G[x-1].append(99999+y)
P=0
CE=0
CV=0
def dfs(p,n):
  global CE,CV
  CE+=1
  if B[n]:
    return 0
  CV+=1
  B[n]=1
  for i in range(len(G[n])):
    if G[n][i]!=p:
      dfs(n,G[n][i])

for i in range(200000):
  if ~B[i]:
    CE=0
    CV=0
    dfs(-1,i)
    P+=(CV>>1)*((CV+1)>>1)-CE+1
print(P)

Submission status: Wrong Answer

Solution code:
n = int(input())

pos_max = 100000

dic = dict()

for _ in range(n):
    x, y = map(int, input().split())
    y += pos_max
    if not x in dic:
        dic[x] = set()
    if not y in dic:
        dic[y] = set()
    dic[x].add(y)
    dic[y].add(x)
checked = set()

count = 0
for x in dic:
    if x in checked:
        continue
    checked.add(x)

    member = {x}
    next_items = {x}
    while next_items:
        v = next_items.pop()
        temp = dic[v] - checked
        next_items |= dic[v] - checked
        checked |= dic[v]
    x_n = sum(w <= pos_max for w in member)
    y_n = sum(w >  pos_max for w in member)
    count += x_n * y_n
print(count - n)

Submission status: Wrong Answer

Solution code:
n = int(input())

pos_max = 100000

dic = dict()

for _ in range(n):
    x, y = map(int, input().split())
    y += pos_max
    if not x in dic:
        dic[x] = set()
    if not y in dic:
        dic[y] = set()
    dic[x].add(y)
    dic[y].add(x)

checked = set()

count = 0
for x in dic:
    if x in checked:
        continue
    checked.add(x)

    member = {x}
    next_member = {x}
    edge_n = 0
    while next_member:
        v = next_member.pop()
        temp = set(filter(lambda w : not w in checked, dic[v]))
        edge_n += len(temp)
        member |= temp
        next_member |= temp
        checked |= temp
    x_n = sum(w <= pos_max for w in member)
    y_n = sum(w >  pos_max for w in member)
    count += x_n * y_n - edge_n
print(count)
    
        

        
    
count = 0

Submission status: Wrong Answer

Solution code:
import sys

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

n, *xy = map(int, read().split())
XY = zip(xy, xy)

max_num = 10 ** 5
delta = 10 ** 5 + 10

graph = [[] for _ in range(max_num + delta + 1)]

for x, y in XY:
    graph[x].append(delta + y)
    graph[delta + y].append(x)

x_used = [False] * (max_num + 1)
y_used = [False] * (max_num + 1)


def dfs(idx):
    x_res = 0
    y_res = 0
    edgenum = 0
    stack = []
    stack.append(idx)
    if idx >= delta:
        y_used[idx % delta] = True
    else:
        x_used[idx] = True
    while stack:
        v = stack.pop()
        if v >= delta:
            # if y_used[v % delta]:
            #     continue
            # y_used[v % delta] = True
            y_res += 1
        else:
            # if x_used[v]:
            #     continue
            # x_used[v] = True
            x_res += 1
        for u in graph[v]:
            if u >= delta:
                if y_used[u % delta]:
                    continue
                y_used[u % delta] = True
            else:
                if x_used[u]:
                    continue
                x_used[u] = True
            edgenum += 1
            stack.append(u)
    res = x_res * y_res
    return res


ans = 0
ok_flag = 0
for i in range(max_num + 1):
    if x_used[i]:
        continue
    temp = dfs(i)
    ans += temp
for i in range(max_num + 1):
    if y_used[i]:
        continue
    i += delta
    temp = dfs(i)
    ans += temp
print(ans - n)

Submission status: Wrong Answer

Solution code:
import collections

N = int(input())
XY = [[int(x) for x in input().split()] for _ in range(N)]

if len(XY) <= 2:
    print(0)
    exit()

xset = set()
yset = set()
xc = collections.Counter()
yc = collections.Counter()
for x, y in XY:
    xset.add(x)
    yset.add(y)
    xc[x] += 1
    yc[x] += 1
xone = 0
yone = 0
for k in xc.keys():
    if xc[k] == 1:
        xone += 1
for k in yc.keys():
    if yc[k] == 1:
        yone += 1

print((xone * (len(yset) - yone)) * (len(xset) - xone) * yone)

Submission status: Wrong Answer

Solution code:
N = int(input())
XY = [[int(x) for x in input().split()] for _ in range(N)]

if len(XY) <= 2:
    print(0)
    exit()

xset = set()
yset = set()
for x, y in XY:
    xset.add(x)
    yset.add(y)

print(len(yset) * len(xset) - len(XY))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def main():
    N = int(input())
    P = [list(map(int, input().split(' '))) for _ in range(N)]
    x_group, y_group = defaultdict(list), defaultdict(list)
    for i, p in enumerate(P):
        x, y = p
        x_group[x].append(i)
        y_group[y].append(i)
    used = [0] * N
    x_line, y_line = defaultdict(int), defaultdict(int)
    for g in [x_group, y_group]:
        for group in g.values():
            if len(group) < 2:
                continue
            for i in group:
                x, y = P[i]
                x_line[x] = 1
                y_line[y] = 1
                used[i] = 1
    print(len(x_line.keys()) * len(y_line.keys()) - sum(used))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

dic={}
for i in range(n):
    x,y=xy[i]
    if (0,x) in dic:
        dic[(0,x)].append(y)
    else:
        dic[(0,x)]=[y]
    x,y=y,x
    if (1,x) in dic:
        dic[(1,x)].append(y)
    else:
        dic[(1,x)]=[y]
# print(dic)

lst=[[0]*(10**5+1) for i in range(2)]

ans=0
for x,y in xy:
    if lst[0][x]==1:
        continue
    lst[0][x]=1
    d=deque([(0,x)])
    xcnt,ycnt=0,0
    cnt=0
    while d:
        # print(d)
        now=d.popleft()
        if now[0]==0:
            xcnt+=1
        else:
            ycnt+=1
        for j in dic[now]:
            if lst[1-now[0]][j]==0:
                lst[1-now[0]][j]=1
                cnt+=1
                d.append((1-now[0],j))
    # print(xcnt,ycnt,cnt)
    ans+=xcnt*ycnt-cnt
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
V = set()
E = {}

for _ in range(N):
  x,y = map(int, input().split())
  y += 100010
  V.add(x)
  V.add(y)
  if x not in E:
    E[x] = [y]
  else:
    E[x].append(y)
  if y not in E:
    E[y] = [x]
  else:
    E[y].append(x)
    
## DFS
visited = [ False ] * 200020
willSearch = [ False ] * 200020
Q = deque()
ans = 0
for v in V:
  if visited[v]:
    continue

  Q.append(v)
  xcount, ycount = 0,0
  edge_count = 0
  while len(Q) > 0:
    now = Q.pop()
    visited[now] = True

    if now > 100005:
      ycount += 1
    else:
      xcount += 1
      
    for nxt in E[now]:
      if visited[nxt] or willSearch[nxt]:
        continue
      willSearch[nxt] = True
      edge_count += 1
      Q.append(nxt)
  #print(xcount, ycount, edge_count)
  ans += xcount * ycount
  ans -= edge_count
  
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

def dfs(G, F, crr, pre, ret):
    F[crr] = False
    if crr < 10**5:
        ret[0] += 1
    else:
        ret[1] += 1
    for nxt in G[crr]:
        if nxt == pre:
            continue
        if F[nxt]:
            ret[2] += 1
            dfs(G, F, nxt, crr, ret)

def main():
    n = int(input())
    G = [[] for _ in range(2 * 10**5)]
    for _ in range(n):
        x, y = map(int, input().split())
        x, y = x-1, y-1 + 10**5
        G[x].append(y)
        G[y].append(x)
    F = [True]*(2* 10**5)
    ans = 0
    for i in range(2 * 10**5):
        if F[i] and len(G[i]) > 0:
            tmp = [0]*3
            dfs(G, F, i, -1, tmp)
            ans += tmp[0] * tmp[1] - tmp[2]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

def dfs(G, F, crr, pre, ret):
    F[crr] = False
    if crr < 10**5:
        ret[0] += 1
    else:
        ret[1] += 1
    for nxt in G[crr]:
        if nxt == pre:
            continue
        ret[2] += 1
        if F[nxt]:
            dfs(G, F, nxt, crr, ret)

def main():
    n = int(input())
    G = [[] for _ in range(2 * 10**5)]
    for _ in range(n):
        x, y = map(int, input().split())
        x, y = x-1, y-1 + 10**5
        G[x].append(y)
        G[y].append(x)
    F = [True]*(2* 10**5)
    ans = 0
    for i in range(2 * 10**5):
        if F[i] and len(G[i]) > 0:
            tmp = [0]*3
            dfs(G, F, i, -1, tmp)
            ans += tmp[0] * tmp[1] - tmp[2]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# 二部ぐらふ、知らなかった
from collections import defaultdict


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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n + 1) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N = int(input())
U = UnionFind(2*10**5)
for i in range(N):
    x, y = map(int, input().split())
    U.union(x, y+10**5)
ans = 0
Roots = U.roots()

A = {i: [0, 0] for i in range(2*10**5+1)}
for i in range(1, 10**5+1):
    A[U.find(i)][0] += 1
for i in range(10**5+1, 2*10**5):
    A[U.find(i)][1] += 1
for i in Roots:
    ans += A[i][0]*A[i][1]
print(ans-N)

Submission status: Wrong Answer

Solution code:
# 二部ぐらふ、知らなかった
from collections import defaultdict


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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n + 1) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N = int(input())
U = UnionFind(2*10**5)
for i in range(N):
    x, y = map(int, input().split())
    U.union(x, y+10**5)
ans = 0
Roots = U.roots()

A = {i: [0, 0] for i in range(1, 2*10**5+1)}
for i in range(1, 10**5+1):
    A[U.find(i)][0] += 1
for i in range(10**5+1, 2*10**5):
    A[U.find(i)][1] += 1
for i in range(1, 2*10**5+1):
    ans += A[i][0]*A[i][1]
print(ans-N)

Submission status: Wrong Answer

Solution code:
# F must be rectangular
from collections import defaultdict, deque
N = int(input())
# 一回の操作で点は一つ増える。かつ直感的に特殊な時以外では回答はかなり少なくなるはず
X = defaultdict(list)
Y = defaultdict(list)
D = deque()
visited = defaultdict(bool)
for i in range(N):
    x, y = map(int, input().split())
    X[x].append(y)
    Y[y].append(x)
    D.append((x, y))
    visited[(x, y)] = False
ans = 0
while D:
    px, py = D.popleft()
    if visited[(px, py)] == True:
        continue
    else:
        sx = X[px]  # (px,?)
        sy = Y[py]  # (?,py)
        if len(sx)>1 and len(sy)>1:
            for y_node in sx:
                visited[(px, y_node)] = True
            for x_node in sy:
                visited[(x_node, py)] = True
            ans += len(sx)*len(sy)
ans -= N
print(ans)

Submission status: Wrong Answer

Solution code:
# F must be rectangular
from collections import defaultdict, deque
N = int(input())
# 一回の操作で点は一つ増える。かつ直感的に特殊な時以外では回答はかなり少なくなるはず
X = defaultdict(list)
Y = defaultdict(list)
D = deque()
visited = defaultdict(bool)
for i in range(N):
    x, y = map(int, input().split())
    X[x].append(y)
    Y[y].append(x)
    D.append((x, y))
    visited[(x, y)] = False
ans = 0
while D:
    px, py = D.popleft()
    if visited[(px, py)] == True:
        continue
    else:
        sx = X[px]  # (px,?)
        sy = Y[py]  # (?,py)
        for y_node in sx:
            visited[(px, y_node)] = True
        for x_node in sy:
            visited[(x_node, py)] = True
    ans += len(sx)*len(sy)
ans -= N
print(ans)