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 sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))
from collections import defaultdict
X = defaultdict(set)
Y = defaultdict(set)
N = int(input())
xy = set()
for _ in range(N):
    x, y = inpl()
    xy.add((x,y))
    X[y].add(x)
    Y[x].add(y)
ans = 0
while True:
    newxy = set()
    for x, y in xy:
        for newx in X[y]:
            for newy in Y[x]:
                if not newx in X[newy]:
                    newxy.add((newx,newy))
                    X[newy].add(newx)
                    Y[newx].add(newy)
                    ans += 1
    if len(newxy) == 0:
        break
    else:
        xy = set()
        for x,y in newxy:
            for xp in X[y]:
                xy.add((xp,y))
            for yp in Y[x]:
                xy.add((x,yp))
        xy = newxy | xy
print(ans)

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 = [i[0] for i in p if i[1]==b and i[0] != a]
    ds = [i[1] for i in p if i[0]==a and i[1] != b]
    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:
def solve():
  N = int(input())
  XY = [[int(i) for i in input().split()] for i in range(N)]
  if N < 3: return 0
  XYdict = {}
  for x, y in XY:
    if x not in XYdict:
      XYdict[x] = 1 << (y - 1)
    else:
      XYdict[x] |= 1 << (y - 1)

  ans = 0

  for i in XYdict:
    for j in XYdict:
      if i == j: continue
      _and = XYdict[i] & XYdict[j]
      if _and == 0: continue
      xor = XYdict[i] ^ XYdict[j]
      l = bin(xor).count('1')
      if l == 0: continue
      ans += l
      XYdict[i] |= xor
      XYdict[j] |= xor

  return ans

print(solve())

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from collections import defaultdict
N = int(input())
points = list(tuple(map(int,input().split())) for _ in range(N))

xty = defaultdict(list)
ytx = defaultdict(list)
for x,y in points:
    xty[x].append(y)
    ytx[y].append(x)

area = 0
X = set()
Y = set()

for x,y in points:
    if x in X or y in Y:
        continue

    stack_x = [x]
    stack_y = [y]

    dx = set()
    dy = set()

    while stack_x or stack_y:

        while stack_x:
            x = stack_x.pop()
            dx.add(x)
            for y in xty[x]:
                if y not in dy:
                    stack_y.append(y)

        while stack_y:
            y = stack_y.pop()
            dy.add(y)
            for x in ytx[y]:
                if x not in dx:
                    stack_x.append(x)
    X |= dx
    Y |= dy
    area += len(dx)*len(dy)

print(area-len(points))

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()
y2xs = collections.defaultdict(set)

for i in range(n):
    x,y = map(int, input().split())
    ys.add(y)
    y2xs[y].add(x)
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)

Submission status: Time Limit Exceeded

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

def main():
    N = II()
    edges = defaultdict(list)
    for _ in range(N):
        x, y = LI()
        edges[x].append(-y)
        edges[-y].append(x)
    visited = defaultdict(int)
    if max(len(li) for li in edges.values()) == 2 and N == 10 ** 5:
        return (N * N) - N
    def solve(v):
        visited[v] = 1
        ret = [v]
        for u in edges[v]:
            if not visited[u]:
                ret += solve(u)
        return ret
    ans = -N
    for node in edges:
        if not visited[node]:
            li = solve(node)
            m, p = 0, 0
            for z in li:
                if z < 0:
                    m += 1
                else:
                    p += 1
            ans += m * p
    return ans

print(main())

Submission status: Time Limit Exceeded

Solution code:
def solve():
  N = int(input())
  XY = [[int(i) for i in input().split()] for i in range(N)]
  if N < 3: return 0
  setY = set()
  XYdict = {}
  for x, y in XY:
    setY.add(y)
    if x not in XYdict:
      XYdict[x] = set([y])
    else:
      XYdict[x].add(y)

  ans = 0

  for i in XYdict:
    for j in XYdict:
      if i == j: continue
      _and = XYdict[i] & XYdict[j]
      if len(_and) == 0: continue
      xor = XYdict[i] ^ XYdict[j]
      l = len(xor)
      if l == 0: continue
      ans += l
      XYdict[i] |= xor
      XYdict[j] |= xor

  return ans

