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:
from operator import itemgetter

class UnionFindTree():
    def __init__(self, N):
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    def size(self, a):
        return self.__size[self.root(a)]

    def groups(self):
        groups = {}
        for k in range(len(self.__parent_of)):
            r = self.root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N = int(input())
    uft = UnionFindTree(N)
    P = [None] * N
    for i in range(N):
        x, y = map(int, input().split())
        P[i] = (i, x, y)
    Q = sorted(P, key=itemgetter(1))
    for i in range(1, N):
        if Q[i-1][1] == Q[i][1]:
            uft.unite(Q[i-1][0], Q[i][0])
    R = sorted(P, key=itemgetter(2))
    for i in range(1, N):
        if R[i-1][2] == R[i][2]:
            uft.unite(R[i-1][0], R[i][0])
    groups = uft.groups()
    ans = 0
    for g in groups:
        if len(g) < 3:
            continue
        xs = set()
        ys = set()
        for i in g:
            _, x, y = P[i]
            xs.add(x)
            ys.add(y)
        ans += len(xs) * len(ys) - len(g)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

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

        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]

from operator import itemgetter
from collections import defaultdict
from itertools import groupby
N = int(input())
XYI = []
for i in range(N):
    x, y = map(int, input().split())
    XYI.append([x, y, i])
XYx = sorted(XYI, key=itemgetter(0))
XYy = sorted(XYI, key=itemgetter(1))

uf = Uf(N)
px = py = -1
for x, y, i in XYx:
    if px==x:
        uf.unite(i, pi)
    px, pi = x, i
for x, y, i in XYy:
    if py==y:
        uf.unite(i, pi)
    py, pi = y, i
ddx = defaultdict(set)
ddy = defaultdict(set)
for x, y, i in XYI:
    ddx[uf.root(i)].add(x)
    ddy[uf.root(i)].add(y)
ans = 0
for i in range(N):
    if i==uf.root(i):
        ans += len(ddx[i]) * len(ddy[i])
print(ans - N)

Submission status: Accepted

Solution code:
# (x,a), (x,b) → (s,a)と(t,b)は同値になる → aとbを同一視
# 連結成分を作る
N = int(input())
U = 10 ** 5
root_x = [None] * (U+1)
root_y = [None] * (U+1)
size_x = [0] * (U+1) # 連結成分のxの個数
size_y = [0] * (U+1) # 連結成分のyの個数
cnt_x = [0] * (U+1) # 生成時に登場した点
cnt_y = [0] * (U+1) # 生成時に登場した点
x_to_y = [None] * (U+1)
y_to_x = [None] * (U+1)

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

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]

  
answer = 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]
  answer += (sx * sy - cnt)
print(answer)

Submission status: Accepted

Solution code:
N=int(input())
from collections import defaultdict
X=dict()
Y=dict()
P=[]
root=[-1]*N
def find(i):
    global root
    if root[i]>=0:
        root[i]=find(root[i])
        return root[i]
    return i
for i in range(N):
    x,y=map(int,input().split())
    P+=[(x,y)]
    if x not in X.keys():
        rx=i
        X[x]=i
    else:
        rx=find(X[x])
        X[x]=rx
    if y not in Y.keys():
        ry=i
        Y[y]=i
    else:
        ry=find(Y[y])
        Y[y]=ry
    if rx==ry:
        if i!=rx:
            root[i]=rx
        continue
    elif root[rx]<=root[ry]:
        root[rx]+=root[ry]
        root[ry]=rx
        if i!=rx:
            root[i]=rx
    else:
        root[ry]+=root[rx]
        root[rx]=ry
        if i!=ry:
            root[i]=ry
cntx=defaultdict(set)
cnty=defaultdict(set)
RP=set()
ans=0
for i in range(N):
    x,y=P[i]
    r=find(i)
    cntx[r]|={x}
    cnty[r]|={y}
    RP|={r}
for k in RP:
    ans+=len(cntx[k])*len(cnty[k])
print(ans-N)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import random
import collections
import math
import itertools
import bisect

