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

Submission status: Time Limit Exceeded

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

N = int(input())
XY = [[set() for i in range(10**5+1)] for j in range(2)]
is_visited_x = [True] * (10**5 + 1)
for i in range(N):
  x, y = map(int, input().split())
  is_visited_x[x] = False
  XY[0][x].add(y)
  XY[1][y].add(x)


def dfs(x):
  global is_visited_x
  is_visited_x[x] = True
  stack = [[x], []]
  idx = 0
  num_e = 0
  num_xy = [1, 0]
  parent = 0
  while stack[0] or stack[1]:
    node = stack[idx][-1]
    children = XY[idx][node]
    if children:
      child = children.pop()
      XY[idx-1][child].remove(node) # 今来た道を削除
      num_e += 1
      if child in stack[idx-1]:
        continue
      stack[idx-1].append(child)
      num_xy[idx-1] += 1
      is_visited_x[child] += idx
      idx = (idx + 1) % 2
    else:
      stack[idx].pop()
      idx = (idx + 1) % 2
  return num_e, num_xy

ans = 0
for x in range(1, 10**5+1):
  if is_visited_x[x]:
    continue
  num_e, num_xy = dfs(x)
  ans += num_xy[0]*num_xy[1] - num_e

print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
XY = [[set() for i in range(10**5+1)] for j in range(2)]
for i in range(N):
  x, y = map(int, input().split())
  XY[0][x].add(y)
  XY[1][y].add(x)

is_visited_x = [False] * (10**5 + 1)
def dfs(x):
  global is_visited_x
  is_visited_x[x] = True
  stack = [[x], []]
  idx = 0
  num_e = 0
  num_xy = [1, 0]
  parent = 0
  while stack[0] or stack[1]:
    node = stack[idx][-1]
    children = XY[idx][node]
    if children:
      child = children.pop()
      XY[idx-1][child].remove(node) # 今来た道を削除
      num_e += 1
      if child in stack[idx-1]:
        continue
      stack[idx-1].append(child)
      num_xy[idx-1] += 1
      is_visited_x[child] += idx
      idx = (idx + 1) % 2
    else:
      stack[idx].pop()
      idx = (idx + 1) % 2
  return num_e, num_xy

ans = 0
for x in range(1, 10**5+1):
  if is_visited_x[x]:
    continue
  num_e, num_xy = dfs(x)
  ans += num_xy[0]*num_xy[1] - num_e

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

XY = [[set() for i in range(10**5+1)] for j in range(2)]
for i in range(N):
  x, y = map(int, input().split())
  XY[0][x].add(y)
  XY[1][y].add(x)

is_visited_x = [False] * (10**5 + 1)
def dfs(x):
  global is_visited_x
  is_visited_x[x] = True
  stack = [[x], []]
  idx = 0
  num_e = 0
  num_xy = [1, 0]
  parent = 0
  while stack[0] or stack[1]:
    node = stack[idx][-1]
    children = XY[idx][node]
    if children:
      child = children.pop()
      XY[idx-1][child].remove(node) # 今来た道を削除
      num_e += 1
      if child in stack[idx-1]:
        continue
      stack[idx-1].append(child)
      num_xy[idx-1] += 1
      is_visited_x[child] += idx
      idx = (idx + 1) % 2
    else:
      stack[idx].pop()
      idx = (idx + 1) % 2
  return num_e, num_xy

ans = 0
for x in range(1, 10**5+1):
  if is_visited_x[x]:
    continue
  num_e, num_xy = dfs(x)
  ans += num_xy[0]*num_xy[1] - num_e

print(ans)

Submission status: Time Limit Exceeded

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

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

MAX = 10**5
Xs = [[] for _ in range(MAX+1)]
Ys = [[] for _ in range(MAX+1)]
for i, (x, y) in enumerate(XY):
    Xs[x].append(i)
    Ys[y].append(i)

