Problem:


Score : 600 points

Problem Statement

There are N dots in a two-dimensional plane. The coordinates of the i-th dot are (x_i, y_i).

We will repeat the following operation as long as possible:

Choose four integers a, b, c, d (a \neq c, b \neq d) such that there are dots at exactly three of the positions (a, b), (a, d), (c, b) and (c, d), and add a dot at the remaining position.

We can prove that we can only do this operation a finite number of times. Find the maximum number of times we can do the operation.

Constraints

1 \leq N \leq 10^5

1 \leq x_i, y_i \leq 10^5

If i \neq j, x_i \neq x_j or y_i \neq y_j.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print the maximum number of times we can do the operation.

Sample Input 1

3
1 1
5 1
5 5

Sample Output 1

1

By choosing a = 1, b = 1, c = 5, d = 5, we can add a dot at (1, 5). We cannot do the operation any more, so the maximum number of operations is 1.

Sample Input 2

2
10 10
20 20

Sample Output 2

0

There are only two dots, so we cannot do the operation at all.

Sample Input 3

9
1 1
2 1
3 1
4 1
5 1
1 2
1 3
1 4
1 5

Sample Output 3

16

We can do the operation for all choices of the form a = 1, b = 1, c = i, d = j (2 \leq i,j \leq 5), and no more. Thus, the maximum number of operations is 16.



Sample input:
3
1 1
5 1
5 5


Sample output:
1

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

N = int(input())

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

x_set = set()
y_set = set()

for point in point_list:
    x_set.add(point[0])
    y_set.add(point[1])

x_points = len(x_set)
y_points = len(y_set)
preset_points = len(point_list)

if (x_points - 1) * (y_points - 1) == 0:
    print(0)
elif preset_points <= 2:
    print(0)
else:
    print(x_points * y_points - preset_points)

Submission status: Wrong Answer

Solution code:
n = int(input())
E = [[int(i) for i in input().split()] for j in range(n)]

X = [[] for i in range(10 ** 5 + 1)]
Y = [[] for i in range(10 ** 5 + 1)]

for x, y in E:
    X[x].append(y)
    Y[y].append(x)

ans = 0

for x in X:
    if len(x) < 2:
        continue
    for a in x:
        if Y[a]:
            ans += len(x) - len(Y[a])

print(ans)

Submission status: Wrong Answer

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())

def Find(x):    #xの根を返す
    global table

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

def Unite(x,y):    #xとyを繋げる
    global size
    global rank
    x = Find(x)
    y = Find(y)
    sx = Size(x)
    sy = Size(y)

    if x == y:
        return

    if rank[x] > rank[y]:
        table[y] = x
        size[x] = sx + sy
    else:
        table[x] = y
        size[y] = sx + sy
        if rank[x] == rank[y]:
            rank[y] += 1

def Check(x,y):
    if Find(x) == Find(y):
        return True
    else:
        return False

def Size(x):
    return size[Find(x)]

table = [i for i in range(10**5+1)]    #木の親 table[x] == x なら根
rank  = [1 for i in range(10**5+1)]    #木の長さ
size  = [1 for i in range(10**5+1)]    #集合のサイズ


N = int(input())
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 Check(s,t):
            Unite(s,t)

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

print(ans)

Submission status: Time Limit Exceeded

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

    def find(self, x):
        """ 根を見つける関数を定義（同時にxを直接根にくっつける操作も行う）"""
        tmp = []
        parents = self.parents
        while parents[x] >= 0:
            tmp.append(x)
            x = parents[x]
        for y in tmp:
            parents[y] = x
        return 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 same(self, x, y):
        """ xとyが同じ根の子かを判定 """
        return self.find(x) == self.find(y)

    def size(self, x):
        """ x の根の parent（= 要素数）を返す """
        return -self.parents[self.find(x)]

    def members(self, x):
        """ xが属するグループの要素をリストとして返す O(N)"""
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """ 全ての根の要素をリストとして返す O(N)"""
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """ グループの数を返す O(1)"""
        return len(self.roots())

    def size_list(self):
        """ 各グループの要素数のリストを返す(根の番号は返さない) O(N)"""
        return [-x for x in self.parents if x < 0]

    def all_group_members(self):
        """ {根:[根の子(根を含む)のリスト],...}を辞書で返す """
        res = dict()
        for i in range(self.n):
            x = self.find(i)
            res[x] = res.get(x,[]) + [i]
        return {r: res[r] for r in self.roots()}

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


##############################################################################################################
import sys
input = sys.stdin.readline


N = int(input())
U = UnionFind(2*N)
P = [[] for _ in range(N)]
code1, code2 = {}, {}
for i in range(N):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    if a not in code1:
        code1[a]=i
    if b not in code2:
        code2[b]=i+N
    U.union(code1[a],code2[b])