def real_main():
    n = read_int()
    points = [read_int_array() for _ in range(n)]
    next_id = 1
    scc = [0]*n
    y_idx = collections.defaultdict(list)
    x_idx = collections.defaultdict(list)
    for i, (x, y) in enumerate(points):
        y_idx[y].append(i)
        x_idx[x].append(i)

    def bfs(start):
        q = [start]
        for i in q:
            x, y = points[i]
            for ni in y_idx[y]:
                if not scc[ni]:
                    scc[ni] = next_id
                    q.append(ni)
            for ni in x_idx[x]:
                if not scc[ni]:
                    scc[ni] = next_id
                    q.append(ni)
        return q

    ans = 0
    for i in range(n):
        if not scc[i]:
            scc[i] = next_id
            scc_points = bfs(i)
            diff_x, diff_y = len(set(points[idx][0] for idx in scc_points)), len(set(points[idx][1] for idx in scc_points))
            if diff_x > 1 and diff_y > 1:
                ans += diff_x * diff_y - len(scc_points)
            next_id += 1
    print(ans)


def solve():
    pass


def main():
    if False and 'PYCHARM_HOSTED' in os.environ:
        main_pycharm()
    else:
        real_main()


from copy import deepcopy
def main_pycharm():
    solution = solve

    test_inputs = None
    test_outputs = None
    judge = None
    slow_solution = None
    if solution is not None:
        if test_outputs is not None:
            test_with_answers(solution, test_inputs, test_outputs)
        if judge is not None:
            test_with_judge(solution, test_inputs, judge)
        if slow_solution is not None:
            test_with_slow_solution(solution, test_inputs, slow_solution)


def test_with_answers(solution, inputs, answers):
    total, wrong = 0, 0
    for args, test_ans in zip(inputs, answers):
        ans = solution(*deepcopy(args))
        if ans != test_ans:
            print('WRONG! ans=%s, test_ans=%s, args=%s' % (ans, test_ans, args))
            wrong += 1
        else:
            print('GOOD')
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_judge(solution, inputs_gen, judge):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        if not judge(deepcopy(ans), *deepcopy(args)):
            print('WRONG! ans=%s, args=%s' % (ans, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


def test_with_slow_solution(solution, inputs_gen, solution_slow):
    total, wrong = 0, 0
    for args in inputs_gen:
        ans = solution(*deepcopy(args))
        slow = solution_slow(*deepcopy(args))
        if ans != slow:
            print('WRONG! ans=%s, slow=%s, args=%s' % (ans, slow, args))
            wrong += 1
        total += 1
    print('ALL %d TESTS PASSED' % total if not wrong else '%d out of %d tests are WRONG' % (wrong, total))


# This mergesort can be like 7 times faster than build in sort
# (for stupid reasons)
def mergesort(A, key=lambda x: x, reverse=False):
    C = A
    A = list(range(len(A)))
    B = list(A)

    n = len(A)
    for i in range(0, n - 1, 2):
        if key(C[A[i]]) > key(C[A[i ^ 1]]):
            A[i], A[i ^ 1] = A[i ^ 1], A[i]

    width = 2
    while width < n:
        for i in range(0, n, 2 * width):
            R1, R2 = min(i + width, n), min(i + 2 * width, n)
            j, k = R1, i
            while i < R1 and j < R2:
                if key(C[A[i]]) > key(C[A[j]]):
                    B[k] = A[j]
                    j += 1
                else:
                    B[k] = A[i]
                    i += 1
                k += 1
            while i < R1:
                B[k] = A[i]
                k += 1
                i += 1
            while k < R2:
                B[k] = A[k]
                k += 1
        A, B = B, A
        width *= 2

    if reverse:
        A.reverse()
    return A


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

def read():
    return input()

def read_int():
    return int(input())

def read_array(sep=None, maxsplit=-1):
    return input().split(sep, maxsplit)

def read_int_array():
    return [int(a) for a in read_array()]

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# (x,a), (x,b) → (s,a)と(t,b)は同値になる → aとbを同一視
# 連結成分を作る
N = int(input())
U = 10 ** 5
root_x = [None] * (U+1)
root_y = [None] * (U+1)
size_x = [0] * (U+1) # 連結成分のxの個数
size_y = [0] * (U+1) # 連結成分のyの個数
cnt_x = [0] * (U+1) # 生成時に登場した点
cnt_y = [0] * (U+1) # 生成時に登場した点
x_to_y = [None] * (U+1)
y_to_x = [None] * (U+1)

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

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]

  
answer = 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]
  answer += (sx * sy - cnt)
