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())
V = 100005

to = [[] for _ in range(V*2)]
visited = [False] * (V*2)
cnt = [0, 0]

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

def main():
    ans = 0

    # 二部グラフの作成
    for i in range(N):
        x, y = map(int, input().split())
        y += V
        to[x].append(y)
        to[y].append(x)

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

    ans -= N
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

N = int(input())
V = 100005

to = [[] for _ in range(V*2)]
visited = [False] * (V*2)
cnt = [0, 0]

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

def main():
    ans = 0

    # 二部グラフの作成
    for i in range(N):
        x, y = map(int, input().split())
        y += V
        to[x].append(y)
        to[y].append(x)

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

    ans -= N
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

class UnionFind:
    def __init__(self,N): # 頂点数 N
        self.table = [i for i in range(N)]    #木の親 table[x] == x なら根
        self.rank  = [1 for i in range(N)]    #木の長さ
        self.size  = [1 for i in range(N)]    #集合のサイズ

    def Find(self,x):    #xの根を返す
        if self.table[x] == x:
            return x
        else:
            self.table[x] = self.Find(self.table[x])    #親の更新(根を直接親にして参照距離を短く)
            self.size[x] = self.size[self.table[x]]
            return self.table[x]

    def Unite(self,x,y):    #xとyを繋げる
        x,y = self.Find(x), self.Find(y)
        sx,sy = self.Size(x), self.Size(y)
        if x == y: return
        if self.rank[x] > self.rank[y]:
            self.table[y] = x
            self.size[x] = sx + sy
        else:
            self.table[x] = y
            self.size[y] = sx + sy
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def Check(self,x,y):
        return self.Find(x) == self.Find(y)

    def Size(self,x):
        return self.size[self.Find(x)]



N = int(input())
UF = UnionFind(N)

xys = [inpl() for _ in range(N)]
xys.sort()
tatedict = defaultdict(list)
xx = set()
for x,y in xys:
    tatedict[x].append(y)
    xx.add(x)

for x in xx:
    s = tatedict[x][0]
    for t in tatedict[x]:
        if not UF.Check(s,t):
            UF.Unite(s,t)

ans = 0
for x in xx:
    s = tatedict[x][0]
    ans += UF.Size(s) - len(tatedict[x])

print(ans)

Submission status: Runtime Error

Solution code:
V=10**5
class UnionFind:
    def __init__(self,n):
        self.parent=[i for i in range(n)]
        self.rank=[0 for _ in range(n)]
        # use for n=2*V
        self.xSize=[1 if i<V else 0 for i in range(n)]
        self.ySize=[0 if i<V else 1 for i in range(n)]

    def find(self,x):
        if self.parent[x]==x:
            return x
        else:
            parentx=self.find(self.parent[x])
            self.parent[x]=parentx
            return parentx

    def union(self,x,y):
        rootx=self.find(x)
        rooty=self.find(y)
        if self.rank[rootx]>self.rank[rooty]:
            self.parent[rooty]=rootx
            self.xSize[rootx]+=self.xSize[rooty]
            self.ySize[rootx]+=self.ySize[rooty]
        else:
            self.parent[rootx]=rooty
            self.xSize[rooty]+=self.xSize[rootx]
            self.ySize[rooty]+=self.ySize[rootx]
            if self.rank[rootx]==self.rank[rooty]:
                self.rank[rooty]+=1

n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
uf=UnionFind(V*2)
for xi,yi in xy:
    uf.union(xi,yi+V)

for i in range(V*2):
    uf.find(i)

ans=0
used=set()
for i in range(V*2):
    rooti=uf.find(i)
    if rooti not in used:
        used.add(rooti)
        ans+= uf.xSize[rooti]*uf.ySize[rooti]
print(ans-n)

Submission status: Runtime Error