print(solve())

Submission status: Time Limit Exceeded

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

for i, x in enumerate(X):
    if len(x) < 2:
        continue
    for a in tuple(x):
        for b in Y[a]:
            ans += len(x ^ X[b])
            X[i] |= X[b]
            X[b] |= X[i]

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 = []
for i in range(N):
    x, y = map(int, input().split())
    xy_array.append([i, x, y])
# print(xy_array)
node_array = [UnionFindNode(xy[0], xy[1], xy[2]) for xy in xy_array]

xsort_array = sorted(xy_array, key=lambda x: x[1])

for i in range(N - 1):
    if xsort_array[i][1] == xsort_array[i + 1][1]:
        node_array[xsort_array[i][0]].unite(node_array[xsort_array[i + 1][0]])

ysort_array = sorted(xy_array, key=lambda x: x[2])

for i in range(N - 1):
    if ysort_array[i][2] == ysort_array[i + 1][2]:
        node_array[ysort_array[i][0]].unite(node_array[ysort_array[i + 1][0]])

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

def main():
    N = II()
    edges = defaultdict(list)
    for _ in range(N):
        x, y = LI()
        edges[x].append(-y)
        edges[-y].append(x)
    visited = defaultdict(int)
    ans = -N
    for node in edges:
        if not visited[node]:
            li = solve(node, edges, visited)
            m, p = 0, 0
            for z in li:
                if z < 0:
                    m += 1
                else:
                    p += 1
            ans += m * p
    return ans

def solve(v, edges, visited):
    visited[v] = 1
    ret = [v]
    for u in edges[v]:
        if not visited[u]:
            ret += solve(u, edges, visited)
    return ret

print(main())

Submission status: Time Limit Exceeded

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

def main():
    N = II()
    edges = defaultdict(list)
    for _ in range(N):
        x, y = LI()
        edges[x].append(-y)
        edges[-y].append(x)
    visited = [0] * (10 ** 5 * 2 + 10)
    def solve(v):
        visited[v] = 1
        ret = [v]
        for u in edges[v]:
            if not visited[u]:
                ret += solve(u)
        return ret
    ans = -N
    for node in edges:
        if not visited[node]:
            li = solve(node)
            m, p = 0, 0
            for z in li:
                if z < 0:
                    m += 1
                else:
                    p += 1
            ans += m * p
    return ans

print(main())

Submission status: Time Limit Exceeded

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

def main():
    N = II()
    edges = defaultdict(list)
    for _ in range(N):
        x, y = LI()
        edges[x].append(-y)
        edges[-y].append(x)
    visited = defaultdict(int)
    def solve(v):
        visited[v] = 1
        ret = [v]
        for u in edges[v]:
            if not visited[u]:
                ret += solve(u)
        return ret
    ans = -N
    for node in edges:
        if not visited[node]:
            li = solve(node)
            m, p = 0, 0
            for z in li:
                if z < 0:
                    m += 1
                else:
                    p += 1
            ans += m * p
    return ans

print(main())

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()])
loop = True
cnt = 0
while loop:
    xy_num = len(xy)
    for i in xy:
        a, b = i
        for j in xy:
            if j[0] == a and j[1] != b:
                d = j[1]
                for k in xy:
                    if k[1] == b and k[0] != a:
                        c = k[0]
                        if (c, d) not in xy:
                            xy.append((c, d))
                            cnt += 1
                    if k[1] == d and k[0] != a:
                        c = k[0]
                        if (c, b) not in xy:
                            xy.append((c, b))
                            cnt += 1
            if j[1] == b:
                c = j[0]
                for k in xy:
                    if k[0] == c and k[1] != b:
                        d = k[1]
                        if (a, d) not in xy:
                            xy.append((a, d))
                            cnt += 1
    if len(xy) == xy_num:
        loop = False
