The maximum matching of a graph is the largest possible set of edges in which no two edges share a common vertex.
Bipartite graphs are graphs whose nodes can be divided into two sets A and B such that each edge in the graph has one endpoint in A and one endpoint in B. In these graphs, the maximum matching problem can be perfectly solved in polynomial time using maximum flow algorithms.
In this problem you will be given a graph that is almost bipartite and you will have to calculate the maximum matching of that graph. An almost bipartite graph is a graph whose nodes can be divided into two sets A = {a0,...,anA-1} and B = {b0,...,bnB-1} such that all edges have one endpoint in A and one endpoint in B with the exception of the edges from ai to ai+1 that exist for every i between 0 and nA-2, inclusive, and the edges from bi to bi+1 that allways exist for every i between 0 and nB-2, inclusive.
You will be given nA and nB as two ints. The set of edges that have one endpoint in A and one endpoint in B is given as two int[]s edgesA and edgesB. The ith edge has one endpoint aedgesA[ i ] and one endpoint bedgesB[ i ]. Since they are always part of the graph, edges with two endpoints in the same set are implicit. Return the size of the maximum set of edges in this graph that do not share a vertex.
|