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: Accepted

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

def find_root(root, size, x):
    y = root[x]
    if y is None:
        root[x] = x
        size[x] = 1
        return x
    if x == y:
        return y
    z = find_root(root, size, y)
    root[x] = z
    return z


def merge(root, size, cnt, x, y):
    rx = find_root(root, size, x)
    ry = find_root(root, size, y)
    if rx == ry:
        return
    sx = size[rx]
    sy = size[ry]
    if sx > sy:
        root[ry] = rx
        size[rx] += sy
        cnt[rx] += cnt[ry]
    else:
        root[rx] = ry
        size[ry] += sx
        cnt[ry] += cnt[rx]
    return


def main():
    N = int(input())
    U = 10 ** 5
    root_x = [None] * (U + 1)
    root_y = [None] * (U + 1)
    size_x = [0] * (U + 1)
    size_y = [0] * (U + 1)
    cnt_x = [0] * (U + 1)
    cnt_y = [0] * (U + 1)
    x_to_y = [None] * (U + 1)
    y_to_x = [None] * (U + 1)

    for _ in range(N):
        x, y = map(int, input().split())
        rx = find_root(root_x, size_x, x)
        ry = find_root(root_y, size_y, y)
        cnt_x[rx] += 1
        cnt_y[ry] += 1
        if x_to_y[rx] is None:
            x_to_y[rx] = ry
        if y_to_x[ry] is None:
            y_to_x[ry] = rx
        merge(root_y, size_y, cnt_y, x_to_y[rx], ry)
        merge(root_x, size_x, cnt_x, y_to_x[ry], rx)
        x_to_y[root_x[rx]] = root_y[ry]
        y_to_x[root_y[ry]] = root_x[rx]

    ans = 0
    for x in range(1, U + 1):
        if root_x[x] is None:
            continue
        rx = find_root(root_x, size_x, x)
        if x != rx:
            continue
        y = x_to_y[x]
        ry = find_root(root_y, size_y, y)
        sx = size_x[rx]
        sy = size_y[ry]
        cnt = cnt_x[rx]
        ans += sx * sy - cnt
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = S()
    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            print("Bad")
            quit()
    print("Good")
    return

#B
def B():
    n,l = LI()
    a = [i+l for i in range(n)]
    ans = sum(a)
    m = n+l-1
    for i in a[::-1]:
        if i < 0:break
        m = min(m,i)
    ans -= m
    print(ans)
    return

#C
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
def C():
    a,b,c,d = LI()
    g = gcd(c,d)
    l = c*d//g
    sc = b//c-(a-1)//c
    sd = b//d-(a-1)//d
    sl = b//l-(a-1)//l
    print(b-a+1-sc-sd+sl)
    return

#D
def D():
    n = I()
    w = LIR(n)
    w.sort(key = lambda x: x[1])
    t = 0
    for a,b in w:
        if t+a > b:
            print("No")
            quit()
        t += a
    print("Yes")
    return

#E
def E():
    n,k = LI()
    if k == 0:
        m = (n*(n-1))//2
        print(m)
        for i in range(1,n+1):
            for j in range(i+1,n+1):
                print(i,j)
    else:
        if k > ((n-1)*(n-2))//2:
            print(-1)
        else:
            ans = []
            for i in range(2,n+1):
                ans.append((1,i))
            m = ((n-1)*(n-2))//2
            for i in range(2,n+1):
                for j in range(i+1,n+1):
                    if m == k:break
                    ans.append((i,j))
                    m -= 1
                if m == k:break
            print(len(ans))
            for i,j in ans:
                print(i,j)
    return

#F
def F():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]
    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    n = I()
    v = defaultdict(list)
    h = defaultdict(list)
    par = defaultdict(int)
    rank = defaultdict(int)
    for i in range(n):
        a,b = LI()
        v[a].append(b)
        h[b].append(a)
        par[a] = a
        rank[a] = 0
    h = h.values()
    for l in h:
        for i in range(len(l)-1):
            x = l[i]
            y = l[i+1]
            if root(x) != root(y):
                unite(x,y)
    h = defaultdict(list)
    for i in par.keys():
        par[i] = root(par[i])
        h[par[i]].append(i)
    h = h.values()
    ans = 0
    for k in h:
        f = defaultdict(lambda : 0)
        m = 0
        for i in k:
            for j in v[i]:
                if not f[j]:
                    m += 1
                    f[j] = 1
        for i in k:
            ans += m-len(v[i])
    print(ans)
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Accepted

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