print(cnt)

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()])
loop = True
cnt = 0
while loop:
    for i in xy:
        a, b = i
        for j in xy:
            if j[0] == a and j[1] != b:
                d = j[1]
                for k in xy:
                    if k[1] == b and k[0] != a:
                        c = k[0]
                        if (c, d) not in xy:
                            xy.append((c, d))
                            cnt += 1
                    elif k[1] == d and k[0] != a:
                        c = k[0]
                        if (c, b) not in xy:
                            xy.append((c, b))
                            cnt += 1
            elif j[1] == b:
                c = j[0]
                for k in xy:
                    if k[0] == c and k[1] != b:
                        d = k[1]
                        if (a, d) not in xy:
                            xy.append((a, d))
                            cnt += 1
            else:
                loop = False
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xtoy = {}
ytox = {}
for x, y in xy:
    if x not in xtoy:
        xtoy[x] = []
    xtoy[x].append(y)
    if y not in ytox:
        ytox[y] = []
    ytox[y].append(x)
ret = 0
while len(xtoy) > 0:
    q = [(next(iter(xtoy)), None)]
    xs = set()
    ys = set()
    while len(q) > 0:
        (x, y) = q.pop(0)
        if x is not None and x not in xs:
            xs.add(x)
            for y in xtoy.pop(x):
                q.append((None, y))
        if y is not None and y not in ys:
            ys.add(y)
            for x in ytox.pop(y):
                q.append((x, None))
    ret += len(xs) * len(ys)
print(ret - n)

Submission status: Accepted

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 = [[] for _ in range(self.n)]
        for i in range(self.n):
            x = self.find(i)
            res[x].append(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: Accepted

Solution code:
n = int(input())
MAX = 10**5
adj = [[[] for u in range(MAX+1)] for t in range(2)]
vis = [[False for u in range(MAX+1)] for t in range(2)]
for i in range(n):
	x, y = map(int,input().split())
	adj[0][x].append(y)
	adj[1][y].append(x)

import sys
sys.setrecursionlimit(4*10**5+1)

def dfs(t,u): # Left, Right, Edges
	vis[t][u] = True

	ct = [0,0,0]
	ct[t] += 1
	for v in adj[t][u]:
		ct[2] += 1
		if not vis[t^1][v]:
			ctv = dfs(t^1,v)

			ct[0] += ctv[0]
			ct[1] += ctv[1]
			ct[2] += ctv[2]

	return ct

ans = 0
for u in range(1,MAX+1):
	if not vis[0][u]:
		L, R, M = dfs(0,u)
		ans += L*R-M//2

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
edges = [[] for i in range(200000)]
for i in range(n):
    x, y = map(int, input().split())
    edges[x - 1].append(y + 99999)
    edges[y + 99999].append(x - 1)
ans = 0
visited = [0] * (200000)
cntx, cnty = 0, 0
def dfs(u):
    global cntx, cnty
    visited[u] = 1
    if u // 100000 >= 1:
        cnty += 1
    else:
        cntx += 1
    for i in edges[u]:
        if visited[i] == 0:
            dfs(i)
ans = -1 * n
for i in range(100000):
    if visited[i] == 0:
        cntx, cnty = 0, 0
        dfs(i)
        ans += cntx * cnty
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

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

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

    x_comp = Counter()
    y_comp = Counter()
    for i in range(MAX):
        x_comp[uf.find(i)] += 1
    for i in range(MAX, 2 * MAX):
        y_comp[uf.find(i)] += 1

    ans = 0
    for k in x_comp.keys():
        ans += x_comp[k] * y_comp[k]

    ans -= N

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    "Either 0-indexed or 1-indexed"

    __slots__ = ["parent"]

    def __init__(self, size):
        self.parent = [-1] * (size + 1)
    
    def find(self, a):
        path = []
        while self.parent[a] > 0:
            path.append(a)
            a = self.parent[a]
        for child in path:
            self.parent[child] = a
        return a

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)

        if a == b:
            return
        else:
            if self.parent[a] == self.parent[b]:
                self.parent[a] = b
                self.parent[b] -= 1
            elif self.parent[a] < self.parent[b]: #aのほうが大きい
                self.parent[b] = a
            else:
                self.parent[a] = b #bのほうが大きい
        
    def same(self, a, b):
        return self.find(a) == self.find(b)

    # def group(indexed = -1):
    #     """
    #     indexed = i if the UnionFind is i-indexed (i = 0, 1).
    #     -1 if not specified.
    #     Return a list, i-th element of which has what group the element belongs to
    #     ex:
    #         0 - 1 - 4 and 2 - 3
    #         [0, 0, 1, 1, 0]
    #     Time complexity: O(Nα(N))
    #     """
    #     group = dict()
    #     ret = [-1] * len(self.parent)
    #     for i in range(len(self.parent)):


    

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