print(answer)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

class UnionFindTree:
    def __init__(self, n):
        self.nodes = list(range(n+1))
    def find(self, x):
        if self.nodes[x] == x:
            return x
        parent = self.find(self.nodes[x])
        self.nodes[x] = parent
        return parent
    def unite(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        self.nodes[a] = self.nodes[b]
    def is_same(self, a, b):
        return self.find(a) == self.find(b)

UFL=UnionFindTree(100010)
UFR=UnionFindTree(100010)

N=II()
rmap = {}
lmap = {}
for i in range(N):
    l,r=LI()
    if not r in rmap:
        rmap[r] = []
    if not l in lmap:
        lmap[l] = []
    rmap[r].append(l)
    lmap[l].append(r)

for l, lis in lmap.items():
    for r in lmap[l]:
        for l2 in rmap[r]:
            UFL.unite(l,l2)
for r, lis in rmap.items():
    for l in rmap[r]:
        for r2 in lmap[l]:
            UFR.unite(r,r2)

varl = {}
varr = {}

for l in lmap.keys():
    gr = UFL.find(l)
    if gr in varl:
        varl[gr] += 1
    else:
        varl[gr] = 1

for r in rmap.keys():
    gr = UFR.find(r)
    if gr in varr:
        varr[gr] += 1
    else:
        varr[gr] = 1

res = {}
for l, lis in lmap.items():
    gl = UFL.find(l)
    gr = UFR.find(lis[0])
    res[(gl,gr)] = varl[gl] * varr[gr]

# print(varl)
# print(varr)
# print(res)
ressum = 0
for i in res.values():
    ressum += i
print(ressum - N)

Submission status: Accepted

Solution code:
class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[i for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)
N=int(input())
P=[(i,)+tuple(map(int,input().split())) for i in range(N)]
G=UnionFind(N)
P.sort(key=lambda x:x[1])
for i in range(N-1):
    if P[i][1]==P[i+1][1]:
        G.unite(P[i][0],P[i+1][0])
P.sort(key=lambda x:x[2])
for i in range(N-1):
    if P[i][2]==P[i+1][2]:
        G.unite(P[i][0],P[i+1][0])
P.sort(key=lambda x:x[0])
Dx=dict()
Dy=dict()
for i in range(N):
    j=G.find(i)
    if j in Dx:
        Dx[j].add(P[i][1])
    else:
        Dx[j]={P[i][1]}
    if j in Dy:
        Dy[j].add(P[i][2])
    else:
        Dy[j]={P[i][2]}
ans=-N
for j in Dx:
    ans+=len(Dx[j])*len(Dy[j])
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(2*10**6)
class UF():
    def __init__(self, num):
        self.par = [-1]*num
        self.size = [1]*num
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
                self.size[rx] += self.size[ry] 
            elif self.par[rx] > self.par[ry]:
                self.par[rx] = ry
                self.size[ry] += self.size[rx]
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
                self.size[rx] += self.size[ry]
        return



N = int(input())

XY = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]
X, Y = list(map(list, zip(*XY)))
G = UF(N)
checked = [False]*N

Xc = defaultdict(list)
Yc = defaultdict(list)
for i in range(N):
    Xc[X[i]].append(i)
    Yc[Y[i]].append(i)

for v in Xc.values():
    if len(v) == 1:
        continue
    vx = v[0]
    for x in v[1:]:
        G.union(vx, x)

for v in Yc.values():
    if len(v) == 1:
        continue
    vy = v[0]
    for y in v[1:]:
        G.union(vy, y)

ans = -N

Zx = defaultdict(set)
Zy = defaultdict(set)
for i in range(N):
    ri = G.find(i)
    Zx[ri].add(X[i])
    Zy[ri].add(Y[i])

for i in range(N):
    ri = G.find(i)
    if checked[ri] == True:
        continue
    checked[ri] = True
    ans += len(Zx[ri])*len(Zy[ri])
print(ans)

Submission status: Accepted

Solution code:
# coding=utf-8