res = 0
for a in U.all_group_members().values():
    x, y = 0, 0
    for b in a:
        if b<N: x += 1
        else: y += 1
    res += x*y
print(res-N)

Submission status: Time Limit Exceeded

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

    def find(self, x):
        """ 根を見つける関数を定義（同時にxを直接根にくっつける操作も行う）"""
        tmp = []
        parents = self.parents
        while parents[x] >= 0:
            tmp.append(x)
            x = parents[x]
        for y in tmp:
            parents[y] = x
        return 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 same(self, x, y):
        """ xとyが同じ根の子かを判定 """
        return self.find(x) == self.find(y)

    def size(self, x):
        """ x の根の parent（= 要素数）を返す """
        return -self.parents[self.find(x)]

    def members(self, x):
        """ 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())

    def size_list(self):
        """ 各グループの要素数のリストを返す(根の番号は返さない) """
        return [-x for x in self.parents if x < 0]

    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())


##############################################################################################################
import sys
input = sys.stdin.readline


N = int(input())
U = UnionFind(2*N)
P = [[] for _ in range(N)]
code1, code2 = {}, {}
for i in range(N):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    if a not in code1:
        code1[a]=i
    if b not in code2:
        code2[b]=i+N
    U.union(code1[a],code2[b])
res = 0
for a in U.all_group_members().values():
    x, y = 0, 0
    for b in a:
        if b<N: x += 1
        else: y += 1
    res += x*y
print(res-N)

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


class UnionFind:
    # Reference: https://note.nkmk.me/python-union-find/
    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 same(self, x, y):
        return self.find(x) == self.find(y)

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

    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())

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


def main():
    N, *XY = map(int, read().split())

    P = [(x, y) for x, y in zip(*[iter(XY)] * 2)]
    uf = UnionFind(N)

    Q = [(x, y, i) for i, (x, y) in enumerate(P)]

    Q.sort()
    for j in range(N - 1):
        if Q[j][0] == Q[j + 1][0]:
            uf.union(Q[j][2], Q[j + 1][2])

    Q.sort(key=itemgetter(1))
    for j in range(N - 1):
        if Q[j][1] == Q[j + 1][1]:
            uf.union(Q[j][2], Q[j + 1][2])

    ans = 0
    for vec in uf.all_group_members().values():
        x_points = len(set(P[i][0] for i in vec))
        y_points = len(set(P[i][1] for i in vec))
        ans += x_points * y_points - len(vec)

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

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])
    
    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 = [set() for i in range(n+1)]
    for i in range(1, n+1):
        member[union.find(i)].add(i)
    
    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: Time Limit Exceeded

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])
    
    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])
    
    ans = 0
    already = [False]*(n+1)
    for i in range(1, n+1):
        if already[i]:
            continue
        table = union.members(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: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readlines = sys.stdin.buffer.readlines
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)


def main():
    OFS = 100005
    N = int(input())
    G = [[] for _ in [0]*OFS*2]
    for line in readlines():
        x, y = map(int, line.split())
        y += OFS
        G[x].append(y)
        G[y].append(x)

    def dfs(v):
        if v < OFS:
            counter[0] += 1
        else:
            counter[1] += 1

        for u in G[v]:
            if visited[u]:
                continue
            visited[u] = 1
            dfs(u)

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

    print(ans - N)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readlines = sys.stdin.buffer.readlines
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)

OFS = 100005
N = int(input())
G = [[] for _ in [0]*OFS*2]
for line in readlines():
    x, y = map(int, line.split())
    y += OFS
    G[x].append(y)
    G[y].append(x)

visited = [0]*OFS*2


def dfs(v, x=0, y=0):
    if v < OFS:
        x += 1
    else:
        y += 1

    for u in G[v]:
        if visited[u]:
            continue
        visited[u] = 1
        x, y = dfs(u, x, y)

    return x, y


ans = 0
for i in range(OFS):
    if visited[i]:
        continue
    visited[i] = 1
    x, y = dfs(i)
    ans += x*y

print(ans - N)

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N = ri()
to = defaultdict(list)
V = 100005
X = []
for i in range(N):
	x, y = rl()
	X.append(x)
	y += V
	to[x].append(y)
	to[y].append(x)

visited = set()
nx, ny = 0, 0
def dfs(n):
	global nx, ny
	if n in visited: return
	visited.add(n)
	if n < V:
		nx += 1
	else:
		ny += 1
	for m in to[n]:
		dfs(m)

ans = 0
for x in X:
	if x in visited: continue
	nx, ny = 0, 0
	dfs(x)
	ans += nx*ny
print(ans-N)

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N = ri()
to = defaultdict(list)
V = 100005
X = []
for i in range(N):
	x, y = rl()
	X.append(x)
	y += V
	to[x].append(y)
	to[y].append(x)

visited = set()
nums = [0, 0]
def dfs(n):
	if n in visited: return
	visited.add(n)
	if n < V:
		nums[0] += 1
	else:
		nums[1] += 1
	for m in to[n]:
		dfs(m)

ans = 0
for x in X:
	nums[0] = 0
	nums[1] = 0
	dfs(x)
	ans += nums[0]*nums[1]
print(ans-N)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def solve(points):
    N = len(points)
    X = defaultdict(list)
    Y = defaultdict(list)

    for i,(x,y) in enumerate(points):
        X[x].append(i)
        Y[y].append(i)
    
    res = 0
    visited = [False]*N
    for p0 in range(N):
        if visited[p0]:
            continue
        stack = [p0]
        visited[p0] = True
        xx = set()
        yy = set()
        while stack:
            p = stack.pop()
            x,y = points[p]
            xx.add(x)
            yy.add(y)

            for q in X[x]:
                if not visited[q]:
                    visited[q] = True
                    stack.append(q)
            for q in Y[y]:
                if not visited[q]:
                    visited[q] = True
                    stack.append(q)
        res += len(xx)*len(yy)
    return res-N




if __name__ == '__main__':
    N = int(input())
    points = [tuple(map(int,input().split())) for _ in range(N)]
    print(solve(points))

Submission status: Time Limit Exceeded

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

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: Time Limit Exceeded

Solution code:
from networkx import*
def main():
    g=Graph()
    for a in[*open(0)][1:]:
        a,b=map(int,a.split())
        g.add_edge(a,b+.5)
    x=0
    for c in connected_components(g):
        s=g.subgraph(c)
        a,b=map(len,bipartite.sets(s))
        x+=a*b-s.size()
    print(x)
main()

Submission status: Time Limit Exceeded

Solution code:
from networkx import*
def main():
    g=Graph()
    for a in[*open(x:=0)][1:]:
        a,b=map(int,a.split())
        g.add_edge(a,b+.5)
    for c in connected_components(g):
        s=g.subgraph(c)
        a,b=map(len,bipartite.sets(s))
        x+=a*b-s.size()
    print(x)
main()

Submission status: Time Limit Exceeded

Solution code:
from networkx import*
def main():
    g=Graph()
    for a in[*open(x:=0)][1:]:
        a,b=map(int,a.split())
        g.add_edge(a,b+.5)
    for c in connected_components(g):
        a,b=map(len,bipartite.sets(s:=g.subgraph(c)))
        x+=a*b-s.size()
    print(x)
main()

Submission status: Time Limit Exceeded

Solution code:
from networkx import*
def main():
    g=Graph()
    for a in[*open(x:=0)][1:]:
        a,b=map(int,a.split())
        g.add_edge(a,7**6+b)
    for c in connected_components(g):
        a,b=map(len,algorithms.bipartite.sets(s:=g.subgraph(c)))
        x+=a*b-s.size()
    print(x)
main()

Submission status: Time Limit Exceeded

Solution code:
from networkx import*
def main():
    g=Graph()
    for a in[*open(x:=0)][1:]:
        a,b=map(int,a.split())
        g.add_edge(a,7**6+b)
    for c in connected_components(g):
        a,b=map(len,algorithms.bipartite.sets(s:=g.subgraph(c)))
        x+=a*b-len(s.edges)
    print(x)
main()

Submission status: Time Limit Exceeded

Solution code:
from networkx import*
def main():
    g=Graph()
    for a in[*open(x:=0)][1:]:
        a,b=map(int,a.split())
        g.add_edge(a,7**6+b)
    for c in connected_components(g):
        a,b=map(len,bipartite.sets(s:=g.subgraph(c)))
        x+=a*b-len(s.edges)
    print(x)
main()

Submission status: Time Limit Exceeded

Solution code:
from networkx import*
g=Graph()
for a in[*open(x:=0)][1:]:
  a,b=map(int,a.split())
  g.add_edge(a,7**6+b)
for c in connected_components(g):
  a,b=map(len,bipartite.sets(s:=g.subgraph(c)))
  x+=a*b-len(s.edges)
print(x)

Submission status: Time Limit Exceeded

Solution code:
from networkx import*
g=Graph()
for a,b in[*map(str.split,open(x:=0))][1:]:g.add_edge(a,'y'+b)
for c in connected_components(g):a,b=map(len,bipartite.sets(s:=g.subgraph(c)));x+=a*b-len(s.edges)
print(x)

Submission status: Time Limit Exceeded

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)
    # print(dx, dy)
    # print(dx_inv, dy_inv)
    # print(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)
        # print(queue)
        x, y = queue[head]
        head += 1
        samex = X2Y[x]          # これはxが同じ節点のy座標の集合
        samey = Y2X[y]          # これはyが同じ節点のx座標の集合
        # 全ての組み合わせを追加
        additive = []
        for nx in samey:
            if nx == x:
                continue
            nys = samex-X2Y[nx]
            additive.extend([(nx, ny) for ny in nys])
            cnt += len(nys)
            X2Y[nx] |= nys
            # print(nys)
            for ny in nys:
                Y2X[ny].add(nx)
    print(cnt)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n = int(input())
v = 10**5+2
e = [[] for i in range(2*v)]
for i in range(n):
    x,y = map(int,input().split())
    y += v
    e[x].append(y)
    e[y].append(x)
visit = [0]*(2*v)
def dfs(x):
    if not visit[x]:
        visit[x] = 1
        count[x//v] += 1
        for nex in e[x]:
            dfs(nex)
ans = 0
for i in range(v):
    if not visit[i]:
        count = [0]*2
        dfs(i)
        ans += count[0]*count[1]
print(ans-n)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def main():
    N = int(input())
    V = 10 ** 5 + 5
    edge = [[] * (2 * V) for _ in range(2 * V)]
    visited = [False] * (2 * V)
    for i in range(N):
        x, y = map(int, input().split())
        y += V
        edge[x].append(y)
        edge[y].append(x)

    def dfs(i):
        if visited[i]:
            return
        visited[i] = True
        cnt[i//V] += 1
        for j in edge[i]:
            dfs(j)
    ans = 0
    for i in range(2 * V):
        if visited[i]:
            continue
        cnt = [0,0]
        dfs(i)
        ans += cnt[0] * cnt[1]

    print(ans - N)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
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: Time Limit Exceeded

Solution code:
import bisect
import heapq
import sys
import queue


input = sys.stdin.readline
sys.setrecursionlimit(100000)


class V:
    def __init__(self, f):
        self.f = f
        self.v = None

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n)

    def get(self):
        return self.v


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def f(x, X, VX):
    visit_node = [set(), set()]
    visit_link = set()

    q = queue.Queue()
    q.put((0, x))
    while not q.empty():
        ps = q.get()
        if ps in visit_node:
            continue

        p, s = ps
        visit_node[p].add(s)
        VX[p][s] = True
        for t in X[p][s]:
            l = (s, t) if p == 0 else (t, s)
            if l in visit_link:
                continue
            visit_link.add(l)

            if t in visit_node[1 - p]:
                continue
            q.put((1 - p, t))

    return len(visit_node[0]) * len(visit_node[1]) - len(visit_link)


def main():
    N = int(input())
    X = {}
    Y = {}

    for _ in range(N):
        x, y = read_values()
        x -= 1
        y -= 1
        X.setdefault(x, set()).add(y)
        Y.setdefault(y, set()).add(x)

    VX = [False] * (10 ** 5)
    VY = [False] * (10 ** 5)

    res = 0
    for x in X.keys():
        if VX[x]:
            continue

        if len(X[x]) < 2:
            continue

        res += f(x, [X, Y], [VX, VY])

    for y in Y.keys():
        if VY[y]:
            continue

        if len(Y[y]) < 2:
            continue

        res += f(y, [Y, X], [VY, VX])

    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import heapq
import sys
import queue


input = sys.stdin.readline
sys.setrecursionlimit(100000)


class V:
    def __init__(self, f):
        self.f = f
        self.v = None

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n)

    def get(self):
        return self.v


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def f(x, X, VX):
    visit_node = [set(), set()]
    visit_link = set()

    q = queue.Queue()
    q.put((0, x))
    while not q.empty():
        ps = q.get()
        if ps in visit_node:
            continue

        p, s = ps
        visit_node[p].add(s)
        VX[p][s] = True
        for t in X[p][s]:
            l = (s, t) if p == 0 else (t, s)
            if l in visit_link:
                continue
            visit_link.add(l)

            if t in visit_node[1 - p]:
                continue
            q.put((1 - p, t))

    return len(visit_node[0]) * len(visit_node[1]) - len(visit_link)


def main():
    N = int(input())
    X = {}
    Y = {}

    for _ in range(N):
        x, y = read_values()
        x -= 1
        y -= 1
        X.setdefault(x, set()).add(y)
        Y.setdefault(y, set()).add(x)

    VX = [False] * (10 ** 5)
    VY = [False] * (10 ** 5)

    res = 0
    for x in X.keys():
        if VX[x]:
            continue

        res += f(x, [X, Y], [VX, VY])

    for y in Y.keys():
        if VY[y]:
            continue

        res += f(y, [Y, X], [VY, VX])

    print(res)


if __name__ == "__main__":
    main()