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
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()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx == 0 or gy == 0:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
        elif gx != gy:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
    ans = -N
    for xys in g2xy.values():
        nx, ny = 0, 0
        for xy in xys:
            if xy > 0:
                nx += 1
            else:
                ny += 1
        ans += nx * ny
    return ans

print(main())

Submission status: Accepted

Solution code:
def f_must_be_rectangular(N, Positions):
    # 参考: https://atcoder.jp/contests/abc131/submissions/6086451
    # x軸, y軸をまとめて1つのリストで扱う
    import sys
    sys.setrecursionlimit(10**6)

    vertex_maxsize = 10**5 + 5
    target = [[] for _ in range(2 * vertex_maxsize)]
    is_visited = [False] * (2 * vertex_maxsize)
    for x, y in Positions:
        y += vertex_maxsize  # 1つのリストで扱う都合上、ずらす
        target[x].append(y)
        target[y].append(x)

    def dfs(v):
        if is_visited[v]:
            return
        is_visited[v] = True
        count[v // vertex_maxsize] += 1  # vがx軸とy軸のどっちを指しているか
        for u in target[v]:
            dfs(u)  # 頂点vに接続されている頂点へ向かう

    ans = 0
    for i in range(2 * vertex_maxsize):
        if is_visited[i]:
            continue
        count = [0] * 2
        dfs(i)  # 頂点iにつながっている頂点を調べる
        # x座標とy座標のそれぞれについて、ペアにすると矩形が完成する
        # 座標がいくつあるか。その積が解となる
        ans += count[0] * count[1]
    return ans - N  # 最初に与えられた座標の分、引く

N = int(input())
Positions = [[int(i) for i in input().split()] for j in range(N)]
print(f_must_be_rectangular(N, Positions))

Submission status: Accepted

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()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx == 0 or gy == 0:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
        elif gx != gy:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
    ans = -N
    for xys in g2xy.values():
        nx = 0
        for xy in xys:
            if xy > 0:
                nx += 1
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Submission status: Accepted

Solution code:
def f_must_be_rectangular(N, Positions):
    # 参考: https://atcoder.jp/contests/abc131/submissions/6086451
    # x軸, y軸をまとめて1つのリストで扱う
    import sys
    sys.setrecursionlimit(10**7)

    vertex_maxsize = 10**5 + 5
    target = [[] for _ in range(2 * vertex_maxsize)]
    is_visited = [False] * (2 * vertex_maxsize)
    count = [0] * 2
    for x, y in Positions:
        y += vertex_maxsize  # 1つのリストで扱う都合上、ずらす
        target[x].append(y)
        target[y].append(x)

    def dfs(v):
        if is_visited[v]:
            return
        is_visited[v] = True
        count[v // vertex_maxsize] += 1  # vがx軸とy軸のどっちを指しているか
        for u in target[v]:
            dfs(u)  # 頂点vに接続されている頂点へ向かう

    ans = 0
    for i in range(2 * vertex_maxsize):
        if is_visited[i]:
            continue
        count = [0] * 2
        dfs(i)  # 頂点iにつながっている頂点を調べる
        # x座標とy座標のそれぞれについて、ペアにすると矩形が完成する
        # 座標がいくつあるか。その積が解となる
        ans += count[0] * count[1]
    return ans - N  # 最初に与えられた座標の分、引く

N = int(input())
Positions = [[int(i) for i in input().split()] for j in range(N)]
print(f_must_be_rectangular(N, Positions))

Submission status: Accepted

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()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx == 0 or gy == 0:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
        elif gx != gy:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
    ans = -N
    for xys in g2xy.values():
        nx = sum(xy > 0 for xy in xys)
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Submission status: Accepted

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()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx == gy != 0:
            continue
        elif gx != 0 and gy != 0:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        elif gx != 0:
            xy2g[y] = gx
            g2xy[gx].add(y)
        elif gy != 0:
            xy2g[x] = gy
            g2xy[gy].add(x)
        else:
            g = x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        nx = sum(xy > 0 for xy in xys)
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Submission status: Accepted

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()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = [None] * (10 ** 5 * 2 + 1)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx == gy is not None:
            continue
        elif gx is not None is not gy:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        nx = sum(xy > 0 for xy in xys)
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Submission status: Accepted

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()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx == gy != 0:
            continue
        elif gx != 0 != gy:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        nx = sum(xy > 0 for xy in xys)
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(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():
    n = I()
    v = defaultdict(list)
    l = []
    f = defaultdict(lambda : 1)
    for i in range(n):
        x,y = LI()
        y += 100001
        v[x].append(y)
        v[y].append(x)
        if f[x]:
            f[x] = 0
            l.append(x)
        if f[y]:
            f[y] = 0
            l.append(y)
    ans = 0
    bfs = defaultdict(lambda : 1)
    q = deque()
    for i in l:
        if bfs[i]:
            bfs[i] = 0
            q.append(i)
            nx = (i < 100001)
            ny = 1-nx
            while q:
                x = q.popleft()
                for y in v[x]:
                    if bfs[y]:
                        bfs[y] = 0
                        q.append(y)
                        k = (y < 100001)
                        nx += k
                        ny += (1-k)
            ans += nx*ny
    print(ans-n)
    return

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

Submission status: Accepted

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 ** 4:
        m, p = 0, 0
        for k in edges.keys():
            if k < 0:
                m += 1
            else:
                p += 1
        return m * p - 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: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

class UnionFind():
    def __init__(self, N):
        self.rank = [0] * N
        self.par = [i for i in range(N)]
        self.counter = [1] * 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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            z = self.counter[x] + self.counter[y]
            self.counter[x], self.counter[y] = z, z
        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 size(self, x):
        x = self.find(x)
        return self.counter[x]

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

N = int(input())
uf = UnionFind(N)
x_dict={}
y_dict={}

xy = []
for i in range(N):
    x,y = map(int,input().split())
    if x in x_dict:
        uf.unite(i,x_dict[x])
    else:
        x_dict[x]=i
    if y in y_dict:
        uf.unite(i,y_dict[y])
    else:
        y_dict[y]=i
    xy.append((x,y))
unite_dict={}
for i in range(N):
    ur = uf.find(i)
    unite_dict.setdefault(ur,[set(),set()])
    unite_dict[ur][0].add(xy[i][0])
    unite_dict[ur][1].add(xy[i][1])

p = 0
for k,v in unite_dict.items():
    p +=len(v[0])*len(v[1])
print(p-N)

Submission status: Accepted

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()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx == gy != 0:
            continue
        elif gx != 0 and gy != 0:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        nx = sum(xy > 0 for xy in xys)
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Submission status: Accepted

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()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != 0 and gy != 0:  # merge
            if gx == gy:
                continue
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        nx = sum(xy > 0 for xy in xys)
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Submission status: Accepted

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()
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for _ in range(N):
        x, y = LI()
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != 0 and gy != 0:  # merge
            if gx == gy:
                continue
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        nx = sum(xy > 0 for xy in xys)
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Submission status: Accepted

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()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != 0 and gy != 0 and gx != gy:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        nx = sum(xy > 0 for xy in xys)
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Submission status: Accepted

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()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != 0 and gy != 0 and gx != gy:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        nx = len([1 for xy in xys if xy > 0])
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Submission status: Accepted

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()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != 0 and gy != 0 and gx != gy:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        nx = sum(1 for xy in xys if xy > 0)
        ny = len(xys) - nx
        ans += nx * ny
    return ans

print(main())

Submission status: Accepted

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()
    xy = []
    for _ in range(N):
        xy.append(LI())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != 0 and gy != 0:  # merge
            if gx == gy:
                continue
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        m, p = 0, 0
        for xy in xys:
            if xy < 0:
                m += 1
            else:
                p += 1
        ans += m * p
    return ans

print(main())

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import *
import sys
input = sys.stdin.readline

U = 10**5
N = int(input())
XY = np.array([input().split() for _ in range(N)], dtype=np.int32)

graph = csr_matrix((np.ones(N,dtype=np.bool), (XY[:,0], U + XY[:,1])), (2*U+1, 2*U+1))
_, component = csgraph.connected_components(graph)

X_cnt = np.bincount(component[:U+1], minlength = 2*U+2)
Y_cnt = np.bincount(component[U+1:], minlength = 2*U+2)
pts_cnt = np.bincount(component[XY[:,0]], minlength = 2*U+2)
answer = (X_cnt * Y_cnt - pts_cnt).sum()
print(answer)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import *

U = 10**5
N = int(input())
XY = np.array([input().split() for _ in range(N)], dtype=np.int32)

graph = csr_matrix(([1]*N, (XY[:,0], U + XY[:,1])), (2*U+1, 2*U+1))
_, component = csgraph.connected_components(graph)

X_cnt = np.bincount(component[:U+1], minlength = 2*U+2)
Y_cnt = np.bincount(component[U+1:], minlength = 2*U+2)
pts_cnt = np.bincount(component[XY[:,0]], minlength = 2*U+2)
answer = (X_cnt * Y_cnt - pts_cnt).sum()
print(answer)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse import *

U = 10**5
N = int(input())
XY = np.array([input().split() for _ in range(N)], dtype=np.int32)

graph = csr_matrix((np.ones(N,dtype=np.bool), (XY[:,0], U + XY[:,1])), (2*U+1, 2*U+1))
_, component = csgraph.connected_components(graph)

X_cnt = np.bincount(component[:U+1], minlength = 2*U+2)
Y_cnt = np.bincount(component[U+1:], minlength = 2*U+2)
pts_cnt = np.bincount(component[XY[:,0]], minlength = 2*U+2)
answer = (X_cnt * Y_cnt - pts_cnt).sum()
print(answer)

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))#親ノード
        self.size = [1]*n #グループの要素数

    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につなぐ
        else:
            self.size[x] += self.size[y] #xの要素数を更新
            self.parent[y] = x #yをxにつなぐ
        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)

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


