Dance Together

Hard
0/120
Average time to solve is 60m
profile
Contributed by
4 upvotes
Asked in company
Tower Research Capital

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
3 2 4
1 1
1 2
2 1
3 1
Sample Output 1:
1
Explanation Of Sample Input 1:
Test case 1:
For the first test case of sample output 1, as we have two girls, we can pair girl ‘2’ with boy ‘1’, and girl ‘1’ to either boy ‘2’ or ‘3’.
Sample Input 2:
2
2 2 2
1 2
1 1
5 4 4
1 4
2 3
3 2
4 1
Sample Output 2:
1
1
Explanation Of Sample Input 2:
Test case 1:
For the first test case of sample output 2, as boy ‘1’ can pair with both girls, hence we choose either of the girls.
Hint

Can we use the concept of Maximum Bipartite Matching to solve this?

Approaches (1)
Greedy Approach

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
Time Complexity

O(K * sqrt(N + M)) where K is the potential pairs and N and M are the number of boys and girls respectively.


Each iteration of the Hopcroft-Karp algorithm executes the breadth-first search and depth-first search once. This takes O(K) time. Since each iteration of the algorithm finds the maximal set of shortest augmenting paths by eliminating a path from a root to an unmatched edge, there are at most O(sqrt(N + M)) iterations needed in the worst case.

Space Complexity

O(N + M + K) where K is the potential pairs and N and M are the number of boys and girls respectively.


The Hopcroft-Karp algorithm takes O(N + M + K) space in the worst case for the BFS or DFS algorithm.

Code Solution
(100% EXP penalty)
Dance Together
Full screen
Console