ans = 0
checked = [False]*N
for i in range(N):
    if checked[i]: continue
    q = [i]
    checked[i] = True
    X = set()
    Y = set()
    c = 0
    while q:
        qq = []
        for p in q:
            x, y = XY[p]
            X.add(x)
            Y.add(y)
            c += 1
            for ni in Xs[x]:
                if not checked[ni]:
                    checked[ni] = True
                    qq.append(ni)
            for ni in Ys[y]:
                if not checked[ni]:
                    checked[ni] = True
                    qq.append(ni)
        q = qq
    ans += len(X)*len(Y)-c

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    V=100005
    n=int(input())
    E=[[] for _ in range(V*2)]
    for _ in range(n):
        x,y=map(int,input().split())
        y+=V
        E[x].append(y)
        E[y].append(x)

    visited=[0]*(2*V)
    def dfs(v):
        if(visited[v]): return
        visited[v]=1
        cnt[v//V]+=1
        for nv in E[v]: dfs(nv)

    ans=[0]
    for v in range(2*V):
        if(visited[v]): continue
        cnt=[0]*2 # 連結成分のx,yの個数
        dfs(v)
        ans[0]+=cnt[0]*cnt[1]
    print(ans[0]-n)
resolve()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

ans -= n
print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

ans -= n
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
xy=[]
for i in range(N):
  xy.append(list(map(int, input().split())))

xdict=dict()
ydict=dict()

for i in range(N):
  xdict[xy[i][0]]=[]
  ydict[xy[i][1]]=[]
for i in range(N):
  xdict[xy[i][0]].append(xy[i][1])
  ydict[xy[i][1]].append(xy[i][0])

activex=dict()
activex_next=dict()
for i in range(N):
  activex[xy[i][0]]=1

activey=dict()
activey_next=dict()
for i in range(N):
  activey[xy[i][1]]=0

  
judge=1  
num=0
times=0
while judge==1:
  judge=0
  for i in range(N):
    activex_next[xy[i][0]]=0
    activey_next[xy[i][1]]=0
  for x, ylist in xdict.items():
    if times==0 or activex[x]==1: #1
      if len(ylist)>=2: #[1,2,3,4,5]
        for y in ylist: #2
          if times==0 or activey[y]==1: #1
            xlist=ydict[y] #[1]
            for targetx in xlist: #1
              for targety in ylist: #[1,2,3,4,5]
                if not targety in xdict[targetx]:
                  xdict[targetx].append(targety)
                  ydict[targety].append(targetx)
                  judge=1
                  num+=1
                  activex_next[targetx]=1
                  activey_next[targety]=1
  times+=1
                  
  activex=activex_next.copy() 
  activey=activey_next.copy() 
print(num)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
xy=[]
for i in range(N):
  xy.append(list(map(int, input().split())))

xdict=dict()
ydict=dict()

for i in range(N):
  xdict[xy[i][0]]=[]
  ydict[xy[i][1]]=[]
for i in range(N):
  xdict[xy[i][0]].append(xy[i][1])
  ydict[xy[i][1]].append(xy[i][0])

activex=dict()
activex_next=dict()
for i in range(N):
  activex[xy[i][0]]=1

  
judge=1  
num=0
times=0
while judge==1:
  judge=0
  for i in range(N):
    activex_next[xy[i][0]]=0
  for x, ylist in xdict.items():
    if times==0 and activex[x]==1: #1
      if len(ylist)>=2: #[1,2,3,4,5]
        for y in ylist: #2
          xlist=ydict[y] #[1]
          for targetx in xlist: #1
            for targety in ylist: #[1,2,3,4,5]
              if not targety in xdict[targetx]:
                xdict[targetx].append(targety)
                ydict[targety].append(targetx)
                judge=1
                num+=1
                activex_next[targetx]=1
  activex=activex_next.copy() 
print(num)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
xy=[]
for i in range(N):
  xy.append(list(map(int, input().split())))

xdict=dict()
ydict=dict()

for i in range(N):
  xdict[xy[i][0]]=[]
  ydict[xy[i][1]]=[]
for i in range(N):
  xdict[xy[i][0]].append(xy[i][1])
  ydict[xy[i][1]].append(xy[i][0])

activex=dict()
activex_next=dict()
for i in range(N):
  activex[xy[i][0]]=1

  
judge=1  
num=0
times=0
while judge==1:
  judge=0
  for i in range(N):
    activex_next[xy[i][0]]=0
  for x, ylist in xdict.items():
    if times==0 or activex[x]==1: #1
      if len(ylist)>=2: #[1,2,3,4,5]
        for y in ylist: #2
          xlist=ydict[y] #[1]
          for targetx in xlist: #1
            for targety in ylist: #[1,2,3,4,5]
              if not targety in xdict[targetx]:
                xdict[targetx].append(targety)
                ydict[targety].append(targetx)
                judge=1
                num+=1
                activex_next[targetx]=1
  activex=activex_next.copy()
              
print(num)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
xy=[]
for i in range(N):
  xy.append(list(map(int, input().split())))

xdict=dict()
ydict=dict()

for i in range(N):
  xdict[xy[i][0]]=[]
  ydict[xy[i][1]]=[]
for i in range(N):
  xdict[xy[i][0]].append(xy[i][1])
  ydict[xy[i][1]].append(xy[i][0])

judge=1  
num=0
while judge==1:
  judge=0
  for x, ylist in xdict.items(): #1
    if len(ylist)>=2: #[1,2,3,4,5]
      for y in ylist: #2
        xlist=ydict[y] #[1]
        for targetx in xlist: #1
          for targety in ylist: #[1,2,3,4,5]
            if not targety in xdict[targetx]:
              xdict[targetx].append(targety)
              ydict[targety].append(targetx)
              judge=1
              num+=1
         
              
print(num)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xy = [0] * n
for i in range(n):
    xy[i] = tuple([int(j) for j in input().split()])
xy.sort(key=lambda x: (x[0], x[1]))

cnt = 0
for i in xy:
    for j in xy:
        if xy.index(i) >= xy.index(j) or i[0] == j[0] or i[1] == j[1]:
            continue
        a, b, c, d = i[0], i[1], j[0], j[1]
        if (a, d) in xy:
            if (c, b) in xy:
                continue
            else:
                xy.append((c, b))
                xy.sort(key=lambda x: (x[0], x[1]))
                cnt += 1
        if (c, b) in xy:
            if (a, d) in xy:
                continue
            else:
                xy.append((a, d))
                xy.sort(key=lambda x: (x[0], x[1]))
                cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def append_p(p, xpeers_s, ypeers_s):
  x = p[X]
  if not x in xpeers_s:
    xpeers_s[x] = []
  xpeers_s[x].append(p)

  y = p[Y]
  if not y in ypeers_s:
    ypeers_s[y] = []
  ypeers_s[y].append(p)
  
  
X = 0
Y = 1
n = int(input())
p_set = set(tuple(int(v) for v in input().split()) for _ in range(n))
xpeers_s = {}
ypeers_s = {}
for p in p_set:
  append_p(p, xpeers_s, ypeers_s)

#print(p_set)
#print(xpeers_s)
#print(ypeers_s)
#print("")
ans = 0

search_targets = p_set
while True:
  repeat = False
  p_set_new = set()
  for p in search_targets:
    x = p[X]
    y = p[Y]
    if (x in xpeers_s) and (y in ypeers_s):
      xpeers = xpeers_s[x]
      ypeers = ypeers_s[y]
      #print(xpeers, ypeers)
      for xpeer in xpeers:
        for ypeer in ypeers:
          dpeer = (ypeer[X], xpeer[Y])
          #print(xpeer, ypeer)
          if dpeer not in (p_set|p_set_new):
            ans += 1
            repeat = True
            p_set_new.add(dpeer)
            
  #print("repeat={}, ans={}".format(repeat, ans))
  p_set |= p_set_new
  search_targets = set()
  x_set = set()
  y_set = set()
  for p_new in p_set_new:
    #print(p_new)
    append_p(p_new, xpeers_s, ypeers_s)
    x_set.add(p_new[X])
    y_set.add(p_new[Y])
  for x in x_set:
    search_targets |= set(xpeers_s[x])
    search_targets |= set(ypeers_s[y])
    
  if not repeat:
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def append_p(p, xpeers_s, ypeers_s):
  x = p[X]
  if not x in xpeers_s:
    xpeers_s[x] = []
  xpeers_s[x].append(p)

  y = p[Y]
  if not y in ypeers_s:
    ypeers_s[y] = []
  ypeers_s[y].append(p)
  
  
X = 0
Y = 1
n = int(input())
p_set = set(tuple(int(v) for v in input().split()) for _ in range(n))
xpeers_s = {}
ypeers_s = {}
for p in p_set:
  append_p(p, xpeers_s, ypeers_s)

#print(p_set)
#print(xpeers_s)
#print(ypeers_s)
#print("")
ans = 0
for _rep in range(10):
#while True:
  repeat = False
  p_set_new = set()
  for p in p_set:
    x = p[X]
    y = p[Y]
    if (x in xpeers_s) and (y in ypeers_s):
      xpeers = xpeers_s[x]
      ypeers = ypeers_s[y]
      #print(xpeers, ypeers)
      for xpeer in xpeers:
        for ypeer in ypeers:
          dpeer = (ypeer[X], xpeer[Y])
          #print(xpeer, ypeer)
          if dpeer not in (p_set|p_set_new):
            ans += 1
            repeat = True
            p_set_new.add(dpeer)
            
  #print("repeat={}, ans={}".format(repeat, ans))
  p_set |= p_set_new
  for p_new in p_set_new:
    #print(p_new)
    append_p(p_new, xpeers_s, ypeers_s)
  if not repeat:
    break
print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

main()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


class Group:
    
    def __init__(self, x, y):
        self.n = 1
        self.x = {x: None}
        self.y = {y: None}
        
    def insertx(self, x):
        self.x[x] = None
        self.n += 1

    def inserty(self, y):
        self.y[y] = None
        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
        for x in group.x:
            self.x[x] = None
        for y in group.y:
            self.y[y] = None
        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:
                group1.n += 1
                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)
            else:
                yg[yi] = group1
                group1.inserty(yi)
        elif yi in yg:
            group = yg[yi]
            xg[xi] = group
            group.insertx(xi)
        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: Time Limit Exceeded

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