Solution code:
V=10**5
class UnionFind:
    def __init__(self,n):
        self.parent=[i for i in range(n)]
        self.rank=[0 for _ in range(n)]
        # use for n=2*V
        self.xSize=[1 if i<V else 0 for i in range(n)]
        self.ySize=[0 if i<V else 1 for i in range(n)]

    def find(self,x):
        if self.parent[x]==x:
            return x
        else:
            parentx=self.find(self.parent[x])
            self.parent[x]=parentx
            return parentx

    def union(self,x,y):
        rootx=self.find(x)
        rooty=self.find(y)
        if self.rank[rootx]>self.rank[rooty]:
            self.parent[rooty]=rootx
            self.xSize[rootx]+=self.xSize[rooty]
            self.ySize[rootx]+=self.ySize[rooty]
        else:
            self.parent[rootx]=rooty
            self.xSize[rooty]+=self.xSize[rootx]
            self.ySize[rooty]+=self.ySize[rootx]
            if self.rank[rootx]==self.rank[rooty]:
                self.rank[rooty]+=1

n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
uf=UnionFind(V*2)
for xi,yi in xy:
    uf.union(xi,yi+V)

ans=0
used=set()
for i in range(V*2):
    rooti=uf.find(i)
    if rooti not in used:
        used.add(rooti)
        ans+= uf.xSize[rooti]*uf.ySize[rooti]
print(ans-n)

Submission status: Runtime Error

Solution code:
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 insert(self, x, y):
        if x not in self.x:
            self.x.append(x)
        if y not in self.y:
            self.y.append(y)
        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
        self.x.extend(group.x)
        self.x = list(set(self.x))
        self.y.extend(group.y)
        self.y = list(set(self.y))
        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)

Submission status: Runtime Error

Solution code:
class Group:
    
    def __init__(self, x, y):
        self.n = 1
        self.x = [x]
        self.y = [y]
        
    def insert(self, x, y):
        if x not in self.x:
            self.x.append(x)
        if y not in self.y:
            self.y.append(y)
        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
        self.x.extend(group.x)
        self.x = list(set(self.x))
        self.y.extend(group.y)
        self.y = list(set(self.y))
        group.n = 0


if N <= 2:
    print(0)
else:
    xg, yg = {}, {}
    group_list = []
    for xi, yi in COR:
        if xi in xg:
            if yi in yg:
                xg[xi].join(yg[yi])
            group = xg[xi]
            yg[yi] = group
            group.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)

Submission status: Runtime Error

Solution code:
F-Must_Be_Rectangular
Python 3  
File
Edit
View
Insert
Cell
Kernel
Widgets
Help
1
N = int(input())
2
COR = [tuple((map(int, input().split()))) for _ in range(N)]
3
​
8
1 1
2 1
3 1
1 2
2 6
4 4
5 3
5 4
)
1
class Group:
2
    
3
    def __init__(self, x, y):
4
        self.n = 1
5
        self.x = [x]
6
        self.y = [y]
7
        
8
    def insert(self, x, y):
9
        if x not in self.x:
10
            self.x.append(x)
11
        if y not in self.y:
12
            self.y.append(y)
13
        self.n += 1
14
    
15
    def new_cor_n(self):
16
        if self.n == 0:
17
            return 0
18
        return len(self.x) * len(self.y) - self.n
19
​
20
    def join(self, group):
21
        self.n += group.n
22
        self.x.extend(group.x)
23
        self.x = list(set(self.x))
24
        self.y.extend(group.y)
25
        self.y = list(set(self.y))
26
        group.n = 0
27
​
28
​
29
if N <= 2:
30
    print(0)
31
else:
32
    xg, yg = {}, {}
33
    group_list = []
34
    for xi, yi in COR:
35
        if xi in xg:
36
            if yi in yg:
37
                xg[xi].join(yg[yi])
38
            group = xg[xi]
39
            yg[yi] = group
40
            group.insert(xi, yi)
41
        elif yi in yg:
42
            group = yg[yi]
43
            xg[xi] = group
44
            group.insert(xi, yi)
45
        else:
46
            new_group = Group(xi, yi)
47
            xg[xi] = new_group
48
            yg[yi] = new_group
49
            group_list.append(new_group)
50
    s = 0
51
    for group in group_list:
52
        s += group.new_cor_n()
53
    print(s)
5

Submission status: Runtime Error

