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: Wrong Answer

Solution code:
N = int(input())
points = []
for i in range(0, N):
    points.append(list(map(int, input().split(' '))))
abcd = list(set(sum(points, [])))
count = 0
for i, a in enumerate(abcd):
    for j, b in enumerate(abcd):
        for c in abcd[i+1:]:
            for d in abcd[j+1:]:
                if a == c and b == d:
                    continue
                p = []
                if [a, b] not in points:
                    p.append([a, b])
                if [a, d] not in points:
                    p.append([a, d])
                if [c, b] not in points:
                    p.append([c, b])
                if [c, d] not in points:
                    p.append([c, d])
                if len(p) == 1:
                    count += 1
                    points.append(p[0])
print(count)

Submission status: Wrong Answer

Solution code:
V=10**5+1
class UnionFind:
    def __init__(self,n):
        self.parent=[i for i in range(n)]
        self.rank=[0 for _ in range(n)]
        # use for n=2*V
        self.xSize=[1 if i<V else 0 for i in range(n)]
        self.ySize=[0 if i<V else 1 for i in range(n)]

    def find(self,x):
        if self.parent[x]==x:
            return x
        else:
            parentx=self.find(self.parent[x])
            self.parent[x]=parentx
            return parentx

    def union(self,x,y):
        rootx=self.find(x)
        rooty=self.find(y)
        if self.rank[rootx]>self.rank[rooty]:
            self.parent[rooty]=rootx
            self.xSize[rootx]+=self.xSize[rooty]
            self.ySize[rootx]+=self.ySize[rooty]
        else:
            self.parent[rootx]=rooty
            self.xSize[rooty]+=self.xSize[rootx]
            self.ySize[rooty]+=self.ySize[rootx]
            if self.rank[rootx]==self.rank[rooty]:
                self.rank[rooty]+=1

n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
uf=UnionFind(V*2)
for xi,yi in xy:
    uf.union(xi,yi+V)

for i in range(V*2):
    uf.find(i)

ans=0
used=set()
for i in range(V*2):
    rooti=uf.find(i)
    if rooti not in used:
        used.add(rooti)
        ans+= uf.xSize[rooti]*uf.ySize[rooti]
print(ans-n)

Submission status: Wrong Answer

Solution code:
V=10**5+1
class UnionFind:
    def __init__(self,n):
        self.parent=[i for i in range(n)]
        self.rank=[0 for _ in range(n)]
        # use for n=2*V
        self.xSize=[1 if i<V else 0 for i in range(n)]
        self.ySize=[0 if i<V else 1 for i in range(n)]

    def find(self,x):
        if self.parent[x]==x:
            return x
        else:
            parentx=self.find(self.parent[x])
            self.parent[x]=parentx
            return parentx

    def union(self,x,y):
        rootx=self.find(x)
        rooty=self.find(y)
        if self.rank[rootx]>self.rank[rooty]:
            self.parent[rooty]=rootx
            self.xSize[rootx]+=self.xSize[rooty]
            self.ySize[rootx]+=self.ySize[rooty]
        else:
            self.parent[rootx]=rooty
            self.xSize[rooty]+=self.xSize[rootx]
            self.ySize[rooty]+=self.ySize[rootx]
            if self.rank[rootx]==self.rank[rooty]:
                self.rank[rooty]+=1

n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
uf=UnionFind(V*2)
for xi,yi in xy:
    uf.union(xi,yi+V)

# for i in range(V*2):
#     uf.find(i)

ans=0
used=set()
for i in range(V*2):
    rooti=uf.find(i)
    if rooti not in used:
        used.add(rooti)
        ans+= uf.xSize[rooti]*uf.ySize[rooti]
print(ans-n)

Submission status: Wrong Answer

Solution code:
N = int(input())
COR = [tuple((map(int, input().split()))) for _ in range(N)]


class Group:
    
    def __init__(self, x, y):
        self.n = 1
        self.x = [x]
        self.y = [y]
        
    def insert(self, x, y):
        if x not in self.x:
            self.x.append(x)
        if y not in self.y:
            self.y.append(y)
        self.n += 1
    
    def new_cor_n(self):
        if self.n == 0:
            return 0
        return len(self.x) * len(self.y) - self.n

    def join(self, group):
        self.n += group.n
        self.x.extend(group.x)
        self.x = list(set(self.x))
        self.y.extend(group.y)
        self.y = list(set(self.y))
        group.n = 0


