A ball is participated by students from Kumpula and students from Viikki. The students of each campus are numbered .
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 from Kumpula and a student from Viikki are willing to dance with each othermax_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 dances with the Viikki student
- The Kumpula student dances with the Viikki student
- The Kumpula student dances with the Viikki student
Notice that each campus has students. For example the Kumpula student and the Viikki student are two different students.