get = lambda: int(raw_input().strip())
getl = lambda: 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]
    if x > 0:
        count[root][0] += 1
    else:
        count[root][1] += 1

res = 0
for x in count:
    pos, neg = count[x]
    if pos > 1 and neg > 1:
        res += pos * neg
    else:
        res += max(pos, neg)
print res - N

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def Find(x):    #xの根を返す
    global table

    if table[x] == x:
        return x
    else:
        table[x] = Find(table[x])    #親の更新(根を直接親にして参照距離を短く)
        size[x] = size[table[x]]
        return table[x]

def Unite(x,y):    #xとyを繋げる
    global size
    global rank
    x = Find(x)
    y = Find(y)
    sx = Size(x)
    sy = Size(y)

    if x == y:
        return

    if rank[x] > rank[y]:
        table[y] = x
        size[x] = sx + sy
    else:
        table[x] = y
        size[y] = sx + sy
        if rank[x] == rank[y]:
            rank[y] += 1

def Check(x,y):
    if Find(x) == Find(y):
        return True
    else:
        return False

def Size(x):
    return size[Find(x)]

table = [i for i in range(10**5+1)]    #木の親 table[x] == x なら根
rank  = [1 for i in range(10**5+1)]    #木の長さ
size  = [1 for i in range(10**5+1)]    #集合のサイズ


N = int(input())
xys = [inpl() for _ in range(N)]
xys.sort()
tatedict = defaultdict(list)
xx = set()
for x,y in xys:
    tatedict[x].append(y)
    xx.add(x)

for x in xx:
    s = tatedict[x][0]
    for t in tatedict[x]:
        if not Check(s,t):
            Unite(s,t)

ans = 0
for x in xx:
    s = tatedict[x][0]
    ans += Size(s) - len(tatedict[x])

print(ans)

Submission status: Accepted

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

N=int(input())
P=[list(map(int,input().split()))+[i] for i in range(N)]
Q=copy.deepcopy(P)

#UnionFind

Group=[i for i in range(N)]#グループ分け.Group[i]=jのときiとjは同じグループ

def find(x):#find(a)=find(b)のとき同じグループ
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):  # xとyが同じグループになるよう更新
    if find(x) != find(y):
        Group[find(y)]=Group[find(x)]=min(find(y),find(x))

P.sort(key=lambda x:x[0])

for i in range(1,N):
    if P[i][0]==P[i-1][0]:
        Union(P[i][2],P[i-1][2])


P.sort(key=lambda x:x[1])

for i in range(1,N):
    if P[i][1]==P[i-1][1]:
        Union(P[i][2],P[i-1][2])

#print([find(i) for i in range(N)])
#F=[find(i) for i in range(N)]
#S=set(F)

B=[[] for i in range(N)]

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

ANS=0
for BEL in B:
    X=[]
    Y=[]
    for b in BEL:
        X.append(Q[b][0])
        Y.append(Q[b][1])

    #print(BEL,X,Y)
    ANS+=len(set(X))*len(set(Y))-len(BEL)
print(ANS)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()

upper = [-1]*(2*n)
nxs = [0]*(2*n)
for i in range(n):
    nxs[i] += 1

def root(x):
    if upper[x] < 0:
        return x
    else:
        upper[x] = root(upper[x])
        return upper[x]

def equiv(x, y):
    return root(x) == root(y)

def unite(x, y):
    x, y = root(x), root(y)
    if x != y:
        if upper[y] < upper[x]:
            x, y = y, x
        upper[x] += upper[y]
        nxs[x] += nxs[y]
        upper[y] = x
    return x == y



co = []

for i in range(n):
    co.append(na())

xs = list(set(_[0] for _ in co))
xs.sort()

ys = list(set(_[1] for _ in co))
ys.sort()

for c in co:
    unite(bisect_left(xs, c[0]), bisect_left(ys, c[1])+n)

ans = 0
for i in range(2*n):
    if upper[i] < 0:
        ans += nxs[i] * (-upper[i] - nxs[i])
ans -= n
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readlines = sys.stdin.buffer.readlines
input = sys.stdin.buffer.readline

OFS = 100005
N = int(input())
G = [[] for _ in [0]*OFS*2]
for line in readlines():
    x, y = map(int, line.split())
    y += OFS
    G[x].append(y)
    G[y].append(x)

