11159 - Factors and Multiples

Difficulty : medium

Solution Description :

Graph (Maximum bipartite matching or Maximum Matching (DFS)) problem

This is completely a maximum bipartite matching problem. We want to maximum match elements set A to set B, if B[j]%A[i]==0.
If B[j]%A[i]==0 then j is adjacency of i.
Remember, If A[i]=0 then got run time error for B[j]%A[i]. But 0 is a multiple of 0 because, P is a multiple of Q if there is some integer K such that P = K * Q.
You can see the "Hopcroft-Karp" algorithm for Maximum bipartite matching.