def find_root(root, size, x):
    y = root[x]
    if y is None:
        root[x] = x
        size[x] = 1
        return x
    if x == y:
        return y
    z = find_root(root, size, y)
    root[x] = z
    return z


def merge(root, size, cnt, x, y):
    rx = find_root(root, size, x)
    ry = find_root(root, size, y)
    if rx == ry:
        return
    sx = size[rx]
    sy = size[ry]
    if sx > sy:
        root[ry] = rx
        size[rx] += sy
        cnt[rx] += cnt[ry]
    else:
        root[rx] = ry
        size[ry] += sx
        cnt[ry] += cnt[rx]
    return


def main():
    N = int(input())
    U = 10 ** 5
    root_x = [None] * (U + 1)
    root_y = [None] * (U + 1)
    size_x = [0] * (U + 1)
    size_y = [0] * (U + 1)
    cnt_x = [0] * (U + 1)
    cnt_y = [0] * (U + 1)
    x_to_y = [None] * (U + 1)
    y_to_x = [None] * (U + 1)

    for _ in range(N):
        x, y = map(int, input().split())
        rx = find_root(root_x, size_x, x)
        ry = find_root(root_y, size_y, y)
        cnt_x[rx] += 1
        cnt_y[ry] += 1
        if x_to_y[rx] is None:
            x_to_y[rx] = ry
        if y_to_x[ry] is None:
            y_to_x[ry] = rx
        merge(root_y, size_y, cnt_y, x_to_y[rx], ry)
        merge(root_x, size_x, cnt_x, y_to_x[ry], rx)
        x_to_y[root_x[rx]] = root_y[ry]
        y_to_x[root_y[ry]] = root_x[rx]

    ans = 0
    for x in range(1, U + 1):
        if root_x[x] is None:
            continue
        rx = find_root(root_x, size_x, x)
        if x != rx:
            continue
        y = x_to_y[x]
        ry = find_root(root_y, size_y, y)
        sx = size_x[rx]
        sy = size_y[ry]
        cnt = cnt_x[rx]
        ans += sx * sy - cnt
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = S()
    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            print("Bad")
            quit()
    print("Good")
    return

#B
def B():
    n,l = LI()
    a = [i+l for i in range(n)]
    ans = sum(a)
    m = n+l-1
    for i in a[::-1]:
        if i < 0:break
        m = min(m,i)
    ans -= m
    print(ans)
    return

#C
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
def C():
    a,b,c,d = LI()
    g = gcd(c,d)
    l = c*d//g
    sc = b//c-(a-1)//c
    sd = b//d-(a-1)//d
    sl = b//l-(a-1)//l
    print(b-a+1-sc-sd+sl)
    return

#D
def D():
    n = I()
    w = LIR(n)
    w.sort(key = lambda x: x[1])
    t = 0
    for a,b in w:
        if t+a > b:
            print("No")
            quit()
        t += a
    print("Yes")
    return

#E
def E():
    n,k = LI()
    if k == 0:
        m = (n*(n-1))//2
        print(m)
        for i in range(1,n+1):
            for j in range(i+1,n+1):
                print(i,j)
    else:
        if k > ((n-1)*(n-2))//2:
            print(-1)
        else:
            ans = []
            for i in range(2,n+1):
                ans.append((1,i))
            m = ((n-1)*(n-2))//2
            for i in range(2,n+1):
                for j in range(i+1,n+1):
                    if m == k:break
                    ans.append((i,j))
                    m -= 1
                if m == k:break
            print(len(ans))
            for i,j in ans:
                print(i,j)
    return

