Company: Deshaw_13oct
Difficulty: medium
Maximum Recipes Problem Description Determine the largest set of recipes that can be cooked without violating any precedence notes. Chef Bill wants to prepare a subset of n different recipes for tonight's banquet. His sous-chef supplies m handwritten notes, each stating that one recipe must be completed before another. A note written as a before b means Bill has to finish recipe a strictly earlier than recipe b. Treating each recipe as a vertex and every note as a directed edge a → b forms a dependency graph. Because every recipe appears on the right-hand side of at most one note, every vertex has in-degree ≤ 1. Such a graph is a collection of directed chains and single directed cycles (possibly with chains leading out of them). To make it acyclic, exactly one recipe must be skipped from every directed cycle; a self-loop (a before a) counts as a cycle of length 1 and forces that recipe to be skipped. Your task is to compute the maximum number of recipes Chef Bill can prepare without vi