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

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

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


def read_int():
    return int(input())


def read_int_n():
    return tuple(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, XY):
    g = [[] for _ in range((10**5)*2)]
    offset = 10**5
    cs = set()
    for x, y in XY:
        x -= 1
        y = y - 1 + offset
        g[x].append(y)
        g[y].append(x)
        cs.add(x)
        cs.add(y)
    ans = 0
    while cs:
        q = [x]
        done = set()
        while q:
            v = q.pop()
            for u in g[v]:
                if v >= offset:
                    e = (u, v)
                else:
                    e = (v, u)
                if e not in done:
                    q.append(u)
                    done.add(e)
        xn = set()
        yn = set()
        for v, u in done:
            for z in (v, u):
                if z >= offset:
                    yn.add(z)
                else:
                    xn.add(z)
        ans += (len(xn) * len(yn)) - len(done)
        for v, u in done:
            if u in cs:
                cs.remove(u)
            if v in cs:
                cs.remove(v)

    return ans

def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    print(slv(N, XY))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-



class UnionFind():
  def __init__(self):
    self.group = []
  
  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[j] = [set(),set(),0]

  def new(self,x,y):
    merge_i = -1
    for i in range(len(self.group)):
      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.extend([[{x},{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 min([x,y]) >= 2:
        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: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-



class UnionFind():
  def __init__(self):
    self.group = []
  
  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,r = [0,len(self.group)]
    while l < r:
      if x in self.group[l][0] or y in self.group[l][1]:
        if merge_i >= 0:
          self.merge(merge_i,l)
          l -= 1
          r -= 1
        else:
          self.group[l][0].add(x)
          self.group[l][1].add(y)
          self.group[l][2] += 1
          merge_i = l
      l += 1
    if merge_i < 0:
      self.group.append([{x},{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 min([x,y]) >= 2:
        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: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(200010)
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
    cnt[pos//v] += 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: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(200010)
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: Time Limit Exceeded

Solution code:
import sys


sys.setrecursionlimit(200010)
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: Time Limit Exceeded

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 x1, y_set1 in X.items():
  if len(y_set1) < 2: continue

  for y in y_set1:
    for x2 in Y[y]:
      if x2 == x1: continue
      count += len(y_set1 - X[x2])
      X[x2] |= y_set1

print(count)

Submission status: Time Limit Exceeded

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

V = 100005
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 xy in XY:
  x, y = xy[0], xy[1]
  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: Time Limit Exceeded

Solution code:
N = int(input())

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

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

N = int(input())
V = 100005
to = [set() 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].add(y)
    to[y].add(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: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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()
  X[x].add(y)
  if y not in Y: Y[y] = set()
  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])
      X[_x] = y_set | X[_x]

print(count)

Submission status: Time Limit Exceeded

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

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

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

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

ans = 0

used = [False] * (10 ** 5 + 1)

def dfs(x):
    if used[x]:
        return set()
    used[x] = True

    res = set(X[x])

    for y in X[x]:
        for a in Y[y]:
            res |= dfs(a)

    return res

used2 = [False] * (10 ** 5 + 1)

def dfs2(S, x):
    if used2[x]:
        return 0
    used2[x] = True

    res = 0
    
    for y in X[x]:
        for a in Y[y]:
            res += dfs2(S, a)

    return res + len(S - X[x])


for i, x in enumerate(X):
    if len(x) < 2:
        continue
    S = dfs(i)
    ans += dfs2(S, i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

class Bag:
    def __init__(self):
        self.points = set()
        self.x = set()
        self.y = set()

    def __or__(self, other):
        self.points |= other.points
        self.x |= other.x
        self.y |= other.y
        return self

    def add_points(self, x, y):
        self.points.add((x, y))
        self.x.add(x)
        self.y.add(y)

bags = []
N = int(input())
for i in range(N):
    x, y = list(map(int, input().split()))
    used_bags = []
    new_bags = []
    for bag in bags:
        if x in bag.x or y in bag.y:
            used_bags.append(bag)
        else:
            new_bags.append(bag)
    initial_bag = Bag()
    for bag in used_bags:
        initial_bag |= bag
    initial_bag.add_points(x, y)
    new_bags.append(initial_bag)
    bags = new_bags

result = 0
for bag in bags:
    result += len(bag.x) * len(bag.y) - len(bag.points)
print(result)

Submission status: Time Limit Exceeded

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()
  X[x].add(y)
  if y not in Y: Y[y] = set()
  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

      _y_set =  X[_x]
      for _y in y_set:
        if _y not in _y_set:
          _y_set.add(_y)
          count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:

p = [[int(i) for i in input().split()] for _ in range(int(input()))]
count = 0
for i in p:
    a,b = i
    cs, ds = [],[]
    for i in p:
        if i[1]==b and i[0] != a:
            cs.append(i[0])
        if i[0]==a and i[1] != b:
            ds.append(i[1])
    if not cs or not ds:
        continue
    for c in cs:
        for d in ds:
            if not [c,d] in p:
                p.append([c, d])
                count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
ri = lambda: int(input())
#rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rl = lambda: map(int,input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7

N = ri()
X = [set() for i in range(10**5+1)]
Y = [set() for i in range(10**5+1)]
X_set = set()
Y_set = set()
for i in range(N):
    x,y=rl()
    X[x].add(y)
    Y[y].add(x)
    X_set.add(x)
    Y_set.add(y)

from collections import deque
sX = deque([-1])
sX.extend(list(X_set))
sY = deque([-1])
sY.extend(list(Y_set))
ans = 0


while True:
    sx = sX.pop()
    #print(sx,sX,cnt)
    if sx == -1:
        sX.appendleft(-1)
        break
    if len(X[sx]) >= 2:
        sx_Y = set()
        sx_Y_in = set()
        for y in X[sx]:
            sx_Y = sx_Y | Y[y]
        sx_Y_in = sx_Y_in | sx_Y 
        for y in X[sx]:
            sx_Y_in = sx_Y_in & Y[y]
            Y_dif = sx_Y - Y[y]
            for ssx in Y_dif:
                ans += 1
                X[ssx].add(y)
                Y[y].add(ssx)
        #print(ans,X[sx],sx_Y,sx_Y_in)
        if len(sx_Y - sx_Y_in) > 0:
            sX.extend(sx_Y - sx_Y_in)

while True:
    sy = sY.pop()
    #print(sy,sY,cnt)
    if sy == -1:
        sY.appendleft(-1)
        break
    if len(Y[sy]) >= 2:
        sy_X = set()
        sy_X_in = set()
        for x in Y[sy]:
            sy_X = sy_X | X[x]
        sy_X_in = sy_X_in | sy_X 
        for x in Y[sy]:
            sy_X_in = sy_X_in & X[x]
            X_dif = sy_X - X[x]
            for ssy in X_dif:
                ans += 1
                Y[ssy].add(x)
                X[x].add(ssy)
        #print(ans,Y[sy],sy_X,sy_X_in)
        if len(sy_X - sy_X_in) > 0:
            sY.extend(sy_X - sy_X_in)
while True:
    sx = sX.pop()
    #print(sx,sX,cnt)
    if sx == -1:
        sX.appendleft(-1)
        break
    if len(X[sx]) >= 2:
        sx_Y = set()
        sx_Y_in = set()
        for y in X[sx]:
            sx_Y = sx_Y | Y[y]
        sx_Y_in = sx_Y_in | sx_Y 
        for y in X[sx]:
            sx_Y_in = sx_Y_in & Y[y]
            Y_dif = sx_Y - Y[y]
            for ssx in Y_dif:
                ans += 1
                X[ssx].add(y)
                Y[y].add(ssx)
        #print(ans,X[sx],sx_Y,sx_Y_in)
        if len(sx_Y - sx_Y_in) > 0:
            sX.extend(sx_Y - sx_Y_in)

while True:
    sy = sY.pop()
    #print(sy,sY,cnt)
    if sy == -1:
        sY.appendleft(-1)
        break
    if len(Y[sy]) >= 2:
        sy_X = set()
        sy_X_in = set()
        for x in Y[sy]:
            sy_X = sy_X | X[x]
        sy_X_in = sy_X_in | sy_X 
        for x in Y[sy]:
            sy_X_in = sy_X_in & X[x]
            X_dif = sy_X - X[x]
            for ssy in X_dif:
                ans += 1
                Y[ssy].add(x)
                X[x].add(ssy)
        #print(ans,Y[sy],sy_X,sy_X_in)
        if len(sy_X - sy_X_in) > 0:
            sY.extend(sy_X - sy_X_in)
while True:
    sx = sX.pop()
    #print(sx,sX,cnt)
    if sx == -1:
        sX.appendleft(-1)
        break
    if len(X[sx]) >= 2:
        sx_Y = set()
        sx_Y_in = set()
        for y in X[sx]:
            sx_Y = sx_Y | Y[y]
        sx_Y_in = sx_Y_in | sx_Y 
        for y in X[sx]:
            sx_Y_in = sx_Y_in & Y[y]
            Y_dif = sx_Y - Y[y]
            for ssx in Y_dif:
                ans += 1
                X[ssx].add(y)
                Y[y].add(ssx)
        #print(ans,X[sx],sx_Y,sx_Y_in)
        if len(sx_Y - sx_Y_in) > 0:
            sX.extend(sx_Y - sx_Y_in)

while True:
    sy = sY.pop()
    #print(sy,sY,cnt)
    if sy == -1:
        sY.appendleft(-1)
        break
    if len(Y[sy]) >= 2:
        sy_X = set()
        sy_X_in = set()
        for x in Y[sy]:
            sy_X = sy_X | X[x]
        sy_X_in = sy_X_in | sy_X 
        for x in Y[sy]:
            sy_X_in = sy_X_in & X[x]
            X_dif = sy_X - X[x]
            for ssy in X_dif:
                ans += 1
                Y[ssy].add(x)
                X[x].add(ssy)
        #print(ans,Y[sy],sy_X,sy_X_in)
        if len(sy_X - sy_X_in) > 0:
            sY.extend(sy_X - sy_X_in)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections


class UnionFind:

    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.size = size
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        # 集合の代表を求める
        cs = []
        while self.table[x] >= 0:
            cs.append(x)
            x = self.table[x]
        for c in cs:
            self.table[c] = x
        return x

    def union(self, x, y):
        # 併合
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] >= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
        return self.table[s1]


n = int(input())
ys = set()
xs = set()
y2xs = collections.defaultdict(set)
x2ys = collections.defaultdict(set)

for i in range(n):
    x, y = map(int, input().split())
    ys.add(y)
    y2xs[y].add(x)
    xs.add(x)
    x2ys[x].add(y)



if len(xs) < len(ys):
    ys = xs
    y2xs = x2ys

ys = sorted(list(ys))
y_cnt = [len(y2xs[y]) for y in ys]
y_size = len(ys)
y_used = [False] * y_size

total = 0


uf = UnionFind(y_size)
for i in range(y_size - 1):
    for j in range(i + 1, y_size):
        if not y2xs[ys[uf.find(i)]].isdisjoint(y2xs[ys[uf.find(j)]]):
            if not y_used[i]:
                total -= len(y2xs[ys[i]])
                y_used[i] = True
            if not y_used[j]:
                total -= len(y2xs[ys[j]])
                y_used[j] = True

            new_set = y2xs[ys[uf.find(i)]] | y2xs[ys[uf.find(j)]]
            uf.union(i, j)
            y2xs[ys[uf.find(i)]] = new_set

for i in range(y_size):
    if y_used[uf.find(i)]:
        total += len(y2xs[ys[uf.find(i)]])

print(total)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import math


n = int(stdin.readline().rstrip())

m = []

for i in range(n):
    x, y = [int(x) for x in stdin.readline().rstrip().split()]
    m.append((x,y))

m.sort()
#print(m)

ans=0

for x,y in m:
  for x2,y2 in [(x2,y2) for x2,y2 in m if x2==x and y < y2]:
    for x3,y3 in [(x3,y3) for x3,y3 in m if y==y3]:
      if not (x3,y2) in m:
          ans +=1
          m.append((x3,y2))
    for x4,y4 in [(x4,y4) for x4,y4 in m if y2==y4]:
      if not (x4,y) in m:
          ans +=1
          m.append((x4,y))

print(ans)

Submission status: Time Limit Exceeded

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


class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, x, y, parent=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.size_ = 1
        self.rank_ = 1
        self.x_ = {x}
        self.y_ = {y}

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, size: {}, rank: {}, x: {}, y: {})"
        return template.format(self.group_id_, self.parent_, self.size_,
                               self.rank_, self.x_, self.y_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def get_size(self):
        root = self.root()
        return root.size_

    def get_count(self):
        root = self.root()
        if len(root.x_) == 1 or len(root.y_) == 1:
            return 0
        return len(root.x_) * len(root.y_) - root.size_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
                root.size_ += unite_root.size_
                root.x_ = root.x_ | unite_root.x_
                root.y_ = root.y_ | unite_root.y_
            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                unite_root.size_ += root.size_
                unite_root.x_ = root.x_ | unite_root.x_
                unite_root.y_ = root.y_ | unite_root.y_


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

# print(xy_array)
node_array = [UnionFindNode(i, xy[0], xy[1]) for i, xy in enumerate(xy_array)]

for i in range(N):
    for j in range(i, N):
        if xy_array[i][0] == xy_array[j][0] or xy_array[i][1] == xy_array[j][1]:
            node_array[i].unite(node_array[j])

# print("\n".join(list(map(str, node_array))))
# print("\n".join(list(map(lambda x: str(x.root()), node_array))))

ans = 0
for node in node_array:
    if node.is_root():
        # print("root")
        ans += node.get_count()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, x_zahyou, y_zahyou,parent=None, value=None):
        self.group_id_ = group_id
        self.x_zahyou = x_zahyou
        self.y_zahyou = y_zahyou
        self.parent_ = parent
        self.value = value
        self.rank_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.rank_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
                root.x_zahyou += unite_root.x_zahyou
                root.y_zahyou += unite_root.y_zahyou
            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                unite_root.x_zahyou+= root.x_zahyou 
                unite_root.y_zahyou+= root.y_zahyou
                
N = int(input())
X = []
Y = []
node_list = []
for i in range(N):
  x, y = map(int,input().split())
  X += [[i,x]]
  Y += [[i,y]]
  node_list += [UnionFind(i,[x],[y])]
X.sort(key=lambda x: x[1])
Y.sort(key=lambda x: x[1])
for i in range(N-1):
  if X[i][1] == X[i+1][1] :
    node_list[X[i][0]].unite(node_list[X[i+1][0]])
  if Y[i][1] == Y[i+1][1] :
    node_list[Y[i][0]].unite(node_list[Y[i+1][0]])
    
chouten = 0
for i in range(N):
  if node_list[i].is_root():
    chouten += len(set(node_list[i].x_zahyou)) * len(set(node_list[i].y_zahyou))
    
print(chouten - N)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, x_zahyou, y_zahyou,parent=None, value=None):
        self.group_id_ = group_id
        self.x_zahyou = x_zahyou
        self.y_zahyou = y_zahyou
        self.parent_ = parent
        self.value = value
        self.rank_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.rank_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        root = self.root()
        return root.group_id_

    def rank(self):
        root = self.root()
        return root.rank_

    def unite(self, unite_node):
        root = self.root()
        unite_root = unite_node.root()

        if root.group_id_ != unite_root.group_id_:
            if root.rank() > unite_root.rank():
                unite_root.parent_ = root
                root.rank_ = max(root.rank_, unite_root.rank_ + 1)
                root.x_zahyou= root.x_zahyou | unite_root.x_zahyou
                root.y_zahyou= root.y_zahyou | unite_root.y_zahyou
            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                unite_root.x_zahyou= root.x_zahyou | unite_root.x_zahyou
                unite_root.y_zahyou= root.y_zahyou | unite_root.y_zahyou
                
N = int(input())
X = []
Y = []
node_list = []
for i in range(N):
  x, y = map(int,input().split())
  X += [[i,x]]
  Y += [[i,y]]
  node_list += [UnionFind(i,set([x]),set([y]))]
X.sort(key=lambda x: x[1])
Y.sort(key=lambda x: x[1])
for i in range(N-1):
  if X[i][1] == X[i+1][1] :
    node_list[X[i][0]].unite(node_list[X[i+1][0]])
  if Y[i][1] == Y[i+1][1] :
    node_list[Y[i][0]].unite(node_list[Y[i+1][0]])
    
chouten = 0
for i in range(N):
  if node_list[i].is_root():
    chouten += len(node_list[i].x_zahyou) * len(node_list[i].y_zahyou)
    
print(chouten - N)

Submission status: Time Limit Exceeded

Solution code:
import collections

class UnionFind:

    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.size = size
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        # 集合の代表を求める
        cs = []
        while self.table[x] >= 0:
            cs.append(x)
            x = self.table[x]
        for c in cs:
            self.table[c] = x
        return x

    def union(self, x, y):
        # 併合
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] >= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
        return self.table[s1]



n = int(input())
ys = set()
xs = set()
y2xs = collections.defaultdict(set)
x2ys = collections.defaultdict(set)

for i in range(n):
    x,y = map(int, input().split())
    ys.add(y)
    y2xs[y].add(x)
    xs.add(x)
    x2ys[x].add(y)

if len(xs) < len(ys):
    ys= xs
    y2xs = x2ys

ys = sorted(list(ys))
y_cnt = [len(y2xs[y]) for y in ys]
y_size = len(ys)
y_used = [False] * y_size

total = 0


uf = UnionFind(y_size)
for i in range(y_size-1):
    for j in range(i+1, y_size):
        if y2xs[ys[uf.find(i)]] & y2xs[ys[uf.find(j)]]:
            if not y_used[i]:
                total -= len(y2xs[ys[i]])
                y_used[i] = True
            if not y_used[j]:
                total -= len(y2xs[ys[j]])
                y_used[j] = True
            
            new_set = y2xs[ys[uf.find(i)]] | y2xs[ys[uf.find(j)]]
            uf.union(i, j)
            y2xs[ys[uf.find(i)]] = new_set

for i in range(y_size):
    if y_used[uf.find(i)]:
        total += len(y2xs[ys[uf.find(i)]])

print(total)