Solution code:
m = 100005
visited = [False]*(m*2)
cnt = [0,0]
def dfs(i):
    global cnt
    if visited[i]:
        return
    visited[i] = True
    cnt[i//m] = cnt[i//m] + 1
    for j in to[i]:
        dfs(j)


n = int(input())
to = [[] for i in range(m*2)]
for i 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*2):
    cnt = [0,0]
    dfs(i)
    ans = ans + cnt[0]*cnt[1]

print(ans-n)

Submission status: Runtime Error

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

X = {}
Y = {}
G = (X, Y)

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


def dfs_visit(visited, u, i):
  if u in visited[i]: return
  visited[i].add(u)
  for v in G[i][u]:
    dfs_visit(visited, v, (i + 1) % 2)


count = 0
while len(X) > 0:
  visited = (set(), set())
  x = X.__iter__().__next__()
  dfs_visit(visited, x, 0)

  for x in visited[0]:
    count += len(visited[1]) - len(X.pop(x))
  for y in visited[1]:
    del Y[y]

print(count)

Submission status: Runtime Error

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

X = {}
Y = {}
G = (X, Y)

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


def dfs_visit(visited, u, i):
  if u in visited[i]: return
  visited[i].add(u)
  for v in G[i][u]: dfs_visit(visited, v, (i + 1) % 2)


count = 0
while len(X) > 0:
  visited = (set(), set())
  x = X.__iter__().__next__()
  dfs_visit(visited, x, 0)

  for x in visited[0]:
    count += len(visited[1]) - len(X.pop(x))

print(count)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import deque



class UnionFind():
  def __init__(self):
    self.group = deque()
  
  def merge(self,i,j):
    ## i <- j
    self.group[i][0] |= self.group[j][0]
    self.group[i][1] |= self.group[j][1]
    self.group[i][2] += self.group[j][2]
    self.group.pop(j)

  def new(self,x,y):
    merge_i = -1
    l = len(self.group)
    for i in range(l):
      if x in self.group[i][0] or y in self.group[i][1]:
        if merge_i >= 0:
          self.merge(merge_i,i)
        else:
          self.group[i][0].add(x)
          self.group[i][1].add(y)
          self.group[i][2] += 1
          merge_i = i
    if merge_i < 0:
      self.group.append([set([x]),set([y]),1])

  def output(self):
    ret = 0
    for i in range(len(self.group)):
      x = len(self.group[i][0])
      y = len(self.group[i][1])
      if x*y >= 4:
        ret += x*y-self.group[i][2]
    return ret



def main():
  N = int(input())
  uf = UnionFind()
  for _ in range(N):
    x,y = map(int, input().split())
    uf.new(x,y)
  print(uf.output())

if __name__ == "__main__":
  main()

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)

def DFS(i, XorY=0):
    for next in XY[XorY][i]:
        if visited[1-XorY][next]==0:
            visited[1-XorY][next] = 1
            DFS(next, 1-XorY)
            count[1-XorY] += 1

ans = 0
visited = [[0 for _ in range(10**5 +1)] for __ in range(2)]
for i in range(10**5 +1):
    if XY[0][i]!=[] and visited[0][i]==0:
        visited[0][i]=1
        count = [1,0]
        DFS(i)
        ans += count[0]*count[1]
ans -= N

print(ans)

Submission status: Runtime Error

Solution code:
import sys


sys.setrecursionlimit(2000)
n = int(input())
info = [list(map(int, input().split())) for i in range(n)]

v = 100000
graph = [[] for i in range(v*2)]
for i in range(n):
    x = info[i][0] - 1
    y = (info[i][1] - 1) + v
    graph[x].append(y)
    graph[y].append(x)

def dfs(pos):
    if visited[pos]:
        return
    visited[pos] = True
    if 0 <= pos < v:
        cnt[0] += 1
    else:
        cnt[1] += 1
    for i in graph[pos]:
        dfs(i)
    return

visited = [False] * (v*2)
cnt = [0]*2
ans = 0
for i in range(v*2):
    cnt[0] = 0
    cnt[1] = 0
    dfs(i)
    ans += cnt[0]*cnt[1]
print(ans - n)

Submission status: Runtime Error

Solution code:
# coding=utf-8
get = lambda: int(raw_input().strip())
gets = lambda: map(int, raw_input().strip().split())
getss = lambda n: [gets() for _ in xrange(n)]


