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:
N = int(input())
xy = [tuple(map(int,input().split())) for _ in range(N)]
shift = 10**5+1

nodes = {}
visited = {}

for x,y in xy:
    y += shift
    if x in nodes:
        nodes[x].append(y)
    else:
        nodes[x] = [y]
    if y in nodes:
        nodes[y].append(x)
    else:
        nodes[y] = [x]
    visited[x] = False
    visited[y] = False

ans = 0

def dfs(s, nodes,visited):
    q = [s]
    cnt_x = 0
    cnt_y = 0
    
    while q:
        v = q.pop()
        if visited[v]:
            continue
        visited[v] = True
        
        if v//shift < 1:
            cnt_x += 1
        else:
            cnt_y += 1
            
        q.extend(nodes[v])
        
    return visited, cnt_x*cnt_y

for s in nodes:
    if visited[s]:
        continue
    visited, cnt = dfs(s,nodes, visited)
    ans += cnt
    
print(ans - N)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))
from collections import defaultdict

class UnionFind:
    def __init__(self, N=None):
        if N is None or N < 1:
            self.parent = defaultdict(lambda: -1)
        else:
            self.parent = [-1]*int(N)

    def root(self, n):
        if self.parent[n] < 0:
            return n
        else:
            m = self.root(self.parent[n])
            self.parent[n] = m
            return m

    def merge(self, m, n):
        rm = self.root(m)
        rn = self.root(n)
        if rm != rn:
            if -self.parent[rm] < -self.parent[rn]:
                rm, rn = rn, rm
            self.parent[rm] += self.parent[rn]
            self.parent[rn] = rm

    def size(self, n):
        return -self.parent[self.root(n)]
    
    def connected(self, m, n):
        return self.root(m) == self.root(n)
    
    def groups(self):
        if isinstance(self.parent,list):
            return list(map(lambda x: x<0, self.parent)).count(True)
        else: # self.parent: defaultdict
            return list(map(lambda x: x<0, self.parent.values())).count(True) 

class CountUp:
    def __init__(self, start=0):
        self.index = start-1

    def __call__(self):
        self.index += 1
        return self.index

N = int(input())
uf = UnionFind()
for _ in range(N):
    x, y = inpl()
    uf.merge(2*x+1,2*y)

Ng = uf.groups()
nx = [0]*Ng
ny = [0]*Ng
gi = defaultdict(CountUp())
for k in uf.parent.keys():
    if k % 2:
        nx[gi[uf.root(k)]] += 1
    else:
        ny[gi[uf.root(k)]] += 1

ans = sum([ nx[g]*ny[g] for g in range(Ng) ]) - N
print(ans)

Submission status: Accepted

Solution code:
"""
https://atcoder.jp/contests/abc131/submissions/6086380
"""
import os
import sys

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import connected_components

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))
PAD = 10 ** 5 + 1
X = np.array(X)
Y = np.array(Y) + PAD

graph = csr_matrix(([True] * N, (X, Y)), shape=(PAD * 2, PAD * 2))
# i から j までのパスがあれば components[i] と components[j] が同じ値
_, components = connected_components(graph)

# 同じ連結成分に含まれる X の数
# x_cnt[i]: 連結成分 i に含まれる x の数
x_cnt = np.bincount(components[:PAD], minlength=PAD * 2)
y_cnt = np.bincount(components[PAD:], minlength=PAD * 2)
# 同じ連結成分である x の数と y の数をかけた数だけその間に辺を張れる
# すでにある分は引く
print((x_cnt * y_cnt).sum() - N)

Submission status: Accepted

Solution code:
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

yx = defaultdict(lambda: set())
xy = defaultdict(lambda: set())
for x, y in zip(X, Y):
    xy[x].add(y)
    yx[y].add(x)


def connected(x=None, y=None, xret=None, yret=None):
    xret = xret if xret else set()
    yret = yret if yret else set()

    if x is not None:
        for y in xy[x]:
            if y in yret:
                continue
            yret.add(y)
            xret, yret = connected(y=y, xret=xret, yret=yret)
    if y is not None:
        for x in yx[y]:
            if x in xret:
                continue
            xret.add(x)
            xret, yret = connected(x=x, xret=xret, yret=yret)

    return xret, yret


x_counted = set()
y_counted = set()

# X と Y の二部グラフで、連結であるすべての組に辺を張る
ans = 0
for x in xy.keys():
    if x in x_counted:
        continue
    xs, ys = connected(x=x)
    # 辺数
    ans += len(xs) * len(ys)
    x_counted |= xs
    y_counted |= ys