if N <= 2:
    print(0)
else:
    xg, yg = {}, {}
    group_list = []
    for xi, yi in COR:
        if xi in xg:
            group1 = xg[xi]
            if yi in yg:
                group2 = yg[yi]
                for xk in group2.x:
                    xg[xk] = group1
                for yk in group2.y:
                    yg[yk] = group1
                xg[xi].join(yg[yi])
            yg[yi] = group1
            group1.insert(xi, yi)
        elif yi in yg:
            group = yg[yi]
            xg[xi] = group
            group.insert(xi, yi)
        else:
            new_group = Group(xi, yi)
            xg[xi] = new_group
            yg[yi] = new_group
            group_list.append(new_group)
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)

Submission status: Wrong Answer

Solution code:
N = int(input())
COR = [tuple((map(int, input().split()))) for _ in range(N)]


class Group:
    
    def __init__(self, x, y):
        self.n = 1
        self.x = [x]
        self.y = [y]
        
    def insert(self, x, y):
        if x not in self.x:
            self.x.append(x)
        if y not in self.y:
            self.y.append(y)
        self.n += 1
    
    def new_cor_n(self):
        if self.n == 0:
            return 0
        return len(self.x) * len(self.y) - self.n

    def join(self, group):
        self.n += group.n
        self.x.extend(group.x)
        self.x = list(set(self.x))
        self.y.extend(group.y)
        self.y = list(set(self.y))
        group.n = 0


if N <= 2:
    print(0)
else:
    xg, yg = {}, {}
    group_list = []
    for xi, yi in COR:
        if xi in xg:
            if yi in yg:
                xg[xi].join(yg[yi])
            group = xg[xi]
            yg[yi] = group
            group.insert(xi, yi)
        elif yi in yg:
            group = yg[yi]
            xg[xi] = group
            group.insert(xi, yi)
        else:
            new_group = Group(xi, yi)
            xg[xi] = new_group
            yg[yi] = new_group
            group_list.append(new_group)
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)

Submission status: Wrong Answer

Solution code:
class Group:
    
    def __init__(self, x, y):
        self.n = 1
        self.x = [x]
        self.y = [y]
        
    def insert(self, x, y):
        if x not in self.x:
            self.x.append(x)
        if y not in self.y:
            self.y.append(y)
        self.n += 1
    
    def new_cor_n(self):
        return len(self.x) * len(self.y) - self.n

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



if N <= 2:
    print(0)
else:
    g = {}
    group_list = []
    for i in range(N):
        new = True
        xi, yi = COR[i]
        if xi in g:
            group = g[xi]
            g[yi] = group
            group.insert(xi, yi)
        elif yi in g:
            group = g[yi]
            g[xi] = group
            group.insert(xi, yi)
        else:
            new_group = Group(xi, yi)
            g[xi] = new_group
            g[yi] = new_group
            group_list.append(new_group)
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)

Submission status: Wrong Answer

Solution code:
class Group:
    
    def __init__(self, x, y):
        self.n = 1
        self.x = [x]
        self.y = [y]
        
    def insert(self, x, y):
        if x not in self.x:
            self.x.append(x)
        if y not in self.y:
            self.y.append(y)
        self.n += 1
    
    def new_cor_n(self):
        return len(self.x) * len(self.y) - self.n

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

if N <= 2:
    print(0)
else:
    g = {}
    group_list = []
    for i in range(N):
        new = True
        xi, yi = COR[i]
        for xj, yj in COR[:i]:
            if xi == xj or yi == yj:
                group = g[(xj, yj)]
                g[(xi, yi)] = group
                group.insert(xi, yi)
                new = False
                break
        if new:
            new_group = Group(xi, yi)
            g[(xi, yi)] = new_group
            group_list.append(new_group)
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)

Submission status: Wrong Answer

Solution code:
N = int(input())
cor = [tuple((map(int, input().split()))) for _ in range(N)]

def rectangular():
    if N <= 2:
        return 0
    s = 0
    for i in range(N):
        xi, yi = cor[i]
        for j in range(i+1, N):
            xj, yj = cor[j]
            if xi == xj:
                for xk, yk in cor[j+1:]:
                    if yi == yk:
                        if (xk, yj) in cor:
                            continue
                        cor.append((xk, yj))
                        s += 1
                    elif yj == yk:
                        if (xk, yi) in cor:
                            continue
                        cor.append((xk, yi))
                        s += 1
            elif yi == yj:
                for xk, yk in cor[j+1:]:
                    if xi == xk:
                        if (xj, yk) in cor:
                            continue
                        cor.append((xj, yk))
                        s += 1
                    elif xj == xk:
                        if (xi, yk) in cor:
                            continue
                        cor.append((xi, yk))
                        s += 1
    return s

