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: Runtime Error

Solution code:
n = int(input())
edges = [[] for i in range(2*10**5)]
for i in range(n):
    xi, yi = map(int, input().split())
    xi -= 1
    yi = yi - 1 + 10**5
    edges[xi].append(yi)
    edges[yi].append(xi)

already = set([])
def dfs(x, y, node):
    if node in already:
        return x, y
    if node < 10**5:
        x += 1
    else:
        y += 1
    already.add(node)
    for next_node in edges[node]:
        x, y = dfs(x, y, next_node)
    return x, y

num = 0
for i in range(10**5):
    x, y = dfs(0, 0, i)
    num += x * y
print(num-n)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
n = int(input())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    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) 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())
unionfind = UnionFind(n)
x_d = defaultdict(set)
y_d = defaultdict(set)
for i in range(n):
    x_d[data[i][0]].add(i)
    y_d[data[i][1]].add(i)

for i in range(n):
    x, y = data[i]
    if len(x_d[x]) > 1 and len(y_d[y]) > 1:
        for j in x_d[x]:
            unionfind.union(i, j)
        for j in y_d[y]:
            unionfind.union(i, j)

point = [[] for i in range(n)]
for i in range(n):
    if unionfind.size(i) <= 2:
        continue
    else:
        point[unionfind.find(i)].append(i)
ans = 0
for i in range(n):
    if len(point[i]) > 2 :
        x_s = defaultdict(int)
        y_s = defaultdict(int)
        for j in range(len(point)):
            x, y = data[point[i][j]]
            x_s[x] += 1
            y_s[y] += 1
        ans += len(x_s) * len(y_s) - len(point)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n = int(input())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    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) 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())
unionfind = UnionFind(n)
x_d = defaultdict(set)
y_d = defaultdict(set)
for i in range(n):
    x_d[data[i][0]].add(i)
    y_d[data[i][1]].add(i)

for i in range(n):
    x, y = data[i]
    if len(x_d[x]) > 1 and len(y_d[y]) > 1:
        for j in x_d[x]:
            unionfind.union(i, j)
        for j in y_d[y]:
            unionfind.union(i, j)

point = [[] for i in range(n)]
for i in range(n):
    if unionfind.size(i) <= 2:
        continue
    else:
        point[unionfind.find(i)].append(i)
ans = 0
for i in range(n):
    if len(point[i]) > 2 :
        x_s = defaultdict(int)
        y_s = defaultdict(int)
        for j in range(len(point)):
            x, y = data[point[i][j]]
            x_s[x] += 1
            y_s[y] += 1
        ans += len(x_s) * len(y_s) - len(point)
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from itertools import product
sys.setrecursionlimit(10**8)


INF = float("inf")


def compress(X, Y):
    dx = list(sorted(set(X)))
    dx_inv = {x: i for i, x in enumerate(dx)}
    dy = list(sorted(set(Y)))
    dy_inv = {y: i for i, y in enumerate(dy)}
    return (dx, dy), (dx_inv, dy_inv)


def main():
    N = int(input())
    X = [0]*N
    Y = [0]*N
    for i in range(N):
        X[i], Y[i] = map(int, input().split())

    (dx, dy), (dx_inv, dy_inv) = compress(X, Y)

    X2Y = [set() for _ in dx]   # XからYを求める
    Y2X = [set() for _ in dy]   # YからXを求める
    for i in range(N):
        X2Y[dx_inv[X[i]]].add(dy_inv[Y[i]])
        Y2X[dy_inv[Y[i]]].add(dx_inv[X[i]])

    cnt = 0
    head = 0
    queue = [(dx_inv[X[i]], dy_inv[Y[i]]) for i in range(N)]
    while head < len(queue):    # 最終的な節点の個数だけのループ最悪(10^10/4)
        x, y = queue[head]
        head += 1
        samex = X2Y[x]
        samey = Y2X[y]
        # 全ての組み合わせを追加
        additive = []
        for nx in samex:
            if nx == x:
                continue
            nys = samey-X2Y[nx]
            additive.extend([(nx, ny) for ny in nys])
            cnt += len(nys)
            X2Y[nx] |= nys
            for ny in nys:
                Y2X[ny].add(nx)
    print(cnt)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from itertools import product


INF = float("inf")


def compress(X, Y):
    dx = list(sorted(set(X)))
    dx_inv = {x: i for i, x in enumerate(dx)}
    dy = list(sorted(set(Y)))
    dy_inv = {y: i for i, y in enumerate(dy)}
    return (dx, dy), (dx_inv, dy_inv)


