Last Updated: 27 Jun, 2021
Dance Together
Hard
Asked in company
Ninja has recently joined a dance studio as a coach. In the studio, there are N boys and M girls. He can make K potential pairs out of them. He needs to find the maximum number of pairs he can make out of them. Being busy in choreography, he needs your help in finding out the maximum pairs.
Note:
There can be more than one possible set of pairs. In that case, you can return any.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases or queries to be run.
The first line of each test case contains three space-separated integers ‘N’, ‘M’, and ‘K’ denoting the number of boys and girls and potential pairs out of boys and girls.
The next K lines of each test case contain two space-separated integers ‘a’ and ‘b’ denoting the index of boy and index of girl respectively.
Output Format:
For each case, If you return a set of maximum possible pairs then the output will be 1 else it will be 0.
The output of each test case will be printed in a separate line.
Note:
You do not need to input or print anything, and it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 100
1 <= M <= 100
1 <= K <= 100
1 <= a <= N
1 <= b <= M
Timit Limit: 1 sec
Approaches
If we observe the given problem, we can model it in a graph, specifically a bipartite graph - G (X, Y), where ‘X’ is a vertex set of boys and ‘Y’ is vertex set of girls, and there an edge between a girl and boy if they can dance together. Now we just need to find a set with a maximum number of edges such that no two edges in the set have a common vertex. Here, we will use the concept of Maximum Bipartite Matching and the algorithm Hopcroft-Karp Algorithm. Hopcroft-Karp algorithms say that “A matching M is not maximum if there exists an augmenting path. . An augmenting path in a bipartite graph, with respect to some matching, is an alternating path whose initial and final vertices are unsaturated, i.e., they do not belong in the matching. Here, we will find out the augmenting paths. Whenever we get an augmenting path, we will remove it from our maximal matching ‘M’ and add nonmatching edges to ‘M’, and finally return ‘M’.
Algorithm:
- Initialize Maximum Matching M as null.
- Run a loop until there is no augmenting path in Graph.
- Use BFS to build an alternating level graph, rooted at unmatched vertices in the ‘boy’ set
- Augment current matching M with a maximal set of vertex disjoint shortest-length paths using DFS.
- Return M