# すでにある辺が重複してる
ans -= N
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input().strip())

X = {}
Y = {}
G = (X, Y)

for _ in range(N):
  x, y = map(int, input().strip().split())
  if x not in X: X[x] = []
  if y not in Y: Y[y] = []
  X[x].append(y)
  Y[y].append(x)


def dfs_visit(visited, u, i):
  if u in visited[i]: return
  visited[i].add(u)
  for v in G[i][u]:
    dfs_visit(visited, v, (i + 1) % 2)


count = 0
i = 0
while len(X) > 0:
  visited = (set(), set())
  x = X.__iter__().__next__()
  dfs_visit(visited, x, 0)

  for x in visited[0]:
    count += len(visited[1]) - len(X.pop(x))

print(count)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template

# PyPyだと再帰が遅いので注意
# BEGIN CUT HERE
sys.setrecursionlimit(100000)
class UnionFind():
    '''UnionFind木'''
    def __init__(self,n):
        self.data = [-1] * n
    
    def unite(self, x, y):
        '''x と y を結合'''
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        elif self.data[x] < self.data[y]:
            x, y = y, x  # swap
        self.data[x] += self.data[y]
        self.data[y] = x
    
    def root(self, x):
        '''ノード x の親を返す'''
        if self.data[x] < 0:
            return x
        self.data[x] = self.root(self.data[x])
        return self.data[x]

    def same(self, x, y):
        '''x と y が同じグループに属するか判定'''
        return self.root(x) == self.root(y)
    
    def size(self, x):
        '''x を含むグループのノード数を返す'''
        return self.data[self.root(x)]
        
# END CUT HERE

def ABC120_D():
    n, m = mi()
    a = [0] * m
    b = [0] * m
    for i in range(m):
        a[i], b[i] = mi()
        
    uf = UnionFind(n)
    ans = [0] * (m + 1)
    ans[m] = n * (n - 1) // 2

    for i in range(m - 1, -1, -1):
        a[i] -= 1
        b[i] -= 1
        ans[i] = ans[i + 1]
        if uf.same(a[i], b[i]):
            continue
        
        x = uf.size(a[i])
        y = uf.size(b[i])
        ans[i] -= x * y
        
        uf.unite(a[i],b[i])
    
    for i in range(1, m + 1):
        print(ans[i])

# verified on 2019/06/23
# Python3:616ms https://atcoder.jp/contests/abc120/submissions/6094323

def ABC126_E():
    N, M = mi()
    uf = UnionFind(N)
    for i in range(M):
        _X, _Y, _Z = mi()
        uf.unite(_X - 1, _Y - 1)
    ans = 0
    for i in range(N):
        if uf.root(i) == i:
            ans += 1
    print(ans)
# verified on 2019/06/23
# Python3:468ms https://atcoder.jp/contests/abc126/submissions/6094497

def ABC131_F():
    from collections import defaultdict
    MAX = 100010
    uf = UnionFind(2 * MAX)
    N = ii()
    for i in range(N):
        x, y = mi()
        uf.unite(x, y + MAX)
    
    mx = defaultdict(int)
    for i in range(MAX):
        mx[uf.root(i)] += 1
    my = defaultdict(int)
    for i in range(MAX,2*MAX):
        my[uf.root(i)] += 1
    ans = 0
    for i in range(2 * MAX):
        ans += mx[i] * my[i]
    print(ans - N)


if __name__ == '__main__':
    # ABC120_D()
    # ABC126_E()
    ABC131_F()

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
nmax = 2*10**5
nhalf = 10**5

G = [[] for i in range(nmax)]
for i in range(N):
    x,y = map(int,input().split())
    G[x-1].append(nhalf+y-1)
    G[nhalf+y-1].append(x-1)

used = [False] * nmax
ans = 0
# 全探索
for i in range(nhalf):
    # 見つかったノードからBFS
    if G[i] != [] and not used[i]:
        cnt_1 = 0  #前半の連結
        cnt_2 = 0  #後半の連結
        q = deque([i])
        used[i] = True # 始めどこから行くか
        while len(q) > 0:
            a = q.popleft()
            if a < nhalf:
                cnt_2 += 1
            else:
                cnt_1 += 1
            Vs = G[a]
            # print(Vs)
            for u in Vs: # 頂点以外の要素がグラフにあるときはここ
                if not used[u]:
                    q.append(u)
                    # なにか処理を書きたいときはここに書く
                    used[u] = True
        ans += cnt_1*cnt_2