print(rectangular())

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class DGraph:
    def __init__(self, n, edges):
        self._vertice = [{} for _ in range(n)]
        for e in edges:
            self._vertice[e[0]][e[1]] = e[2] if len(e) == 3 else 1

    def __len__(self):
        return len(self._vertice)

    def edges(self, n=None):
        srcs = range(len(self)) if n is None else [n]
        return sum([[(s, d, c) for d, c in self._vertice[s].items()] for s in srcs], [])

    def transpose(self):
        tedges = [(t, f, c) for f, t, c in self.edges()]
        return DGraph(len(self), tedges)

    def cost(self, src, dst):
        return self._vertice[src].get(dst, float('inf'))

class Graph(DGraph):
    def __init__(self, n, edges):
        nd_edges = edges + [(d, s, c) for s, d, c in edges]
        super().__init__(n, nd_edges)

    def transpose(self):
        return self


def solve(N: int, x: "List[int]", y: "List[int]"):
    xs = {v:i for i, v in enumerate(set(x))}
    ys = {v:i for i, v in enumerate(set(y), len(xs))}
    
    n = len(xs) + len(ys)
    es = [(xs[cx], ys[cy], 1) for cx, cy in zip(x, y)]
    g = Graph(n, es)

    visited = [False] * len(g)
    def dfs(g, src):
        nonlocal visited
        stack = [(src, 0)]
        while stack:
            n, c = stack.pop()
            if visited[n]:
                continue
            visited[n] = True

            for _, d, _ in g.edges(n):
                #yield d
                stack.append((d, c + 1))
            yield n, c

    def _f(i):
        ls = list(i)
        if len(ls) == 0:
            return None

        xc = 0
        yc = 0
        for i, _ in ls:
            if i < len(xs):
                xc += 1
            else:
                yc += 1

        if xc < 2 or yc < 2:
            return None

        return xc * yc

    l = [v for v in [_f(dfs(g, i)) for i in range(n)] if v is not None]
    acc = 0 if len(l) == 0 else sum(l)
    acc -= N

    return max(acc, 0)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]" 
    y = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    result = solve(N, x, y)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


class DGraph:
    def __init__(self, n, edges):
        self._vertice = [{} for _ in range(n)]
        for e in edges:
            self._vertice[e[0]][e[1]] = e[2] if len(e) == 3 else 1

    def __len__(self):
        return len(self._vertice)

    def edges(self, n=None):
        srcs = range(len(self)) if n is None else [n]
        return sum([[(s, d, c) for d, c in self._vertice[s].items()] for s in srcs], [])

    def transpose(self):
        tedges = [(t, f, c) for f, t, c in self.edges()]
        return DGraph(len(self), tedges)

    def cost(self, src, dst):
        return self._vertice[src].get(dst, float('inf'))

class Graph(DGraph):
    def __init__(self, n, edges):
        nd_edges = edges + [(d, s, c) for s, d, c in edges]
        super().__init__(n, nd_edges)

    def transpose(self):
        return self


def solve(N: int, x: "List[int]", y: "List[int]"):
    xs = {v:i for i, v in enumerate(set(x))}
    ys = {v:i for i, v in enumerate(set(y), len(xs))}
    
    n = len(xs) + len(ys)
    es = [(xs[cx], ys[cy], 1) for cx, cy in zip(x, y)]
    g = Graph(n, es)

    visited = [False] * len(g)
    def dfs(g, src):
        nonlocal visited
        stack = [(src, 0)]
        while stack:
            n, c = stack.pop()
            if visited[n]:
                continue
            visited[n] = True

            for _, d, _ in g.edges(n):
                #yield d
                stack.append((d, c + 1))
            yield n, c

    def _f(i):
        ls = list(i)
        if len(ls) == 0:
            return None

        if sum(sorted([c for _, c in ls], reverse=True)[:2]) < 3:
            return None

        xc = 0
        yc = 0
        for i, _ in ls:
            if i < len(xs):
                xc += 1
            else:
                yc += 1

        return xc * yc

    l = [v for v in [_f(dfs(g, i)) for i in range(n)] if v is not None]
    acc = 0 if len(l) == 0 else sum(l)
    acc -= N

    return max(acc, 0)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]" 
    y = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    result = solve(N, x, y)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
