Problem: 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.

Submission attempts (in order):
# import sys


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


class Group:
    
    def __init__(self):
        self.n = 0
        self.x = []
        self.y = []
        

#         self.x[x] = None


#         self.y[y] = None
        
    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
        for x in group.x:
            self.x[x] = None
        for y in group.y:
            self.y[y] = None
        group.n = 0

def grouping_y(group, y, xcor, ycor):
    ycor[y][1] = True
    group.y.append(y)
    for x in ycor[y][0]:
        if xcor[x][1]:
            continue
        group.n += 1
        grouping_x(group, x, xcor, ycor)
        
def grouping_x(group, x, xcor, ycor):
    xcor[x][1] = True
    group.x.append(x)
    for y in xcor[x][0]:
        if ycor[y][1]:
            continue
        group.n += 1
        grouping_y(group, y, xcor, ycor)
    
if N <= 2:
    print(0)
else:
    xcor, ycor = {}, {}
    for xi, yi in COR:
        if xi in xcor:
            xcor[xi][0].append(yi)
        else:
            xcor[xi] = [[yi], False]
        if yi in ycor:
            ycor[yi][0].append(xi)
        else:
            ycor[yi] = [[xi], False]
    group_list = []
    xcor = sorted(xcor.items())
    for x, v in xcor.items():
        if v[1]:
            continue
        group = Group()
        group_list.append(group)
        grouping_x(group, x, xcor, ycor)
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)

# import sys


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


class Group:
    
    def __init__(self):
        self.n = 0
        self.x = []
        self.y = []
        
    def new_cor_n(self):
        if self.n <= 2:
            return 0
        return len(self.x) * len(self.y) - self.n
        
def grouping(group, x, xcor, ycor):
    xcor[x][1] = True
    group.x.append(x)
    for y in xcor[x][0]:
        if ycor[y][1]:
            continue
        group.n += 1
        ycor[y][1] = True
        group.y.append(y)
        for x_ in ycor[y][0]:
            if xcor[x_][1]:
                continue
            group.n += 1
            x_cor[x_][1] = True
            group.x.append(x_)
            for y_ in xcor[x_][0]:
                if ycor[y_][1]:
                    continue
                group.n += 1
                ycor[y_][1] = True
                group.y.append(y_)
                for x__ in ycor[y_][0]:
                    if xcor[x__][1]:
                        continue
                    group.n += 1
                    grouping(group, x__, xcor, ycor)
    
if N <= 2:
    print(0)
else:
    xcor, ycor = {}, {}
    for xi, yi in COR:
        if xi in xcor:
            xcor[xi][0].append(yi)
        else:
            xcor[xi] = [[yi], False]
        if yi in ycor:
            ycor[yi][0].append(xi)
        else:
            ycor[yi] = [[xi], False]
    group_list = []
    for x, v in xcor.items():
        if v[1]:
            continue
        group = Group()
        group_list.append(group)
        grouping(group, x, xcor, ycor)
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)

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


class Group:
    
    def __init__(self):
        self.n = 0
        self.x = []
        self.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]
                if group2 is group1:
                    pass
                else:
                    for xk in group2.x:
                        xg[xk] = group1
                    for yk in group2.y:
                        yg[yk] = group1
                    group1.join(group2)
            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)

F-Must_Be_Rectangular
Python 3  
File
Edit
View
Insert
Cell
Kernel
Widgets
Help
1
N = int(input())
2
COR = [tuple((map(int, input().split()))) for _ in range(N)]
3
​
8
1 1
2 1
3 1
1 2
2 6
4 4
5 3
5 4
)
1
class Group:
2
    
3
    def __init__(self, x, y):
4
        self.n = 1
5
        self.x = [x]
6
        self.y = [y]
7
        
8
    def insert(self, x, y):
9
        if x not in self.x:
10
            self.x.append(x)
11
        if y not in self.y:
12
            self.y.append(y)
13
        self.n += 1
14
    
15
    def new_cor_n(self):
16
        if self.n == 0:
17
            return 0
18
        return len(self.x) * len(self.y) - self.n
19
​
20
    def join(self, group):
21
        self.n += group.n
22
        self.x.extend(group.x)
23
        self.x = list(set(self.x))
24
        self.y.extend(group.y)
25
        self.y = list(set(self.y))
26
        group.n = 0
27
​
28
​
29
if N <= 2:
30
    print(0)
31
else:
32
    xg, yg = {}, {}
