‎$n$‎ نفر برای کار در یک اداره انتخاب شده‌اند. این ‎$n$‎ نفر با اعداد ‎۱‎ تا ‎$n$‎ شماره گذاری شده‌اند. هر یک از این ‎$n$‎ نفر مجموعه‌ای از قابلیت‌ها دارد. هر مجموعه قابلیت زیرمجموعه‌ای از ‎$\{1,\ldots,m\}$‎ است.

یک سلسله مراتب اداری، روشی برای نسبت دادن یک رئیس به بعضی افراد اداره است به طوری که اگر فرد ‎$a$‎ رئیس فرد ‎$b$‎ باشد، قابلیت‌های ‎$b$‎ باید زیرمجموعه‌ی سره قابلیت‌های ‎$a$‎ باشد (مجموعه قابلیت‌هایشان نباید یکی باشد).

در یک سلسله مراتب اداری، یک فرد مدیر ارشد است اگر رئیسی نداشته باشد. برای اینکه هماهنگی اداره راحت‌تر باشد می‌خواهیم تعداد مدیران ارشد کمینه باشند.

الگوریتمی با زمان اجرای از ‎$O(mn)$‎ ارائه کنید که با گرفتن مجموعه‌ی قابلیت‌های همه‌ی افراد، یک سلسله مراتب اداری بیابد که کمترین تعداد مدیر ارشد را دارد. خروجی الگوریتم باید ‎$n$‎ عدد باشد: عدد ‎$i$‎ ام شماره‌ی رئیس فرد ‎$i$‎ است، یا صفر است اگر او رئیسی ندارد.

• سوال بعد
• سوال قبل