#F
def F():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]
    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    n = I()
    v = defaultdict(list)
    h = defaultdict(list)
    par = defaultdict(int)
    rank = defaultdict(int)
    for i in range(n):
        a,b = LI()
        v[a].append(b)
        h[b].append(a)
        par[a] = a
        rank[a] = 0
    h = h.values()
    for l in h:
        for i in range(len(l)-1):
            x = l[i]
            y = l[i+1]
            if root(x) != root(y):
                unite(x,y)
    h = defaultdict(list)
    for i in par.keys():
        par[i] = root(par[i])
        h[par[i]].append(i)
    h = h.values()
    ans = 0
    for k in h:
        f = defaultdict(lambda : 0)
        l = []
        m = 0
        for i in k:
            for j in v[i]:
                if not f[j]:
                    m += 1
                    f[j] = 1
        for i in k:
            ans += m-len(v[i])
    print(ans)
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Accepted

Solution code:
# 再帰関数の呼び出し回数が多くなる時はこれが必要！！無いとruntime errorになる。
import sys
sys.setrecursionlimit(100000+10)

# 木の深さ優先探索
def add_edge(u, v):
	G[u].append(v)
	G[v].append(u)

def dfs(vertex, x_set, y_set):

	global visited

	if visited[vertex]:
		#探索済み
		return 0
	visited[vertex] = True

	x_set.add(coords[vertex][1])
	y_set.add(coords[vertex][2])
	for v in G[vertex]:
		if visited[v]:
			#探索済み
			pass
		else:
			dfs(v, x_set, y_set)

	return len(x_set)*len(y_set)

n = int(input())

G = [[] for _ in range(n)] #グラフの隣接リスト表現

visited = [False] * n
now_index = n-1

coords = [ [i] + list(map(int, input().split())) for i in range(n)]

from operator import itemgetter

# xでソート
coords_xs = sorted(coords, key = itemgetter(1))
for i in range(n-1):
	if coords_xs[i][1] == coords_xs[i+1][1]: 
		# 隣接 coords_xs[i][0] coords_xs[i+1][0]
		add_edge(coords_xs[i][0], coords_xs[i+1][0])

# yでソート
coords_ys = sorted (coords, key = itemgetter(2))
for i in range(n-1):
	if coords_ys[i][2] == coords_ys[i+1][2]: 
		# 隣接 coords_ys[i][0] coords_ys[i+1][0]
		add_edge(coords_ys[i][0], coords_ys[i+1][0])

# 深さ優先探索
final = 0
for i in range(n):
	x_set = {coords[i][1]} #set
	y_set = {coords[i][2]}
	final += dfs(i, x_set, y_set)

print(final - n)
# print(coords)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
N = int(input())
K = 10**5+1
P = [i for i in range(K)]

def par(a):
    if P[a] == a:
        return a
    t = par(P[a])
    P[a] = t
    return t
def cb(a, b):
    P[par(b)] = par(a)

X = [[] for _ in range(K)]
Y = [[] for _ in range(K)]
for _ in range(N):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    Y[y-1].append(x-1)
for i in range(K):
    for j in range(len(Y[i])-1):
        cb(Y[i][j], Y[i][j+1])

M = [[] for _ in range(K)]
for i in range(K):
    M[par(i)].append(i)
ans = -N
for i in range(K):
    S = []
    for j in M[i]:
        for k in X[j]:
            S.append(k)
    S = list(set(S))
    ans += len(S)*len(M[i])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
U = 10 ** 5
root = [None] * (2*U+1)
N = int(input())
XY = [[int(x) for x in input().split()] for _ in range(N)]

def find_root(x):
  y = root[x]
  if y is None:
    root[x] = x
    return x
  if x == y:
    return y
  z = find_root(y)
  root[x] = z
  return z

def merge(x,y):
  rx = find_root(x)
  ry = find_root(y)
  if rx == ry:
    return
  root[ry] = rx
  return

for x,y in XY:
  merge(x,U+y)

pts_cnt = defaultdict(int)
x_cnt = defaultdict(int)
y_cnt = defaultdict(int)

for x in range(U+1):
  if root[x] is None:
    continue
  x_cnt[find_root(x)] += 1

for y in range(U+1,U+U+1):
  if root[y] is None:
    continue
  y_cnt[find_root(y)] += 1

for x,y in XY:
  pts_cnt[find_root(x)] += 1

answer = 0
for k,v in pts_cnt.items():
  answer += x_cnt[k] * y_cnt[k] - v