print(ans-N)

Submission status: Accepted

Solution code:
import sys
# DFSの再帰限界を増やす
sys.setrecursionlimit(10**6)

N = int(input())
nmax = 100001
# nmax = 10
# 第一成分にx,第二成分にyをぶち込んでいく。(二部グラフなので)
xys = [[[] for i in range(nmax)] for j in range(2)]

used = [[0 for i in range(nmax)] for j in range(2)]
# 読み込み
for _ in range(N):
    x, y = map(int, input().split())
    xys[0][x].append(y)
    xys[1][y].append(x)
# print(xys)

# 座標の切り替えをx = 1 or 0と1-xで行うのか、うまい！
# よく考えたらtrue/falseをひっくり返しているだけか。
def dfs(i, el=0):
    # el=0->x, el=1->y
    for i in xys[el][i]:
        if not used[1-el][i]:
            used[1-el][i] = True
            dfs(i, 1-el)
            cnt[1-el] += 1

ans = 0
for i in range(nmax):
    # まだ行ったことがなくて空じゃないところ
    if xys[0][i] != [] and used[0][i] == 0:
        used[0][i] = 1
        cnt = [1,0]
        dfs(i,0)
        ans += cnt[0]*cnt[1]
print(ans-N)

Submission status: Accepted

Solution code:
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :return:
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]


class WeightedUnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
            # 直近の親からの重み。root なら 0
            self._weights = [0 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}
            # 直近の親からの重み。root なら 0
            self._weights = {k: 0 for k in nodes}

    def unite(self, x, y, w):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :param w: x と y の重みの差; (重み y) - (重み x)
        :return:
        """
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return

        # rank が小さい方が下
        if self._ranks[rx] > self._ranks[ry]:
            # x が root
            self._parents[ry] = rx
            self._sizes[rx] += self._sizes[ry]
            # root 間の重みに変換
            self._weights[ry] = w + self._weights[x] - self._weights[y]
        else:
            # y が root
            self._parents[rx] = ry
            self._sizes[ry] += self._sizes[rx]
            # root 間の重みに変換
            self._weights[rx] = -w + self._weights[y] - self._weights[x]
            if self._ranks[rx] == self._ranks[ry]:
                self._ranks[ry] += 1

    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        root = self.find(self._parents[x])
        self._weights[x] += self._weights[self._parents[x]]
        self._parents[x] = root
        return root

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]

    def weight(self, x):
        """
        :param x:
        :return:
        """
        # 経路圧縮
        self.find(x)
        return self._weights[x]

    def diff(self, x, y):
        """
        (y の重み) - (x の重み)
        :param x:
        :param y:
        :return:
        """
        if self.find(x) == self.find(y):
            return self._weights[y] - self._weights[x]
        return float("inf")


N = int(sys.stdin.readline())
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

yx = defaultdict(lambda: set())
xy = defaultdict(lambda: set())
for x, y in zip(X, Y):
    xy[x].add(y)
    yx[y].add(x)

# x が同じである y をまとめる
uf = UnionFind(size=10 ** 5 + 1)
for ys in xy.values():
    yli = list(ys)
    for y1, y2 in zip(yli[1:], yli[:-1]):
        uf.unite(y1, y2)

# まとめた y をキーに x をまとめ直す
yx2 = defaultdict(lambda: set())
for y, xs in yx.items():
    root = uf.find(y)
    yx2[root] |= xs

# y の数 * x の数だけ作れる
ans = 0
for y, xs in yx2.items():
    ans += uf.size(y) * len(xs)
# すでにある頂点は消す
ans -= N
print(ans)

Submission status: Accepted

Solution code:
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")


class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :return:
        """
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]


class WeightedUnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        set の最悪計算量は O(N) なので size 指定のほうが若干速い
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
            # 直近の親からの重み。root なら 0
            self._weights = [0 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}
            # 直近の親からの重み。root なら 0
            self._weights = {k: 0 for k in nodes}

    def unite(self, x, y, w):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        :param w: x と y の重みの差; (重み y) - (重み x)
        :return:
        """
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return

        # rank が小さい方が下
        if self._ranks[rx] > self._ranks[ry]:
            # x が root
            self._parents[ry] = rx
            self._sizes[rx] += self._sizes[ry]
            # root 間の重みに変換
            self._weights[ry] = w + self._weights[x] - self._weights[y]
        else:
            # y が root
            self._parents[rx] = ry
            self._sizes[ry] += self._sizes[rx]
            # root 間の重みに変換
            self._weights[rx] = -w + self._weights[y] - self._weights[x]
            if self._ranks[rx] == self._ranks[ry]:
                self._ranks[ry] += 1

    def find(self, x):
        """
        x が属する木の root
        :param x:
        :return:
        """
        if self._parents[x] == x:
            return x
        root = self.find(self._parents[x])
        self._weights[x] += self._weights[self._parents[x]]
        self._parents[x] = root
        return root

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        :return:
        """
        return self._sizes[self.find(x)]

    def weight(self, x):
        """
        :param x:
        :return:
        """
        # 経路圧縮
        self.find(x)
        return self._weights[x]

    def diff(self, x, y):
        """
        (y の重み) - (x の重み)
        :param x:
        :param y:
        :return:
        """
        if self.find(x) == self.find(y):
            return self._weights[y] - self._weights[x]
        return float("inf")


N = int(sys.stdin.readline())
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

yx = defaultdict(lambda: set())
xy = defaultdict(lambda: set())
for x, y in zip(X, Y):
    xy[x].add(y)
    yx[y].add(x)

# x が同じである y をまとめる
uf = UnionFind(size=10 ** 5 + 1)
for ys in xy.values():
    yli = list(ys)
    for y1, y2 in zip(yli[1:], yli[:-1]):
        uf.unite(y1, y2)

yx2 = defaultdict(lambda: set())
for y, xs in yx.items():
    root = uf.find(y)
    yx2[root] |= xs

ans = 0
for y, xs in yx2.items():
    ans += uf.size(y) * len(xs)
ans -= N
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

N = int(input())
XY = [[[] for _ in range(10**5 +1)] for __ in range(2)]
for _ in range(N):
    x, y = map(int, input().split())
    XY[0][x].append(y)
    XY[1][y].append(x)

def DFS(i, XorY=0):
    for next in XY[XorY][i]:
        if visited[1-XorY][next]==0:
            visited[1-XorY][next] = 1
            DFS(next, 1-XorY)
            count[1-XorY] += 1

ans = 0
visited = [[0 for _ in range(10**5 +1)] for __ in range(2)]
for i in range(10**5 +1):
    if XY[0][i]!=[] and visited[0][i]==0:
        visited[0][i]=1
        count = [1,0]
        DFS(i)
        ans += count[0]*count[1]
ans -= N

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))
from collections import defaultdict

class UnionFind:
    def __init__(self, N=None):
        if N is None or N < 1:
            self.parent = defaultdict(lambda: -1)
        else:
            self.parent = [-1]*int(N)

    def root(self, n):
        if self.parent[n] < 0:
            return n
        else:
            m = self.root(self.parent[n])
            self.parent[n] = m
            return m

    def merge(self, m, n):
        rm = self.root(m)
        rn = self.root(n)
        if rm != rn:
            if -self.parent[rm] < -self.parent[rn]:
                rm, rn = rn, rm
            self.parent[rm] += self.parent[rn]
            self.parent[rn] = rm

    def size(self, n):
        return -self.parent[self.root(n)]
    
    def connected(self, m, n):
        return self.root(m) == self.root(n)
    
    def groups(self):
        if isinstance(self.parent,list):
            return list(map(lambda x: x<0, self.parent)).count(True)
        else: # self.parent: defaultdict
            return list(map(lambda x: x<0, self.parent.values())).count(True) 

class CountUp:
    def __init__(self, start=0):
        self.index = start-1

    def __call__(self):
        self.index += 1
        return self.index

Xi = defaultdict(CountUp())
Yi = defaultdict(CountUp())
N = int(input())
xy = []
for _ in range(N):
    x, y = inpl()
    xi = Xi[x]
    yi = Yi[y]
    xy.append((xi,yi))
Nx = len(Xi)
Ny = len(Yi)
Nxy = Nx + Ny
uf = UnionFind(Nx+Ny)
for xi, yi in xy:
    uf.merge(xi,yi+Nx)

gi = defaultdict(CountUp())
Ng = uf.groups()
edges = [0]*Ng
nx = [0]*Ng
ny = [0]*Ng
for i in range(Nx):
    nx[gi[uf.root(i)]] += 1