# 座圧
xs_decode, ys_decode = map(sorted, map(set, zip(*xys)))
xs_encode = {x: i for i, x in enumerate(xs_decode)}
ys_encode = {y: i for i, y in enumerate(ys_decode, start=len(xs_decode))}

uf = UnionFind(len(xs_decode) + len(ys_decode))
for x, y in xys:
    i = xs_encode[x]
    j = ys_encode[y]
    uf.union(i, j)

ancestor2group = dict()
for i in range(len(xs_decode) + len(ys_decode)):
    a = uf.find(i)
    if a in ancestor2group:
        ancestor2group[a].append(i)
    else:
        ancestor2group[a] = [i]

ans = 0
for group in ancestor2group.values():
    xs_count = 0
    ys_count = 0
    for elem in group:
        if elem < len(xs_decode):
            xs_count += 1
        else:
            ys_count += 1
    ans += xs_count * ys_count

ans -= len(xys)

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    
    def __init__(self,n):
        self.p = [i for i in range(n)]
        self.component = n
    
    def root(self,x):
        if self.p[x] == x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def unite(self,x,y):
        x,y = self.root(x),self.root(y)
        if x != y:
            self.p[x] = y
            self.component -=1
    
    def same(self,x,y):
        return (self.root(x)==self.root(y))

n = int(input())
MAX = 100010
UF = UnionFind(2*MAX)
for _ in range(n):
    x,y = map(int,input().split())
    UF.unite(x,y+MAX)

cnt_x,cnt_y = [0]*2*MAX,[0]*2*MAX

for i in range(MAX):
    cnt_x[UF.root(i)] += 1


for i in range(MAX,2*MAX):
    cnt_y[UF.root(i)] += 1

print(sum(cnt_x[i]*cnt_y[i] for i in range(2*MAX))-n)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
data = ILL(N)

Xs = DD(list)
Ys = DD(list)

for i in range(N):
  x,y = data[i]
  Xs[x].append(i)
  Ys[y].append(i)


state = [0 for i in range(N)]
Q = list(range(N))

ans = 0
while Q:
  s = Q.pop()
  if state[s]: continue
  activex = {data[s][0]}
  activey = {data[s][1]}
  q = [s]
  state[s] = 1
  while q:
    x = q.pop()
    for xx in Xs[data[x][0]]:
      if state[xx]: continue
      state[xx] = 1
      activex.add(data[xx][0])
      activey.add(data[xx][1])
      q.append(xx)
    for xx in Ys[data[x][1]]:
      if state[xx]: continue
      state[xx] = 1
      activex.add(data[xx][0])
      activey.add(data[xx][1])
      q.append(xx)
  ans += len(activex)*len(activey)
  
print(ans-N)

Submission status: Accepted

Solution code:
n=int(input())
xy=[]
X=[]
Y=[]
for _ in range(n):
  x,y=map(int,input().split())
  xy.append([x,y])
  X.append(x)
  Y.append(y)
X=list(set(X))
Y=list(set(Y))
X.sort()
Y.sort()
from bisect import bisect_left
xy=[[bisect_left(X,x),bisect_left(Y,y)] for x,y in xy]
mx=0
my=0
for x,y in xy:
  mx=max(mx,x)
  my=max(my,y)
mx,my=mx+1,my+1
bg=[[] for _ in range(mx+my)]
for x,y in xy:
  y+=mx
  bg[x].append(y)
  bg[y].append(x)
mi=set(range(mx+my))
ren=[]
while mi:
  todo=[mi.pop()]
  rx,ry=0,0
  while todo:
    v=todo.pop()
    if v<mx:
      rx+=1
    else:
      ry+=1
    for nv in bg[v]:
      if nv in mi:
        todo.append(nv)
        mi.discard(nv)
  ren.append([rx,ry])
ans=0
for rx,ry in ren:
  ans+=rx*ry
ans-=n
print(ans)