from collections import deque


def solve(N: int, X: "List[int]", Y: "List[int]"):
    adj = defaultdict(list)
    done = set()
    for x, y in zip(X, Y):
        xnode = (x, 0)
        ynode = (y, 1)
        adj[xnode].append(ynode)
        adj[ynode].append(xnode)

    points_to_add = 0    
    for x, y in zip(X, Y):
        xnode = (x, 0)
        ynode = (y, 1)
        if xnode in done or ynode in done:
            continue
        x_count = 1
        y_count = 0
        edge_count = 0
        done.add(xnode)
        Q = deque()
        Q.append(xnode)
        while len(Q) > 0:
            node = Q.pop()
            for node_next in adj[node]:
                if node_next in done:
                    continue
                if node_next[1] == 0:
                    x_count += 1
                else:
                    y_count += 1
                edge_count += 1
                Q.append(node_next)
                done.add(node_next)
        points_to_add += x_count * y_count - edge_count
    print(points_to_add)
        
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]" 
    y = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
from collections import deque


def solve(N: int, X: "List[int]", Y: "List[int]"):
    adj = defaultdict(list)
    done = set()
    for x, y in zip(X, Y):
        xnode = (x, 0)
        ynode = (y, 1)
        adj[xnode].append(ynode)
        adj[ynode].append(xnode)

    points_to_add = 0    
    for x, y in zip(X, Y):
        if x in done or y in done:
            continue
        xnode = (x, 0)
        ynode = (y, 1)
        x_count = 1
        y_count = 0
        edge_count = 0
        done.add(xnode)
        Q = deque()
        Q.append(xnode)
        while len(Q) > 0:
            node = Q.pop()
            for node_next in adj[node]:
                if node_next in done:
                    continue
                if node_next[1] == 0:
                    x_count += 1
                else:
                    y_count += 1
                edge_count += 1
                Q.append(node_next)
                done.add(node_next)
        points_to_add += x_count * y_count - edge_count
    print(points_to_add)
        
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]" 
    y = [int()] * (N)  # type: "List[int]" 
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-



class UnionFind():
  def __init__(self):
    self.group = []
  
  def merge(self,i,j):
    ## i <- j
    self.group[j][3] = self.group[i][3]

  def new(self,x,y):
    merge_i = -1
    for i in range(len(self.group)):
      if x in self.group[i][0] or y in self.group[i][1]:
        if merge_i >= 0:
          self.merge(merge_i,i)
        else:
          self.group[i][0].add(x)
          self.group[i][1].add(y)
          self.group[i][2] += 1
          merge_i = i
    if merge_i < 0:
      self.group.extend([[{x},{y},1,len(self.group)]])

  def output(self):
    xyn = [[set(),set(),0] for _ in range(len(self.group))]
    for i in range(len(self.group)):
      ids = self.group[i][3]
      xyn[ids][0] |= self.group[i][0]
      xyn[ids][1] |= self.group[i][1]
      xyn[ids][2] += self.group[i][2]

    ret = 0
    for x,y,n in xyn:
      if len(x)>=2 and len(y)>=2:
        ret += len(x)*len(y)-n
    return ret



def main():
  N = int(input())
  uf = UnionFind()
  for _ in range(N):
    x,y = map(int, input().split())
    uf.new(x,y)
  print(uf.output())

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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: [])
xy = defaultdict(lambda: [])
for x, y in zip(X, Y):
    xy[x].append(y)
    yx[y].append(y)

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

x_counts = defaultdict(int)
for y, xs in yx.items():
    root = uf.find(y)
    x_counts[root] += 1

ans = 0
for y, cnt in x_counts.items():
    ans += uf.size(y) * cnt
ans -= N
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-