for i in range(Nx,Nxy):
    ny[gi[uf.root(i)]] += 1
for xi, yi in xy:
    edges[gi[uf.root(xi)]] += 1

ans = 0
for g in range(Ng):
    ans += nx[g]*ny[g] - edges[g]
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

N = int(input())
e5 = 10 ** 5

v = [[] for _ in range(2 * e5)]
visited = [True] * (2 * e5)

for _ in range(N) :
    x, y = map(int, input().split())
    x, y = x - 1, y - 1
    v[x].append(y + e5)
    v[y + e5].append(x)
    visited[x] = visited[y + e5] = False

ret = 0
for i in range(e5) :
    if not visited[i] :
        queue = [i]
        visited[i] = True
        nx, ny = 1, 0
        
        while queue :
            q = queue.pop()
            for j in v[q] :
                if not visited[j] :
                    visited[j] = True
                    queue.append(j)
                    
                    if j < e5 :
                        nx += 1
                    else :
                        ny += 1
                    
        ret += nx * ny
                    
print(ret - N)

Submission status: Accepted

Solution code:
get = lambda: int(raw_input().strip())
gets = lambda: map(int, raw_input().strip().split())
getss = lambda n: [gets() for _ in xrange(n)]


# N = 3
# A = [[1, 1], [5, 1], [5, 5]]

# N = 2
# A = [[10, 20], [20, 20]]

N = get()
A = getss(N)
UF = {}


def find(x):
    if x != UF[x]:
        UF[x] = find(UF[x])
    return UF[x]


def union(x, y):
    UF.setdefault(x, x)
    UF.setdefault(y, y)
    UF[find(x)] = find(y)


for i, j in A:
    union(i, -j)
count = {}
for x in UF:
    root = find(x)
    if root not in count:
        count[root] = [0, 0]
    count[root][x > 0] += 1

print sum(u[0] * u[1] for u in count.values()) - N

Submission status: Accepted

Solution code:
N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N)]
V = 10**5+5

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.size_x = [1 - i//V for i in range(N)]
        self.size_y = [i//V for i in range(N)]
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
            self.size_x[rb] += self.size_x[ra]
            self.size_y[rb] += self.size_y[ra]
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
            self.size_x[ra] += self.size_x[rb]
            self.size_y[ra] += self.size_y[rb]

uf = UnionFind(V*2)

for x,y in XY:
    uf.unite(x,y+V)
for i in range(V*2):
    uf.root(i)

ans = 0
used = set()
for i in range(V*2):
    r = uf.root(i)
    if r in used: continue
    used.add(r)
    ans += uf.size_x[r] * uf.size_y[r]
ans -= N
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
dx = defaultdict(list)
dy = defaultdict(list)
pts = set()
for _ in range(n):
    x, y = map(int, input().split())
    dx[x].append(y)
    dy[y].append(x)
    pts.add((x, y))

vx, vy = set(), set()
cnt = 0
for x, y in pts:
    if x in vx or y in vy: continue
    sx, sy = [x], [y]
    xs, ys = set(), set()
    while sx or sy:
        while sx:
            x = sx.pop()
            if x not in xs:
                xs.add(x)
                for y in dx[x]:
                    if y not in ys:
                        sy.append(y)
        while sy:
            y = sy.pop()
            if y not in ys:
                ys.add(y)
                for x in dy[y]:
                    if x not in xs:
                        sx.append(x)
    vx.update(xs)
    vy.update(ys)
    cnt += len(xs) * len(ys)
print(cnt - len(pts))

Submission status: Accepted

Solution code:
from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x]) # contruction
        return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        self.par[x] = y

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


n = int(input())

uf = UnionFind(n)
xs = []
ys = []
x_dict = {}
y_dict = {}
for i in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)

    if x in x_dict:
        uf.unite(i, x_dict[x])

    if y in y_dict:
        uf.unite(i, y_dict[y])

    x_dict[x] = uf.find(i)
    y_dict[y] = uf.find(i)

# print(uf.par)
xi = defaultdict(list)
yi = defaultdict(list)
for i in range(n):
    xi[uf.find(x_dict[xs[i]])].append(xs[i])
    yi[uf.find(y_dict[ys[i]])].append(ys[i])

ans = 0
for k in xi.keys():
    ans += len(set(xi[k])) * len(set(yi[k])) - len(xi[k])

print(ans)

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 and 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 = 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**6)

    vertex_maxsize = 10**5 + 1
    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))