پیاده سازی گراف دوبخشی با c++

---

شرح پروژه

در یک خانه ی دانشجویی، NN دوست با هم زندگی می کنند. از آنجایی که در این خانه خبری از شام خوابگاه نیست،! هرشب باید یک نفر برای همه شام بپزد. فرض کنید که میخواهید برای NN شب آینده یک برنامه تنظیم کنید که هر فرد دقیقاً یک شب آشپزی کند تا عدالت رعایت شود.

از طرف دیگر، می دانیم که هر فرد در چه شب هایی وقت آشپزی کردن ندارد! (به دلیل خسته بودن، داشتن امتحان، تماشای فوتبال و ...). اگر NN دوست را با {f_1,f_2, \dots, f_N}f1​,f2​,…,fN​ نشان دهیم و شبها را با {d_1,d_2, \dots, d_N}d1​,d2​,…,dN​ نشان دهیم و فرض کنیم که فرد f_ifi​ در مجموعه شبهای S_i \in {d_1,d_2, \dots, d_N}Si​∈d1​,d2​,…,dN​ وقت آشپزی کردن ندارد، الگوریتمی طراحی و پیاده سازی کنید که تعیین کند آیا امکان تنظیم یک برنامه ی عادلانه وجوددارد که در آن هر فرد دقیقاً یک شب آشپزی کند و هیچ شبی هم بدون آشپز نباشد؟

فرض کنید که اگر مساله جواب داشته باشد، دارای یک جواب یکتا است.

راهنمایی: باید از bipartite graph استفاده کنید.

ورودی

در خط اول آن تعداد افراد NN ذکر شده است.

در NN خط بعدی به ترتیب در هر خط شماره ی شبهایی که فرد iiام نمی تواند آشپزی کند با یک فاصله از هم جدا شده اند. اگر فردی در همه شبها امکان آشپزی داشته باشد، در سطر مربوط به این فرد عدد صفر وارد شده است.

خروجی

در خط اول آن کلمه ی YES یا NO بسته به اینکه برنامه ی عادلانه وجوددارد یا نه چاپ می شود.

در صورت وجود برنامه ی عادلانه، در NN خط بعدی به ترتیب شمار ه ی شبی که فرد iiام باید غذا بپزد، آمده است.

مثال ورودی نمونه ۱ 5 3 4 5 2 3 4 5 3 5 2 3 5 1 Plain text Copy

مثلا سطر دوم بیانگر این است که فرد اول در شبهای 3 و 4 و 5 نمیتواند آشپزی کند، اما در شبهای 1 و 2 امکان آشپزی دارد.

خروجی نمونه ۱ YES 2 1 5 3 4 Plain text Copy

در این مثلا فرد 1 تا 5 به ترتیب در شبهای 2، 1، 5، 3 و 4 (از راست به چپ) آشپزی خواهند کرد.

ورودی نمونه ۲ 4 0 1 2 3 1 2 1 2 Plain text Copy خروجی نمونه ۲ NO Plain text Copy ارسال پاسخ برای این سؤال

مهارت ها و تخصص های مورد نیاز

---

---