# X = [-INF, 0, INF] + A + B + D
# Y = [-INF, 0, INF] + C + E + F
# (dx, dy), (dx_inv, dy_inv) = compress(X, Y)
# H = len(dy)
# W = len(dx)

def main():
    N = int(input())
    X = [0]*N
    Y = [0]*N
    for i in range(N):
        X[i], Y[i] = map(int, input().split())

    (dx, dy), (dx_inv, dy_inv) = compress(X, Y)

    X2Y = [set() for _ in dx]   # XからYを求める
    Y2X = [set() for _ in dy]   # YからXを求める
    for i in range(N):
        X2Y[dx_inv[X[i]]].add(dy_inv[Y[i]])
        Y2X[dy_inv[Y[i]]].add(dx_inv[X[i]])

    cnt = 0
    head = 0
    queue = [(dx_inv[X[i]], dy_inv[Y[i]]) for i in range(N)]
    while head < len(queue):    # 最終的な節点の個数だけのループ最悪(10^10/4)
        x, y = queue[head]
        head += 1
        samex = X2Y[x]
        samey = Y2X[y]
        # 全ての組み合わせを追加
        additive = []
        for nx in samex:
            if nx == x:
                continue
            nys = samey-X2Y[nx]
            additive.extend([(nx, ny) for ny in nys])
            cnt += len(nys)
            X2Y[nx] |= nys
            for ny in nys:
                Y2X[ny].add(nx)
    print(cnt)
    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

N = int(input())
d = defaultdict(list)
cd = set()
D = 100000

for _ in range(N):
    x, y = map(int, input().split())
    y += D
    cd.add(x)
    d[x].append(y)
    d[y].append(x)

used = [0]*(D+1)
ans = 0

for x in cd:
    if used[x]:continue
    q = [x]
    used[x] = 1
    cx, sx = 0, 0

    while q:
        a = q.pop()
        if a<=D:
            cx += 1
        sx += 1
        for b in d[a]:
            if used[b]:continue
            used[b] = 1
            q.append(b)
    ans += cx*(sx-cx)

print(ans-N)

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def main():

    """
    <UnionFindを使わない別解>

    x方向とy方向に分けて頂点を辺だと思うのは定石？？？（確かに長方形がメインなら直積分解したくなる？）
    このとき問題文は「長さ３のパスがあればパスを１本追加する操作を繰り返して、各連結成分を完全二部グラフにせよ」

    完全二部グラフになるのは背理法からすぐわかる。なので解法は(¥Sum_{i:component}X_i Y_i) - N
    """

    N = int(input())
    V = 10 ** 5 + 1 # padding for y
    repn = [[] for _ in range(V * 2)]
    for _ in range(N):
        x, y = map(int, input().split())
        repn[x].append(V + y)
        repn[V + y].append(x)

    visited = [0] * (V * 2)
    count = [0, 0]

    # dfsでその都度連結成分を求める
    def dfs(v):
        if visited[v]:
            return
        visited[v] = 1
        count[v // V] += 1
        for u in repn[v]:
            dfs(u)

    ans = 0
    for i in range(V * 2):
        if visited[i]:
            continue
        count[:] = [0, 0]
        dfs(i)
        ans += count[0] * count[1]
    print(ans - N)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter

class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)

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

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


MAX = 10 ** 5
uf = UnionFind(2 * MAX)

N, *XY = map(int, open(0).read().split())

for x, y in zip(*[iter(XY)] * 2):
    uf.union(x, y + MAX)

X = Counter(uf.find(i) for i in range(MAX))
Y = Counter(uf.find(i) for i in range(MAX, MAX * 2))
res = sum(X[i] * Y[i] for i in range(MAX * 2))

print(res - N)

Submission status: Runtime Error

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

n = int(input())
xy = [[[] for _ in range(10**5+1)] for __ in range(2)]

for _ in range(n):
    x,y = map(int,input().split())
    xy[0][x].append(y)
    xy[1][y].append(x)

ans = 0
used = [[False for _ in range(10**5+1)] for __ in range(2)]

def dfs(i,flag):
    for v in xy[flag][i]:
        if not used[1-flag][v]:
            used[1-flag][v] = True
            dfs(v,1-flag)
            count[1-flag] += 1

for i in range(10**5+1):
    if xy[0][i] and not used[0][i]:
        used[0][i] = True
        count = [1,0]
        dfs(i,0)
        ans += count[0]*count[1]

ans -= n
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
xy = [[[] for _ in range(10**5+1)] for __ in range(2)]

for _ in range(n):
    x,y = map(int,input().split())
    xy[0][x].append(y)
    xy[1][y].append(x)

