PROBLEM LINK:
DIFFICULTY:
HARD
PREREQUISITES:
Bipartite Graph
Maximum Bipartite Matching
Minimum Vertex Cover
Konig’s Theorem
EXPLANATION:
Problem boils down to:
Given a bipartite graph with directed edges, do matching to maximise the edges, but each vertex should either have all incoming or all outgoing edges (not both).
We can solve this problem by making a new bipartite graph, where, vertices on left side in new graph denote the directed edges from left to right in original graph. Vertices on right side in new graph denote the directed edges from right to left in original graph.
In the new graph, edges will be between those vertices which contradict each other. Two vertices contradict each other when both cannot exist in the final matching of the original graph. We need to remove minimum vertices in the new graph such that all contradictions (ie. edges in new graph) are removed.
This is same a minimum vertex cover, which is same as maximum bipartite matching (according to Konig’s Theorem).