33
    group_list = []
34
    for xi, yi in COR:
35
        if xi in xg:
36
            if yi in yg:
37
                xg[xi].join(yg[yi])
38
            group = xg[xi]
39
            yg[yi] = group
40
            group.insert(xi, yi)
41
        elif yi in yg:
42
            group = yg[yi]
43
            xg[xi] = group
44
            group.insert(xi, yi)
45
        else:
46
            new_group = Group(xi, yi)
47
            xg[xi] = new_group
48
            yg[yi] = new_group
49
            group_list.append(new_group)
50
    s = 0
51
    for group in group_list:
52
        s += group.new_cor_n()
53
    print(s)
5


# import sys



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


class Group:
    
    def __init__(self):
        self.n = 0
        self.x = []
        self.y = []
        
    def new_cor_n(self):
        return len(self.x) * len(self.y) - self.n
        

def grouping(group, x, xcor, ycor):
    x_list = []
    group.x.append(x)
    for y in xcor[x][0]:
        group.n += 1
        if ycor[y][1]:
            continue
        ycor[y][1] = True
        group.y.append(y)
        for x_ in ycor[y][0]:
            group.n += 1
            if xcor[x_][1]:
                continue
            xcor[x_][1] = True
            x_list.append(x_)
    return x_list

if False:
    print(0)
else:
    xcor, ycor = {}, {}
    for xi, yi in COR:
        if xi in xcor:
            xcor[xi][0].append(yi)
        else:
            xcor[xi] = [[yi], False]
        if yi in ycor:
            ycor[yi][0].append(xi)
        else:
            ycor[yi] = [[xi], False]
    group_list = []
    for i, v in xcor.items():
        if v[1]:
            continue
        group = Group()
        group_list.append(group)
        xcor[i][1] = True
        x_list = [i]
        while True:
            new_x_list = []
            for x in x_list:
                new_x_list += grouping(group, x, xcor, ycor)
            if new_x_list == []:
                break
            x_list = new_x_list
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)


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)

# import sys


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


class Group:
    
    def __init__(self):
        self.n = 0
        self.x = []
        self.y = []
        
    def new_cor_n(self):
        if self.n <= 2:
            return 0
        s = len(self.x) * len(self.y) - self.n
        if s < 0:
            s = 0
        return 0


def grouping_y(group, y, xcor, ycor):
    ycor[y][1] = True
    group.y.append(y)
    for x in ycor[y][0]:
        if xcor[x][1]:
            continue
        group.n += 1
        grouping_x(group, x, xcor, ycor)
        
def grouping_x(group, x, xcor, ycor):
    xcor[x][1] = True
    group.x.append(x)
    for y in xcor[x][0]:
        if ycor[y][1]:
            continue
        group.n += 1
        grouping_y(group, y, xcor, ycor)
    
if N <= 2:
    print(0)
else:
    xcor, ycor = {}, {}
    for xi, yi in COR:
        if xi in xcor:
            xcor[xi][0].append(yi)
        else:
            xcor[xi] = [[yi], False]
        if yi in ycor:
            ycor[yi][0].append(xi)
        else:
            ycor[yi] = [[xi], False]
    group_list = []
    for x, v in xcor.items():
        if v[1]:
            continue
        group = Group()
        group_list.append(group)
        grouping_x(group, x, xcor, ycor)
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)

# import sys


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


class Group:
    
    def __init__(self):
        self.n = 0
        self.x = []
        self.y = []
        
    def new_cor_n(self):
        if self.n <= 2:
            return 0
        s = len(self.x) * len(self.y) - self.n
        if s < 0:
            s = 0
        return 0
        
def grouping(group, x, xcor, ycor):
    xcor[x][1] = True
    group.x.append(x)
    for y in xcor[x][0]:
        if ycor[y][1]:
            continue
        group.n += 1
        ycor[y][1] = True
        group.y.append(y)
        for x_ in ycor[y][0]:
            if xcor[x_][1]:
                continue
            group.n += 1
            grouping(group, x_, xcor, ycor)
            
if N <= 2:
    print(0)
else:
    xcor, ycor = {}, {}
    for xi, yi in COR:
        if xi in xcor:
            xcor[xi][0].append(yi)
        else:
            xcor[xi] = [[yi], False]
        if yi in ycor:
            ycor[yi][0].append(xi)
        else:
            ycor[yi] = [[xi], False]
    group_list = []
    for x, v in xcor.items():
        if v[1]:
            continue
        group = Group()
        group_list.append(group)
        grouping(group, x, xcor, ycor)
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)