ans = 0
used = [[False for _ in range(10**5+1)] for __ in range(2)]

def dfs(i,flag):
    for v in xy[flag][i]:
        if not used[1-flag][v]:
            used[1-flag][v] = True
            dfs(v,1-flag)
            count[1-flag] += 1

for i in range(10**5+1):
    if xy[0][i] and not used[0][i]:
        used[0][i] = True
        count = [1,0]
        dfs(i,0)
        ans += count[0]*count[1]

ans -= n
print(ans)

Submission status: Runtime Error

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):
  activex[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 activex[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
                  activex_next[targety]=1
  times+=1
                  
  activex=activex_next.copy() 
  activey=activey_next.copy() 
print(num)

Submission status: Runtime Error

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]):
			a+=1
		else:
			break
print (s)

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
def ycheck(nx,ny,i,j,array):
    for k in range(ny):
        if k != j and array[i][k] == 1:
            xcheck(nx,ny,i,k,j,array)
            return

def xcheck(nx,ny,i,k,j,array):
    for l in range(nx):
        if l != i and array[l][k] == 1:
            if array[l][j] == 1:
                array[i][j] = 2
                return

N = int(input())
xl = []
yl = []
for i in range(N):
    x,y = map(int,input().split())
    xl.append(x)
    yl.append(y)
setx = set(xl)
sety = set(yl)
nx = len(setx)
ny = len(sety)
array = [[0 for i in range(nx)] for j in range(ny)]

xlist = list(set(xl))
xlist.sort()
ylist = list(set(yl))
ylist.sort()

for i in range(N):
    xp = xlist.index(xl[i])
    yp = ylist.index(yl[i])
    array[xp][yp] = 1

for i in range(nx):
    for j in range(ny):
        if array[i][j] == 0:
            flg = 0
            ycheck(nx,ny,i,j,array)

count=0
for i in range(nx):
    for j in range(ny):
        if array[i][j] == 2:
            count+=1
print(count)

Submission status: Runtime Error

Solution code:
import numpy as np

#userの入力回数
N = int(input())

ls = []
max_x = 0
max_y = 0

#N回x,yを受け取る
#x軸とy軸の最大値も併せて更新する
for i in range(N):
    x,y = map(int,input().split())
    ls.append([x,y])
    if max_x > x and max_y > y:
        continue
    elif max_x < x and max_y > y:
        max_x = x
    elif max_x > x and max_y < y:
        max_y = y
    else:
        max_x,max_y = x, y

#すべて0の座標を作るグラフを作る
square = np.zeros((max_x,max_y), dtype = int)

a = 0
aa = 0
b = 1

max_retu = square.shape
max_retu = max_retu[-1] - 1

cnt = max_retu

#全て0の座標を更新する
for i,j in ls:
    square[i-1,j-1] = 1

old_one =np.count_nonzero(square)

for i in range((max_x -1) * (max_y -1)):
    if square[a,aa] + square[a,b] + square[a+1,aa] + square[a+1,b] == 3:
        square[a,aa] = 1
        square[a,b] = 1
        square[a+1,aa] = 1 
        square[a+1,b] = 1
        b += 1
        cnt -= 1
        aa += 1
        if cnt == 0:
            cnt = max_retu
            a += 1
            b = 1
            aa = 0
    else:
        b += 1
        cnt -= 1
        aa += 1
        if cnt is 0:
            cnt = max_retu
            a += 1
            b = 1
            aa = 0
s = 0 
x = 1
y = 1
for i in range(max_x -1):
    if square[s,s] + square[s,x] + square[y,s] + square[x,y] == 3:
        square[s,s] = 1
        square[s,x] = 1
        square[y,s] = 1
        square[x,y] = 1
        x += 1
        y += 1
    else:
        x += 1
        y += 1
            
new_one =np.count_nonzero(square)
print(new_one - old_one)

Submission status: Runtime Error

Solution code:
import numpy as np

#userの入力回数
N = int(input())

ls = []
max_x = 0
max_y = 0

#N回x,yを受け取る
#x軸とy軸の最大値も併せて更新する
for i in range(N):
    x,y = map(int,input().split())
    ls.append([x,y])
    if max_x > x and max_y > y:
        continue
    elif max_x < x and max_y > y:
        max_x = x
    elif max_x > x and max_y < y:
        max_y = y
    else:
        max_x,max_y = x, y

#すべて0の座標を作るグラフを作る
square = np.zeros((max_x,max_y), dtype = int)

a = 0
aa = 0
b = 1

max_retu = square.shape
max_retu = max_retu[-1] - 1

cnt = max_retu

