Problem
Given a N x M bipartite graph, determine which edges can be selected in a perfect matching.
Solution
First, find an arbitrary matching. If an edge is selected in the matching OR contains in any augmenting cycle, output that edge.
To determine whether an edge is in an augmenting cycle, find the SCC in the residual graph. See whether both ends of an edge is in the same SCC.
Trick: N may not equals M. My solution to this is add a dummy node in the left side.
No comments:
Post a Comment