# import sys


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


class Group:
    
    def __init__(self):
        self.n = 0
        self.x = []
        self.y = []
        
    def new_cor_n(self):
        return len(self.x) * len(self.y) - self.n
        
    
def grouping(group, x, xcor, ycor):
    x_list = []
    xcor[x][1] = True
    group.x.append(x)
    for y in xcor[x][0]:
        if ycor[y][1]:
            continue
        group.n += 1
        ycor[y][1] = True
        group.y.append(y)
        for x_ in ycor[y][0]:
            if xcor[x_][1]:
                continue
            group.n += 1
            xcor[x_][1] = True
            x_list.append(x_)
    return x_list

if N <= 2:
    print(0)
else:
    xcor, ycor = {}, {}
    for xi, yi in COR:
        if xi in xcor:
            xcor[xi][0].append(yi)
        else:
            xcor[xi] = [[yi], False]
        if yi in ycor:
            ycor[yi][0].append(xi)
        else:
            ycor[yi] = [[xi], False]
    group_list = []
    for i, v in xcor.items():
        if v[1]:
            continue
        group = Group()
        group_list.append(group)
        xcor[x][1] = True
        x_list = [i]
        while True:
            new_x_list = []
            for x in x_list:
                new_x_list += grouping(group, x, xcor, ycor)
            if new_x_list == []:
                break
            x_list = new_x_list
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)


# import sys


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


class Group:
    
    def __init__(self):
        self.n = 0
        self.x = []
        self.y = []
        
    def new_cor_n(self):
        return len(self.x) * len(self.y) - self.n
        
    
def grouping(group, x, xcor, ycor):
    x_list = []
    group.x.append(x)
    for y in xcor[x][0]:
        if ycor[y][1]:
            continue
        group.n += 1
        ycor[y][1] = True
        group.y.append(y)
        for x_ in ycor[y][0]:
            if xcor[x_][1]:
                continue
            group.n += 1
            xcor[x_][1] = True
            x_list.append(x_)
    return x_list

if N <= 2:
    print(0)
else:
    xcor, ycor = {}, {}
    for xi, yi in COR:
        if xi in xcor:
            xcor[xi][0].append(yi)
        else:
            xcor[xi] = [[yi], False]
        if yi in ycor:
            ycor[yi][0].append(xi)
        else:
            ycor[yi] = [[xi], False]
    group_list = []
    for i, v in xcor.items():
        if v[1]:
            continue
        group = Group()
        group_list.append(group)
        xcor[x][1] = True
        x_list = [i]
        while True:
            new_x_list = []
            for x in x_list:
                new_x_list += grouping(group, x, xcor, ycor)
            if new_x_list == []:
                break
            x_list = new_x_list
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)


# import sys



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


class Group:
    
    def __init__(self):
        self.n = 0
        self.x = 0
        self.y = 0
        self.xy = {}
        
    def new_cor_n(self):
        return self.x * self.y - self.n
        

def grouping(group, x, xcor, ycor):
    x_list = []
    group.x += 1
    for y in xcor[x][0]:
        if (x, y) not in group.xy:
            group.n += 1
            group.xy[(x, y)] = None
        if ycor[y][1]:
            continue
        ycor[y][1] = True
        group.y += 1
        for x_ in ycor[y][0]:
            if (x_, y) not in group.xy:
                group.n += 1
                group.xy[(x_, y)] = None
            if xcor[x_][1]:
                continue
            xcor[x_][1] = True
            x_list.append(x_)
    return x_list

if N <= 2:
    print(0)
else:
    xcor, ycor = {}, {}
    for xi, yi in COR:
        if xi in xcor:
            xcor[xi][0].append(yi)
        else:
            xcor[xi] = [[yi], False]
        if yi in ycor:
            ycor[yi][0].append(xi)
        else:
            ycor[yi] = [[xi], False]
    group_list = []
    for i, v in xcor.items():
        if v[1]:
            continue
        group = Group()
        group_list.append(group)
        xcor[i][1] = True
        x_list = [i]
        while True:
            new_x_list = []
            for x in x_list:
                new_x_list += grouping(group, x, xcor, ycor)
            if new_x_list == []:
                break
            x_list = new_x_list
    s = 0
    for group in group_list:
        s += group.new_cor_n()
    print(s)


Verdicts: Runtime Error

Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Runtime Error

Accepted