class Group:
    
    def __init__(self, x, y):
        self.n = 1
        self.x = {x: None}
        self.y = {y: None}
        
    def insertx(self, x):
        self.x[x] = None
        self.n += 1

    def inserty(self, y):
        self.y[y] = None
        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
        for x in group.x:
            self.x[x] = None
        for y in group.y:
            self.y[y] = None
        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:
                    group1.n += 1
                    pass
                else:
                    for xk in group2.x:
                        xg[xk] = group1
                    for yk in group2.y:
                        yg[yk] = group1
                    group1.join(group2)
                    group1.n += 1
            else:
                yg[yi] = group1
                group1.inserty(yi)
        elif yi in yg:
            group = yg[yi]
            xg[xi] = group
            group.insertx(xi)
        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: Time Limit Exceeded

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


class Group:
    
    def __init__(self, x, y):
        self.n = 1
        self.x = {x: None}
        self.y = {y: None}
        
    def insert(self, x, y):
        self.x[x] = None
        self.y[y] = None
        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
        for x in group.x:
            self.x[x] = None
        for y in group.y:
            self.y[y] = None
        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: Time Limit Exceeded

Solution code:
N = int(input())
points = []
for i in range(0, N):
    points.append(list(map(int, input().split(' '))))
abcd = set(sum(points, []))
count = 0
for a in abcd:
    for b in abcd:
        for c in abcd:
            for d in abcd:
                if a == c and b == d:
                    continue
                p = []
                if [a, b] not in points:
                    p.append([a, b])
                if [a, d] not in points:
                    p.append([a, d])
                if [c, b] not in points:
                    p.append([c, b])
                if [c, d] not in points:
                    p.append([c, d])
                if len(p) == 1:
                    count += 1
                    points.append(p[0])
print(count)

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):
    cnt = [0,0]
    dfs(i)
    ans = ans + cnt[0]*cnt[1]

print(ans-n)

Submission status: Time Limit Exceeded

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


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:
            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: 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 = [cs.pop()]
        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()