PROBLEM LINK:#
Author : Le Xuan Manh
Tester : Le Xuan Manh
Editorialist : Triveni Mahatha
DIFFICULTY:#
MEDIUM
PREREQUISITES:#
Matching
Hopcroft Carp Algorithm
PROBLEM:#
Given a special directed graph, check if complete matching exist.
QUICK EXPLANATION:
Create a bipartite graph Gn x n = (A, B, E). For each edge from node u to v, create an edge in G from node u in A to node v in B. Check of perfect matching exists in G.
DETAILS:#
AUTHOR’S AND TESTER’S SOLUTIONS:#
Author’s solution can be found here.
Tester’s solution can be found here.