Maximum uniqueness in pairs of numbers with a slight constraint

Here's an algorithmic challenge for you,

I have a list of [0..100] pairs of numbers and I need to find the maximum number of unique "left number" while making sure there is no more than 3 of the "right number".

Here's an example

(1, 1)
(2, 1)
(3, 1)
(4, 1)
(5, 1)
(6, 1)
(7, 1)
(1, 2)
(4, 2)
(1, 3)
(2, 3)
(5, 4)

And the result would be: 7. We would take: (3, 1), (6, 1), (7, 1), (1, 2), (4, 2), (2, 3) and (5, 4).

For whatever reason I can't seem to find any other way than brute forcing it...

Any help is greatly appreciated :)

Solution

You can express this problem as a maximum flow problem:

Make edges of capacity 1 from a source node to each of your left numbers.

Make edges of capacity 3 from each of your right numbers to a sink node.

Make edges of capacity 1 from left number a to right number b for each pair of the form (a, b).

Compute the maximum flow in this network from source to sink.