# N = 3
# A = [[1, 1], [5, 1], [5, 5]]

# N = 2
# A = [[10, 20], [20, 20]]

N = get()
A = getss(N)
UF = {}


def find(x):
    if x != UF[x]:
        UF[x] = find(UF[x])
    return UF[x]


def union(x, y):
    UF.setdefault(x, x)
    UF.setdefault(y, y)
    UF[find(x)] = find(y)


for i, j in A:
    union(i, -j)


count = {}
for x in UF:
    root = find(x)
    if root not in count:
        count[root] = [0, 0]
    if x > 0:
        count[root][0] += 1
    else:
        count[root][1] += 1

print sum(u[0] * u[1] for u in count) - N

Submission status: Runtime Error

Solution code:
n = int(input())
dx = defaultdict(list)
dy = defaultdict(list)
pts = set()
for _ in range(n):
    x, y = map(int, input().split())
    dx[x].append(y)
    dy[y].append(x)
    pts.add((x, y))

vx, vy = set(), set()
cnt = 0
for x, y in pts:
    if x in vx or y in vy: continue
    sx, sy = [x], [y]
    xs, ys = set(), set()
    while sx or sy:
        while sx:
            x = sx.pop()
            if x not in xs:
                xs.add(x)
                for y in dx[x]:
                    if y not in ys:
                        sy.append(y)
        while sy:
            y = sy.pop()
            if y not in ys:
                ys.add(y)
                for x in dy[y]:
                    if x not in xs:
                        sx.append(x)
    vx.update(xs)
    vy.update(ys)
    cnt += len(xs) * len(ys)
print(cnt - len(pts))

Submission status: Runtime Error

Solution code:
N = int(input())

V = N + 1
to = [[] for _ in range(V * 2)]
visited = [False for _ in range(V * 2)]
cnt = []