print(answer)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import defaultdict
class UnionFind:
    def __init__(self,n):
        self.par=[i for i in range(n)]
        self.rank=[0]*n
    def find(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1
    def same_check(self,x,y):
        return self.find(x)==self.find(y)

n=int(input())
uf=UnionFind(n)
XY=[tuple(map(int,input().split())) for _ in range(n)]
Xd=defaultdict(list)
Yd=defaultdict(list)
for i,(x,y) in enumerate(XY):
    Xd[x].append(i)
    Yd[y].append(i)
for x in Xd:
    i=Xd[x][0]
    for j in Xd[x]:
        uf.union(i,j)
for y in Yd:
    i=Yd[y][0]
    for j in Yd[y]:
        uf.union(i,j)
d=defaultdict(list)
for i in range(n):
    d[uf.find(i)].append(i)
ans=0
for k in d:
    Xs,Ys=set(),set()
    for i in d[k]:
        x,y=XY[i]
        Xs.add(x); Ys.add(y)
    ans+=len(Xs)*len(Ys)
ans-=n
print(ans)

Submission status: Accepted

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

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, size: {}, rank: {})"
        return template.format(self.group_id_, self.parent_, self.size_,
                               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 get_size(self):
        root = self.root()
        return 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_

            else:
                root.parent_ = unite_root
                unite_root.rank_ = max(root.rank_ + 1, unite_root.rank_)
                unite_root.size_ += root.size_


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

xy_group = [[set(), set()] for i in range(N)]
for node, xy in zip(node_array, xy_array):
    group = node.find()
    xy_group[group][0].add(xy[1])
    xy_group[group][1].add(xy[2])

ans = 0
for i, xy in enumerate(xy_group):
    if len(xy[0]) <= 1 or len(xy[1]) <= 1:
        continue
    ans += len(xy[0]) * len(xy[1]) - node_array[i].get_size()

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
N = int(input())
K = 10**5+1
P = [i for i in range(K)]

def par(a):
    if P[a] == a:
        return a
    t = par(P[a])
    P[a] = t
    return t
def cb(a, b):
    pa = par(a)
    pb = par(b)
    if pa != pb:
        P[pa] = pb

X = [[] for _ in range(K)]
Y = [[] for _ in range(K)]
for _ in range(N):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    Y[y-1].append(x-1)
for i in range(K):
    for j in range(len(Y[i])-1):
        cb(Y[i][j], Y[i][j+1])

M = [[] for _ in range(K)]
for i in range(K):
    M[par(i)].append(i)
ans = -N
for i in range(K):
    S = []
    for j in M[i]:
        for k in X[j]:
            S.append(k)
    S = list(set(S))
    ans += len(S)*len(M[i])
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, num):
        self.table = [-1 for _ in range(num)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[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 True
        return False
from collections import defaultdict

N = int(input())
u = UnionFind(N)
xy = [list(map(int,input().split())) for _ in range(N)]
x_d = defaultdict(lambda:[])
y_d = defaultdict(lambda:[])
for i in range(N):
    x,y = xy[i]
    x_d[x].append(i)
    y_d[y].append(i)
for x in x_d:
    j = x_d[x][0]
    for i in x_d[x]:
        u.union(i,j)
for y in y_d:
    j = y_d[y][0]
    for i in y_d[y]:
        u.union(i,j)

d = defaultdict(lambda:[])
for i in range(N):
    d[u.find(i)].append(i)

ans = 0
for f in d:
    x_l = []
    y_l = []
    for i in d[f]:
        x,y = xy[i]
        x_l.append(x)
        y_l.append(y)
    x_s = set(x_l)
    y_s = set(y_l)
    ans += len(x_s)*len(y_s)-len(d[f])

print(ans)

Submission status: Accepted

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()
            if x not in dx:
                dx.add(x)
                for y in xty[x]:
                    if y not in dy:
                        stack_y.append(y)

        while stack_y:
            y = stack_y.pop()
            if y not in dy:
                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: Accepted

Solution code:
N = int(input())
x, y = (
    zip(*(map(int, input().split()) for _ in range(N))) if N else
    ((), ())
)


class UnionFindTree:
    def __init__(self, n):
        self.p = [i for i in range(n + 1)]
        self.r = [1 for _ in range(n + 1)]

    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.r[px] < self.r[py]:
                self.p[px] = py
                self.r[py] += self.r[px]
            else:
                self.p[py] = px
                self.r[px] += self.r[py]

    def same(self, x, y):
        return self.find(x) == self.find(y)


uft = UnionFindTree(10**5)
X = [[] for _ in range(10**5 + 1)]
for a, b in zip(x, y):
    X[a].append(b)
Y = [[] for j in range(10**5 + 1)]
for a, b in zip(x, y):
    Y[b].append(a)
SX = set(x)
SY = set(y)
for j in SY:
    for i in Y[j]:
        uft.union(Y[j][0], i)

X2 = [[] for _ in range(10**5 + 1)]
for i in SX:
    X2[uft.find(i)].append(i)
ans = 0
for i in SX:
    S = set()
    for i2 in X2[i]:
        for j in X[i2]:
            S.add(j)
    ans += len(X2[i]) * len(S)
ans -= N

print(ans)

Submission status: Accepted

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

X_dict = {x: [] for x in range(1, 10 ** 5 + 1)}
Y_dict = {y: [] for y in range(1, 10 ** 5 + 1)}
for i, (x, y) in enumerate(Points):
    X_dict[x].append((y, i))
    Y_dict[y].append((x, i))


ans = 0
Visited = [False] * N
for i, (x, y) in enumerate(Points):
    if Visited[i]:
        continue

    stack = [('x', x), ('y', y)]
    cnt = 1
    x_set, y_set = {x}, {y}
    Visited[i] = True
    while stack:
        s, v = stack.pop()
        if s == 'x':
            for yd, j in X_dict[v]:
                if Visited[j]:
                    continue
                else:
                    cnt += 1
                    y_set.add(yd)
                    stack.append(('y', yd))
                    Visited[j] = True
        else:
            for xd, j in Y_dict[v]:
                if Visited[j]:
                    continue
                else:
                    cnt += 1
                    x_set.add(xd)
                    stack.append(('x', xd))
                    Visited[j] = True

    ans += len(x_set) * len(y_set) - cnt

print(ans)

Submission status: Accepted

Solution code:
import sys


def dfs(s, links, dots, checked):
    q = [s]
    xs = set()
    ys = set()
    cnt = 0
    while q:
        v = q.pop()
        if checked[v]:
            continue
        checked[v] = True

        x, y = dots[v]
        xs.add(x)
        ys.add(y)
        cnt += 1
        q.extend(links[v])
    return max(0, len(xs) * len(ys) - cnt)


n = int(input())
dots = [tuple(map(int, line.split())) for line in sys.stdin]
xs = {}
ys = {}
links = [set() for _ in [0] * n]
for i, (x, y) in enumerate(dots):
    if x in xs:
        links[i].add(xs[x])
        links[xs[x]].add(i)
    else:
        xs[x] = i
    if y in ys:
        links[i].add(ys[y])
        links[ys[y]].add(i)
    else:
        ys[y] = i

checked = [False] * n
ans = 0
for i in range(n):
    if checked[i]:
        continue
    ans += dfs(i, links, dots, checked)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

class UnionFind:
    def __init__(self, n,xy):
        self.parent = list(range(n))#親ノード
        self.size = [1]*n #グループの要素数
        self.xval = [{x} for x,y in xy]
        self.yval = [{y} for x,y in xy]

    def root(self, x): #root(x): xの根ノードを返す．
        while self.parent[x] != x:
            x, self.parent[x] = self.parent[x], self.parent[self.parent[x]]
        return x 
 
    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]: 
            self.size[y] += self.size[x] #yの要素数を更新
            self.parent[x] = y #xをyにつなぐ
            self.xval[y].update(self.xval[x])
            self.yval[y].update(self.yval[x])
        else:
            self.size[x] += self.size[y] #xの要素数を更新
            self.parent[y] = x #yをxにつなぐ
            self.xval[x].update(self.xval[y])
            self.yval[x].update(self.yval[y])
        return True
 
    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return self.size[self.root(x)]

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

UF = UnionFind(n,xy)

xval = dict()
yval = dict()
for i,(x,y) in enumerate(xy):
    if y in yval:
        UF.merge(i,yval[y])
    else:
        yval[y] = i

    if x in xval:
        UF.merge(i,xval[x])
    else:
        xval[x] = i

ans = -n
for i,pi in enumerate(UF.parent):
    if i==pi:
        ans += len(UF.xval[pi]) * len(UF.yval[pi])

#print(xval,yval)

print(ans)

Submission status: Accepted

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

X = sorted(set(x for x,y in points))
Y = sorted(set(y for x,y in points))

points = set((bisect_left(X, x), bisect_left(Y, y)) for x,y in points)

xty = [list() for _ in range(len(X))]
ytx = [list() for _ in range(len(Y))]
for x,y in points:
    xty[x].append(y)
    ytx[y].append(x)

area = 0
visited = set()

for p in points:
    if p in visited:
        continue

    stack = [p]

    dx = set()
    dy = set()

    while stack:
        x,y = stack.pop()
        visited.add((x,y))
        if x not in dx:
            for yy in xty[x]:
                if yy != y:
                    stack.append((x,yy))
            dx.add(x)
        if y not in dy:
            for xx in ytx[y]:
                if xx != x:
                    stack.append((xx,y))
            dy.add(y)
    area += len(dx)*len(dy)

print(area-len(points))

Submission status: Accepted

Solution code:
class Union():
  def __init__(me,N):
    me.N = N
    me.up = [-1]*N
    me.down = [ [] for i in range(N) ]
  def union(me,a,b):
    ua = me.up[a] if me.up[a]!=-1 else a
    ub = me.up[b] if me.up[b]!=-1 else b
    if (ua == ub):
      return
    if ( len(me.down[ua]) < len(me.down[ub]) ):
      ub,ua = ua,ub
    for v in me.down[ub]:
      me.up[v] = ua
    me.down[ua].extend( me.down[ub] )
    me.down[ub] = []
    me.up[ub] = ua
    me.down[ua].append( ub )
  def count(me,a):
    ua = me.up[a] if me.up[a]!=-1 else a
    return len(me.down[ua])+1
  
N = int(input())
li = [ [int(it) for it in input().split()] for i in range(N) ]

for i in range(N):
  li[i].append(i)

lx = sorted(li,lambda x:x[0])
ly = sorted(li,lambda x:x[1])

uni = Union(N)
for i in range(N-1):
  if ( lx[i][0] == lx[i+1][0] ):
    uni.union(lx[i][2],lx[i+1][2])
for i in range(N-1):
  if ( ly[i][1] == ly[i+1][1] ):
    uni.union(ly[i][2],ly[i+1][2])

s = 0
for i in range(N):
  if ( uni.up[i] != -1 ):
    continue
  px = set()
  py = set()
  px.add( li[i][0] )
  py.add( li[i][1] )
  for it in uni.down[i]:
      px.add( li[it][0] )
      py.add( li[it][1] )
  #print ( uni.count(i), len(px), len(py) )
  s += len(px)*len(py) - uni.count(i)
print ( s )

Submission status: Accepted

Solution code:
def uf_init(n):
    return list(range(n))

def uf_root(uf, x):
    if uf[x] != x:
        uf[x] = uf_root(uf, uf[x])
    return uf[x]

def uf_same(uf, x, y):
    return uf_root(uf, x) == uf_root(uf, y)

def uf_unite(uf, x, y):
    x = uf_root(uf, x)
    y = uf_root(uf, y)
    if x == y:
        return
    uf[x] = y


N = int(input())

x_dict = {}
y_dict = {}
uf = uf_init(N)

xy_arr = []
for i in range(N):
    x,y = (int(x) for x in input().split())
    if x in x_dict:
        uf_unite(uf, i, x_dict[x])
    else:
        x_dict[x] = i
    if y in y_dict:
        uf_unite(uf, i, y_dict[y])
    else:
        y_dict[y] = i
    xy_arr.append((x,y))

unite_dict = {}
for i in range(N):
    ur = uf_root(uf, i)
    unite_dict.setdefault(ur, [set(), set()])
    unite_dict[ur][0].add(xy_arr[i][0])
    unite_dict[ur][1].add(xy_arr[i][1])

total_points = 0
for k,v in unite_dict.items():
    total_points += len(v[0])*len(v[1])

print(total_points-N)