CSES - Ball

A ball is participated by nn students from Kumpula and nn students from Viikki. The students of each campus are numbered 1,2,,n1,2,\dots,n.

Each dancing pair has one student from Kumpula and one from Viikki, and you know all pairs that are willing to dance with each other. Each student can belong to at most one dancing pair. What is the maximum number of pairs that can be formed?

In a file ball.py, implement the class Ball with the following methods:

  • add_pair declares that a student aa from Kumpula and a student bb from Viikki are willing to dance with each other
  • max_pairs returns the maximum number of dancing pairs
class Ball:
    def __init__(self, n):
        # TODO

    def add_pair(self, a, b):
        # TODO

    def max_pairs(self):
        # TODO

if __name__ == "__main__":
    ball = Ball(4)

    print(ball.max_pairs()) # 0

    ball.add_pair(1, 2)
    print(ball.max_pairs()) # 1

    ball.add_pair(1, 3)
    ball.add_pair(3, 2)
    print(ball.max_pairs()) # 2

    ball.add_pair(2, 1)
    print(ball.max_pairs()) # 3

In the example above, the situation at the end allows three dancing pairs, for instance:

  • The Kumpula student 11 dances with the Viikki student 33
  • The Kumpula student 22 dances with the Viikki student 11
  • The Kumpula student 33 dances with the Viikki student 22

Notice that each campus has nn students. For example the Kumpula student 11 and the Viikki student 11 are two different students.