מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים/הזמנות למסיבה/שאלה

נתונה חברה בת $\displaystyle n$ עובדים: $\displaystyle 1,\ldots n$. החברה היא היררכית: לכל עובד (או עובדת), למעט העומדת בראש החברה, יש בדיוק מנהל (או מנהלת) שאליו הוא כפוף ישירות. רוצים להזמין למסיבה כמה שיותר עובדים מעובדי החברה. כדי למנוע חוסר נעימות, אין להזמין עובד ומנהלו הישיר.

אנא מצא אלגוריתם יעיל למציאת מספר העובדים המירבי שאפשר להזמין. הנח שקיים משתנה גלובלי A ובו זוגות; הזוג $\displaystyle (i,j)$ מציין ש$\displaystyle i$ מנהל את $\displaystyle j$.