class UnionFind():
  def __init__(self):
    self.group = []
  
  def merge(self,i,j):
    ## i <- j
    self.group[i][0] |= self.group[j][0]
    self.group[i][1] |= self.group[j][1]
    self.group[i][2] += self.group[j][2]
    self.group.pop(j)

  def new(self,x,y):
    merge_i = -1
    l,r = [0,len(self.group)]
    while l < r:
      if x in self.group[l][0] or y in self.group[l][1]:
        if merge_i >= 0:
          self.merge(merge_i,l)
          l -= 1
          r -= 1
        else:
          self.group[l][0].add(x)
          self.group[l][1].add(y)
          self.group[l][2] += 1
          merge_i = l
      l += 1
    if merge_i < 0:
      self.group.append([{x},{y},1])

  def output(self):
    ret = 0
    for i in range(len(self.group)):
      print(i,self.group[i])
      x = len(self.group[i][0])
      y = len(self.group[i][1])
      if min([x,y]) >= 2:
        ret += x*y-self.group[i][2]
    return ret



def main():
  N = int(input())
  uf = UnionFind()
  for _ in range(N):
    x,y = map(int, input().split())
    uf.new(x,y)
  print(uf.output())

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-



class UnionFind():
  def __init__(self):
    self.group = []
  
  def merge(self,i,j):
    ## i <- j
    self.group[i][0] |= self.group[j][0]
    self.group[i][1] |= self.group[j][1]
    self.group[i][2] += self.group[j][2]
    self.group.pop(j)

  def new(self,x,y):
    merge_i = -1
    l,r = [0,len(self.group)]
    while l < r:
      if x in self.group[l][0] or y in self.group[l][1]:
        if merge_i >= 0:
          self.merge(merge_i,l)
          l -= 1
          r -= 1
        else:
          self.group[l][0].add(x)
          self.group[l][1].add(y)
          self.group[l][2] += 1
          merge_i = l
      l += 1
    if merge_i < 0:
      self.group.append([{x},{y},1])

  def output(self):
    ret = 0
    for i in range(len(self.group)):
      print(i,self.group[i])
      x = len(self.group[i][0])
      y = len(self.group[i][1])
      if x*y >= 4:
        ret += x*y-self.group[i][2]
    return ret



def main():
  N = int(input())
  uf = UnionFind()
  for _ in range(N):
    x,y = map(int, input().split())
    uf.new(x,y)
  print(uf.output())

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
nmax = 2*10**5
nhalf = 10**5
# nmax = 20
# nhalf = 10
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)
# 木をBFSをする
used = [False] * nmax
used[x-1] = True # 始めどこから行くか
q = deque([x-1])
cnt_1 = 0 #前半の連結
cnt_2 = 0 #後半の連結
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
# print(cnt_1,cnt_2)
print(max(cnt_1*cnt_2-N,0))

Submission status: Wrong Answer

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(2 * e5) :
    tmp = 0
    if not visited[i] :
        queue = [i]
        visited[i] = True
        tmp += 1
        while queue :
            q = queue.pop()
            for j in v[q] :
                if not visited[j] :
                    visited[j] = True
                    queue.append(j)
                    tmp += 1
    ret += (tmp * tmp) // 4
                    
print(ret - N)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy_s = {}
for _ in range(N):
  x,y = map(int,input().split())
  if x in xy_s:
    xy_s[x].append(y)
  else:
    xy_s[x] = [y]
xy_list = list(xy_s.items())
answer = 0
for i in range(len(xy_list)-1):
  for j in range(1,len(xy_list)):
    a = len(set(xy_list[i][1])&set(xy_list[j][1]))
    b = len(xy_list[i][1]) + len(xy_list[j][1]) - a * 2
    answer += a*b
print(answer)

Submission status: Wrong Answer

Solution code:
N = int(input())
xy_s = {}
for _ in range(N):
  x,y = map(int,input().split())
  if x in xy_s:
    xy_s[x].append(y)
  else:
    xy_s[x] = [y]
xy_list = list(xy_s.items())
answer = 0
for i in range(len(xy_list)-1):
  for j in range(1,len(xy_list)):
    a = len(set(xy_list[i][1])&set(xy_list[j][1]))
    b = len(xy_list[i][1]) + len(xy_list[j][1]) - a * 2
    answer += a*b
print()

Submission status: Wrong Answer

Solution code:
N = int(input().strip())

X = {}
Y = {}

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

count = 0

for x, y_set in X.items():
  x_set = set()
  for y in list(y_set):
    x_set |= Y[y]

  for _x in x_set:
    if _x == x: continue
    _y_set = X[_x]
    if len(_y_set) < 2: continue
    count += len(_y_set - y_set)
    y_set |= _y_set

print(count)