def dfs(v):  
  L = [v]
  while len(L) > 0:
    l = L.pop(0)
    if visited[l]:
      continue
    visited[l] = True
    cnt[l // V] += 1
    for u in to[l]:
      L.append(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
  cnt = [0, 0]
  dfs(i)
  ans += cnt[0] * cnt[1]
ans -= N
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())

V = 100005
to = [[] for _ in range(V * 2)]
visited = [False for _ in range(V * 2)]
cnt = []

def dfs(v):
  if visited[v]:
    return
  visited[v] = True
  cnt[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
  cnt = [0, 0]
  dfs(i)
  ans += cnt[0] * cnt[1]
ans -= N
print(ans)

Submission status: Runtime Error

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

X = {}
Y = {}

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

count = 0
for x, y_set in X.items():
  if len(y_set) < 2:
    continue

  for y in y_set:
    x_set = Y[y]
    if len(x_set) < 2:
      continue

    for _x in x_set:
      if x == _x:
        continue

      count += len(y_set - X[_x])
      y_set |= X[_x]

print(count)

Submission status: Runtime Error

Solution code:
def f_must_be_rectangular(N, Positions):
    # 参考: https://atcoder.jp/contests/abc131/submissions/6086451
    # x軸, y軸をまとめて1つのリストで扱う
    import sys
    sys.setrecursionlimit(10**6)

    vertex_maxsize = 10**5
    target = [[] for _ in range(2 * vertex_maxsize)]
    is_visited = [False] * (2 * vertex_maxsize)
    for x, y in Positions:
        y += vertex_maxsize  # 1つのリストで扱う都合上、ずらす
        target[x].append(y)
        target[y].append(x)

    def dfs(v):
        if is_visited[v]:
            return
        is_visited[v] = True
        count[v // vertex_maxsize] += 1  # vがx軸とy軸のどっちを指しているか
        for u in target[v]:
            dfs(u)  # 頂点vに接続されている頂点へ向かう

    ans = 0
    for i in range(2 * vertex_maxsize):
        if is_visited[i]:
            continue
        count = [0] * 2
        dfs(i)  # 頂点iにつながっている頂点を調べる
        # x座標とy座標のそれぞれについて、ペアにすると矩形が完成する
        # 座標がいくつあるか。その積が解となる
        ans += count[0] * count[1]
    return ans - N  # 最初に与えられた座標の分、引く

N = int(input())
Positions = [[int(i) for i in input().split()] for j in range(N)]
print(f_must_be_rectangular(N, Positions))

Submission status: Runtime Error

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

N = int(input())
V = 100000
to = [[] for _ in range(V*2)]
visited = [False] * V * 2
ans = 0
def dfs(v):
    if (visited[v]): return
    visited[v] = True
    cnt[v//V] += 1
    [dfs(u) for u in to[v]]
for _ in range(N):
    x, y = [int(x) for x in input().split()]
    y += V
    to[x].append(y)
    to[y].append(x)
for i in range(V):
    if (visited[i]): continue
    cnt = [0, 0]
    dfs(i)
    ans += cnt[0]*cnt[1]
ans -= N
print(ans)

Submission status: Runtime Error

Solution code:
def f_must_be_rectangular(N, Positions):
    # 参考: https://atcoder.jp/contests/abc131/submissions/6086451
    # x軸, y軸をまとめて1つのリストで扱う
    import sys
    sys.setrecursionlimit(10**6)

    vertex_maxsize = 10**5
    target = [[] for _ in range(2 * vertex_maxsize)]
    is_visited = [False] * (2 * vertex_maxsize)

    for x, y in Positions:
        y += vertex_maxsize  # 1つのリストで扱う都合上、ずらす
        target[x].append(y)
        target[y].append(x)

    def dfs(v):
        if is_visited[v]:
            return
        is_visited[v] = True
        count[v // vertex_maxsize] += 1  # vがx軸かy軸かどっちを指しているか
        for u in target[v]:
            dfs(u)  # 頂点vに接続されている頂点へ向かう

    ans = 0
    for i in range(2 * vertex_maxsize):
        if is_visited[i]:
            continue
        count = [0] * 2
        dfs(i)  # 頂点iにつながっている頂点を調べる
        # x座標とy座標のそれぞれについて、ペアにすると矩形が完成する
        # 座標がいくつあるか。その積が解となる
        ans += count[0] * count[1]
    return ans - N  # 最初に与えられた座標の分、引く

N = int(input())
Positions = [[int(i) for i in input().split()] for j in range(N)]
print(f_must_be_rectangular(N, Positions))

Submission status: Runtime Error

Solution code:
N = int(input())
V = 100005
to = [[] for _ in range(V*2)]
visited = [False] * V * 2
ans = 0
def dfs(v):
    if (visited[v]): return
    visited[v] = True
    cnt[v//V] += 1
    for u in to[v]: dfs(u) 
for _ in range(N):
    x, y = [int(x) for x in input().split()]
    y += V
    to[x].append(y)
    to[y].append(x)
for i in range(V*2):
    if (visited[i]): continue
    cnt = [0, 0]
    dfs(i)
    ans += cnt[0]*cnt[1]
ans -= N
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
V = 100000
to = [[] for _ in range(V*2)]
visited = [False] * V * 2
ans = 0
def dfs(v):
    if (visited[v]): return
    visited[v] = True
    cnt[v//V] += 1
    for u in to[v]: dfs(u) 
for _ in range(N):
    x, y = [int(x) for x in input().split()]
    y += V
    to[x].append(y)
    to[y].append(x)
for i in range(V):
    if (visited[i]): continue
    cnt = [0, 0]
    dfs(i)
    ans += cnt[0]*cnt[1]
ans -= N
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())

V = 100005
to = [-1 for _ in range(V * 2)]
visited = [False for _ in range(V * 2)]
cnt = []

def dfs(v):
  if visited[v]:
    return
  visited[v] = True
  cnt[v // V] += 1
  for u in range(to[v]):
    dfs(u)

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

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))
from collections import defaultdict
class UnionFind:
    def __init__(self, N=None):
        if N is None or N < 1:
            self.parent = defaultdict(lambda: -1)
            self.children = defaultdict(list)
        else:
            self.parent = [-1]*int(N)
            self.children = [ [] for i in range(int(N)) ]

    def root(self, n):
        if self.parent[n] < 0:
            return n
        else:
            m = self.root(self.parent[n])
            self.parent[n] = m
            self.children[m].extend(self.children[n])
            self.children[n] = []
            return m

    def merge(self, m, n):
        rm = self.root(m)
        rn = self.root(n)
        if rm != rn:
            if -self.parent[rm] < -self.parent[rn]:
                rm, rn = rn, rm
            self.parent[rm] += self.parent[rn]
            self.parent[rn] = rm
            self.children[rm].append(rn)
            self.children[rm].extend(self.children[rn])
            self.children[rn] = []

    def size(self, n):
        return -self.parent[self.root(n)]
    
    def connected(self, m, n):
        return self.root(m) == self.root(n)
    
    def groups(self):
        if isinstance(self.parent,list):
            return list(map(lambda x: x<0, self.parent)).count(True)
        else: # self.parent: defaultdict
            return list(map(lambda x: x<0, self.parent.values())).count(True) 

    def collect_descendants(self, n):
        des = []
        for c in self.children[n]:
            self.collect_descendants(c)
            des.extend(self.children[c])
            self.children[c] = []
        self.children[n].extend(des)

    def all_groups(self):
        ans = []
        for r in range(N):
            if self.parent[r] >= 0:
                continue
            else:
                self.collect_descendants(r)
                ans.append( [r] + self.children[r] )
        return ans

class CountUp:
    def __init__(self, start=0):
        self.index = start-1

    def __call__(self):
        self.index += 1
        return self.index

Xi = defaultdict(CountUp())
Yi = defaultdict(CountUp())
N = int(input())
xy = []
for _ in range(N):
    x, y = inpl()
    xi = Xi[x]
    yi = Yi[y]
    xy.append((xi,yi))
Nx = len(Xi)
Ny = len(Yi)
#print(Nx,Ny)
uf = UnionFind(Nx+Ny)
for xi, yi in xy:
    uf.merge(xi,yi+Nx)
groups = uf.all_groups()
#print(uf.parent,uf.children)
#print(groups)
Ng = len(groups)
edge_nums = [0] * Ng
parents_id = dict()
for i in range(Ng):
    parents_id[groups[i][0]] = i
groups_xy = []
for g in groups:
    xs = []
    ys = []
    for k in g:
        if k < Nx:
            xs.append(k)
        else:
            ys.append(k-Nx)
    groups_xy.append([xs,ys])
for i in range(N):
    p = uf.root(xy[i][0])
    pi = parents_id[p]
    edge_nums[pi] += 1
ans = 0
for i in range(Ng):
    nx = len(list(filter(lambda s: s<Nx, groups[i])))
    ny = len(groups[i]) - nx
    ans += nx*ny - edge_nums[i]

print(ans)

Submission status: Runtime Error

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

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

print(main())

Submission status: Runtime Error

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

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

print(main())

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse import *

U = 10
N = int(input())
XY = np.array([input().split() for _ in range(N)], dtype=np.int32)

graph = csr_matrix((np.ones(N,dtype=np.bool), (XY[:,0], U + XY[:,1])), (2*U+1, 2*U+1))
_, component = csgraph.connected_components(graph)

X_cnt = np.bincount(component[:U+1], minlength = 2*U+2)
Y_cnt = np.bincount(component[U+1:], minlength = 2*U+2)
pts_cnt = np.bincount(component[XY[:,0]], minlength = 2*U+2)
answer = (X_cnt * Y_cnt - pts_cnt).sum()
print(answer)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse import *

U = 10
N = int(input())
XY = np.array([input().split() for _ in range(N)], dtype=np.int32)

graph = csr_matrix((np.ones(N,dtype=np.bool), (XY[:,0], U + XY[:,1])), (2*U+1, 2*U+1))
_, component = csgraph.connected_components(graph)

X_cnt = np.bincount(component[:U+1], minlength = U+2)
Y_cnt = np.bincount(component[U+1:], minlength = U+2)
pts_cnt = np.bincount(component[XY[:,0]], minlength = U+2)
answer = (X_cnt * Y_cnt - pts_cnt).sum()
print(answer)

Submission status: Runtime Error

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

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

print(main())