#全て0の座標を更新する
for i,j in ls:
    square[i-1,j-1] = 1

old_one =np.count_nonzero(square)

for i in range((max_x -1) * (max_y -1)):
    if square[a,aa] + square[a,b] + square[a+1,aa] + square[a+1,b] == 3:
        square[a,aa] = 1
        square[a,b] = 1
        square[a+1,aa] = 1 
        square[a+1,b] = 1
        b += 1
        cnt -= 1
        aa += 1
        if cnt == 0:
            cnt = max_retu
            a += 1
            b = 1
            aa = 0
    else:
        b += 1
        cnt -= 1
        aa += 1
        if cnt is 0:
            cnt = max_retu
            a += 1
            b = 1
            aa = 0
s = 0 
ss = 0
x = 1
y = 1
for i in range(max_x -1):
    if square[s,s] + square[s,x] + square[y,s] + square[x,y] == 3:
        square[s,s] = 1
        square[s,x] = 1
        square[y,s] = 1
        square[x,y] = 1
        ss += 1
        x += 1
        y += 1
    else:
        ss += 1
        x += 1
        y += 1
            
new_one =np.count_nonzero(square)


print(new_one - old_one)

Submission status: Runtime Error

Solution code:
MAXVAL = 10**5
N = int(input())
edge = [[] for _ in range(MAXVAL*2)]
visited = [0] * (MAXVAL*2)
ans = 0
xnum = 0; ynum = 0; nodes = 0

def dfs(n):
    global xnum, ynum, nodes
    if visited[n] == 1:
        return True
    if n < MAXVAL:
        xnum += 1
    else:
        ynum += 1
    visited[n] = 1
    for item in edge[n]:
        nodes += 1
        dfs(item)
    return True

for i in range(N):
    x, y = [int(item) for item in input().split()]
    x -= 1; y -= 1
    edge[x].append(y+MAXVAL)
    edge[y+MAXVAL].append(x)

for i in range(MAXVAL*2):
    if visited[i] == 1:
        continue
    xnum = 0; ynum = 0; nodes = 0
    dfs(i)
    if nodes >= 3:
        ans += xnum * ynum - nodes // 2
print(ans)

Submission status: Runtime Error

