Algorithm to determine the possibility of selecting 1 unique element from n arrays

Question

Have a little bit of a nut to crack. I have the brute force implementation of the algorithm, which is not really that hard, but obviously I want something more efficient.

The problem is as follows:

Imagine you have n arrays, each filled with some values between 1 and n. What I need is to determine whether it's possible to select one element from each of those arrays, such that I select each element from 1 to n exactly one time. A little example: suppose n = 4 and we have these n arrays:

[1,2,3,4]
[1,3]
[2,4]
[3,4]

This combination of arrays would pass the algorithm, since it is possible to (for example) select 1, 3, 2, 4 from each array respectively. Another possibility would be 2, 1, 4, 3. A counter example would be:

[1,2,3]
[3]
[3,4]
[3,4]

Here you clearly see that these input arrays wouldn't pass the algorithm. There is no way that it is possible to select 1 element from each array in such a way that each element is selected once.

As I said, the brute force approach is not that complicated, but I want something more efficient, without going through all possible permutations until I found one that passes the criteria.

Answer 1

This problem could be reduced to Maximum Bipartite Matching, which could be solved by Ford-Fulkerson Algorithm for Maximum Flow Problem:

Let's create a flow graph of 2*n nodes, with the first set of n nodes represent the array, while the next set of n nodes represent values. So there will be an edge from node i in the first set to node j in the second set if and only if inside array i, there contains value j. The capacity for this edge should be 1, which represent that you can only choose one from each array.

After forming this graph, apply the classic algorithm to find the answer.

For the example in the question:

[1,2,3,4]
[1,3]
[2,4]
[3,4]

We can form this graph

The white nodes represent arrays, while the green nodes represent values.