CHEFAFD - Editorial

dec16
hamiltonian
hopcroft-karp
matching
maxflow

#1

PROBLEM LINK:#

Practice
Contest

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.

RELATED PROBLEMS:#