Solution code:
V = 100005
to = [[] for i in range(V*2)]
n = int(input())
visited = [False for i in range(V*2)]
counter = []
def dfs(v):
    if(visited[v]):
        return
    visited[v] = True
    counter[v//V] +=1
    for u in to[v]:
        dfs(u)



for i in range(n):
    x,y = map(int, input().split())
    y += V
    to[x].append(y)
    to[y].append(x)
ans = 0
for i in range(V*2):
    if (visited[i]):
        continue
    counter = [0,0]
    dfs(i)
    ans += counter[0]*counter[1]

ans -= n
print(ans)

Submission status: Runtime Error

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

n = inn()
x2y = defaultdict(list)
y2x = defaultdict(list)
xys = []
for i in range(n):
    x,y = inm()
    x -= 1
    y -= 1
    x2y[x].append(y)
    y2x[y].append(x)
    xys.append((x,y))

markx = [False] * 100001
marky = [False] * 100001

def dfsy(x,y):
    st = {(x,y)}
    for x in y2x[y]:
        if markx[x]:
            continue
        markx[x] = True
        st |= dfsx(x,y)
    return st

def dfsx(x,y):
    st = {(x,y)}
    for y in x2y[x]:
        if marky[y]:
            continue
        marky[y] = True
        st |= dfsy(x,y)
    return st

sum = 0
for x,y in xys:
    if markx[x] or marky[y]:
        continue
    if len(x2y[x])>1 and len(y2x[y])>1:
        st = {(x,y)}
        markx[x] = True
        marky[y] = True
        for yy in x2y[x]:
            st |= dfsy(x,yy)
        for xx in y2x[y]:
            st |= dfsx(xx,y)
        numx = len(set([z[0] for z in list(st)]))
        numy = len(set([z[1] for z in list(st)]))
        sum += numx*numy - len(st)

print(sum)

Submission status: Runtime Error

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

n = inn()
x2y = defaultdict(list)
y2x = defaultdict(list)
xys = []
for i in range(n):
    x,y = inm()
    x2y[x].append(y)
    y2x[y].append(x)
    xys.append((x,y))

markx = [False] * 100001
marky = [False] * 100001

def dfsy(x,y):
    st = {(x,y)}
    for x in y2x[y]:
        if markx[x]:
            continue
        markx[x] = True
        st |= dfsx(x,y)
    return st

def dfsx(x,y):
    st = {(x,y)}
    for y in x2y[x]:
        if marky[y]:
            continue
        marky[y] = True
        st |= dfsy(x,y)
    return st

sum = 0
for x,y in xys:
    if markx[x] or marky[y]:
        continue
    if len(x2y[x])>1 and len(y2x[y])>1:
        st = {(x,y)}
        markx[x] = True
        marky[y] = True
        for yy in x2y[x]:
            st |= dfsy(x,yy)
        for xx in y2x[y]:
            st |= dfsx(xx,y)
        numx = len(set([z[0] for z in list(st)]))
        numy = len(set([z[1] for z in list(st)]))
        sum += numx*numy - len(st)

print(sum)

Submission status: Runtime Error

Solution code:
N = int(input())
xy = [None for _in range(N),None for _ in range(N)]

for i in range(N):

Submission status: Runtime Error

Solution code:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3
#sys.setrecursionlimit(int(1e+7))  # スタック上限

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    XY = ii2nnn(N)
    M = int(1e+5) + 5

    # 二部グラフ
    to = [[] for _ in range(M*2)]
    cnt = [0] * (M*2)
    visited = [False] * (M*2)

    # 二部グラフを構築
    for x, y in XY:
        y += M
        to[x].append(y)
        to[y].append(x)

    cnt = [0, 0]
    def dfs(i):
        if visited[i]:
            return
        visited[i] = True
        cnt[i // M] += 1
        for j in to[i]:
            dfs(j)

    # 二部グラフを走査
    ans = 0
    for i in range(M*2):
        if visited[i]:
            continue
        cnt[0] = 0
        cnt[1] = 0
        dfs(i)
        ans += cnt[0] * cnt[1]
    
    ans -= N  # 既にある点は操作数に含まれない
    print(ans)

main()

Submission status: Runtime Error

Solution code:
V = 100005
N = int(input())

lines = [[] for _ in range(V * 2)]
visited = [False] * V * 2

count = []
def dfs(v):
	global count
	if visited[v]:
		return
	visited[v] = True
	count[v // V] += 1
	for u in lines[v]:
		dfs(u)


for i in range(N):
	x, y = [int(x) for x in input().split()]
	y += V
	lines[x].append(y)
	lines[y].append(x)

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

ans -= N
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5)
m = 100005
visited = [False]*(m*2)
cnt = [0,0]
def dfs(i):
    visited[i] = True
    cnt[i//m] +＝ 1
    for j in to[i]:
        if not visited[j]:
            dfs(j)
 
input = sys.stdin.readline
n = int(input())
to = [[] for _ in range(m*2)]
for _ in range(n):
    x,y = map(int,input().split())
    y = y+m
    to[x].append(y)
    to[y].append(x)
 
ans = 0
for i in range(m):
    if not visited[i]:
        cnt = [0,0]
        dfs(i)
        ans = ans + cnt[0]*cnt[1]
 
print(ans-n)

Submission status: Runtime Error

Solution code:
def dfs(x, al):
    global cntx, cnty
    if (al, x) in used:
        return
    used.add((al, x))
    if al == 0:
        cntx += 1
    else:
        cnty += 1
    for xy in to[al][x]:
        dfs(xy, 1 - al)
    return

n = int(input())
to = [{}, {}]
for _ in range(n):
    x, y = map(int, input().split())
    to[0].setdefault(x, [])
    to[1].setdefault(y, [])
    to[0][x] += [y]
    to[1][y] += [x]
used = set()
ans = 0
for x in to[0].keys():
    if (0, x) in used: continue
    cntx = 0
    cnty = 0
    dfs(x, 0)
    ans += cntx * cnty
print(ans - n)

Submission status: Runtime Error

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


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: Runtime Error

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[x][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: Runtime Error

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 = []
    xcor[x][1] = True
    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[x][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: Runtime Error

Solution code:
import sys

def main():
    input = sys.stdin.readline
    V = 10**5  # max size of x
    N = int(input())
    bgraph = [[] for _ in range(2*V)]
    for _ in range(N):
        x, y = map(int, input().split())
        x -= 1
        y += V - 1
        bgraph[x].append(y)
        bgraph[y].append(x)

    def dfs(i):
        if visited[i]:
            return cnt
        visited[i] = True
        cnt[i//V] += 1
        for j in bgraph[i]:
            dfs(j)
        return cnt

    visited = [False] * (2*V)
    ans = 0
    for i in range(V):
        if visited[i]:
            continue
        cnt = [0, 0]
        cnt = dfs(i)
        ans += cnt[0] * cnt[1]

    ans -= N
    return ans


if __name__ == '__main__':
    print(main())