Hello everybody,

I have seen the name "Systems of Distinct Representatives" a few times in a short period of time so I decided to learn it. I have read about Hall's theorem and some of its applications but the thing is that I don't know some efficient way to find that system of distinct representatives. So the problem goes like this: We are given N sets S1,...,Sn of integers. We are to choose an integer from each set which we call a representative of that set. We want all sets to have different representatives. The best algorithm I know is to build a bipartite graph with sides the sets and the numbers and then the maximum matching will give us an answer. So that's why I learned the Hopcroft-Karp matching algorithm and assuming that the graph is built in O(E) time now I can solve the problem in O(E*sqrt(V)) which is worst case O(N^2*sqrt(N)).

However, I was told that it is possible to solve the problem in O(N^2). I will be really thankful if some of you can explain some more algorithms that can solve the problem faster and give me some problems if possible :)

Thanks in advance! :)