visited = [0]*OFS*2


def dfs(v, x=0, y=0):
    if v < OFS:
        x += 1
    else:
        y += 1

    for u in G[v]:
        if visited[u]:
            continue
        visited[u] = 1
        x, y = dfs(u, x, y)

    return x, y


ans = 0
for i in range(OFS):
    if visited[i]:
        continue
    visited[i] = 1
    x, y = dfs(i)
    ans += x*y

print(ans - N)

Submission status: Runtime Error

Solution code:
N=int(input())
G=[[] for i in range(200000)]
x,y=0,0
B=[0]*200000
for i in range(N):
  x,y=map(int,input().split())
  G[99999+y].append(x-1)
  G[x-1].append(99999+y)
P=0
CE=0
CV=[0,0]
def dfs(p,n):
  global CE,CV
  CE+=1
  if B[n]:
    return 0
  CV[n//100000]+=1
  B[n]=1
  for i in range(len(G[n])):
    if G[n][i]!=p:
      dfs(n,G[n][i])

for i in range(200000):
  if ~B[i]:
    CE=0
    CV=[0,0]
    dfs(-1,i)
    P+=max((CV[0])*(CV[1])-CE+1,0)
print(P)

Submission status: Runtime Error

Solution code:
N=int(input())
G=[[] for i in range(200000)]
x,y=0,0
B=[0]*200000
for i in range(N):
  x,y=map(int,input().split())
  G[99999+y].append(x-1)
  G[x-1].append(99999+y)
P=0
CE=0
CV=[0,0]
def dfs(p,n):
  if n>=200000:
    while True:
      pass
  global CE,CV
  CE+=1
  if B[n]:
    return 0
  CV[n//100000]+=1
  B[n]=1
  for i in range(len(G[n])):
    if G[n][i]!=p:
      dfs(n,G[n][i])

for i in range(200000):
  if ~B[i]:
    CE=0
    CV=[0,0]
    dfs(-1,i)
    P+=(CV[0])*(CV[1])-CE+1
print(P)

Submission status: Runtime Error

Solution code:
N=int(input())
G=[[] for i in range(200000)]
x,y=0,0
B=[0]*200000
for i in range(N):
  x,y=map(int,input().split())
  G[99999+y].append(x-1)
  G[x-1].append(99999+y)
P=0
CE=0
CV=[0,0]
def dfs(p,n):
  global CE,CV
  CE+=1
  if B[n]:
    return 0
  CV[n//100000]+=1
  B[n]=1
  for i in range(len(G[n])):
    if G[n][i]!=p:
      dfs(n,G[n][i])

for i in range(200000):
  if ~B[i]:
    CE=0
    CV=[0,0]
    dfs(-1,i)
    P+=(CV[0])*(CV[1])-CE+1
print(P)

Submission status: Runtime Error

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    ################
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        重いかも！　　members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        重いかも！　all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        def find(self, x):
            #根を探す&つなぎかえる
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

            if self.parents[x] > self.parents[y]:
                x, y = y, x

            self.parents[x] += self.parents[y]
            self.parents[y] = x

        def size(self, x):
            return -self.parents[self.find(x)]

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

        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}

        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
        
    ################

    """
    解説放送のように，グラフを考える．
    X座標を表す点を10**5個
    Y座標を表す点を10**5個用意．
    座標を点，点をグラフの辺として表す
    """

    N=I()
    M=10**5
    XY=[0]*(2*M)
    uf=UnionFind(2*M)
    for i in range(N):
        x,y=MI()
        y+=M
        XY[x]+=1
        XY[y]+=1
        uf.union(x,y)
    
    #　各根要素に対して，xの要素数，yの要素数，入出する辺の本数をメモ
    from collections import defaultdict
    ddx = defaultdict(int)
    ddy = defaultdict(int)
    dde = defaultdict(int)
    
    for i in range(2*M):
        root=uf.find(i)
        if i<M:
            ddx[root]+=1
        else:
            ddy[root]+=1
        dde[root]+=XY[i]
        
    ans=0
    
    for k,v in dde.items():
        temp=ddx[k]*ddy[k]-v//2
        ans+=temp
        
    print(ans)
    
    
    

main()