Maximum Bipartite Matching
HardGraphBFS
Description
Given a bipartite graph with m left nodes (0..m-1), n right nodes (0..n-1), and a list of edges [u, v] connecting left u to right v, return the size of a maximum matching.
Examples
Input:
m = 3, n = 3, edges = [[0,0],[0,1],[1,0],[2,2]]Output:
3Explanation:
Perfect matching exists.
Input:
m = 2, n = 2, edges = [[0,0],[0,1]]Output:
1Explanation:
Only one left can match.
Input:
m = 1, n = 1, edges = []Output:
0Explanation:
No edges.
Constraints
- •
1 ≤ m, n ≤ 100 - •
0 ≤ edges.length ≤ 1000