xcon = dict()
ycon = dict()
for i in range(n):
    pi = UF.root(i)
    x,y = xy[i]
    if pi in xcon:
        xcon[pi].add(x)
    else:
        xcon[pi] = {x}

    if pi in ycon:
        ycon[pi].add(y)
    else:
        ycon[pi] = {y}
        

ans = -n
#print(xcon,ycon)
for key, val in xcon.items():
    ans += len(val) * len(ycon[key])

#print(UF.parent)
#print(xval,yval)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())

x_list = [0] * N
y_list = [0] * N

for i in range(N):
    x, y = map(int, input().split())
    x_list[i] = x + 1000000
    y_list[i] = y

# graph
G = dict()
for i in range(N):
    x = x_list[i]
    y = y_list[i]
    G[x] = dict()
    G[y] = dict()

for i in range(N):
    x = x_list[i]
    y = y_list[i]
    G[x][y] = 1
    G[y][x] = 1

x_su = list(set(x_list))
Lx = len(x_su)
x_su_ind = dict()
for i in range(Lx):
    x_su_ind[x_su[i]] = i

y_su = list(set(y_list))
Ly = len(y_su)
y_su_ind = dict()
for i in range(Ly):
    y_su_ind[y_su[i]] = i

done_x = [0]*Lx
done_y = [0]*Ly

res = 0

id_0 = 0
while True:
    while done_x[id_0] == 1:
        id_0 += 1
        if id_0 == Lx:
            break
    if id_0 == Lx:
        break
    # BFS
    cx = 1
    cy = 0
    queue = deque([x_su[id_0]])
    done_x[id_0] = 1
    while len(queue) > 0:
        p = queue.popleft()
        for q in G[p].keys():
            if q < 1000000:
                if done_y[y_su_ind[q]] == 0:
                    queue.append(q)
                    done_y[y_su_ind[q]] = 1
                    cy += 1
            else:
                if done_x[x_su_ind[q]] == 0:
                    queue.append(q)
                    done_x[x_su_ind[q]] = 1
                    cx += 1
    res += cx * cy

print(res - N)