حلالت

فرض کنید $n$ یک عدد طبیعی باشد. از ورودی دو مورد زیر به ما داده می‌شود:

• یک درخت با مجموعه‌ی رأس‌های $\{1, 2, \ldots, n\}$ که حداکثر ۱۳۹۸ برگ دارد.
• مجموعه‌ی $A$ از یال‌ها با رأس‌های $\{1, 2, \ldots, n\}$ که هیچ یک از آن‌ها در درخت گفته شده وجود ندارد.

می‌خواهیم تعدادی از یال‌های مجموعه‌ی $A$ را به درخت اضافه کنیم، طوری که گراف حاصل دوهمبند شود. پاسخ مسئله، کمینه‌ی تعداد یال‌هایی است که اضافه می‌کنیم (اگر دوهمبند کردن گراف ممکن نبود، پاسخ را $-1$ در نظر می‌گیریم). الگوریتمی با زمان چندجمله‌ای ارائه کنید که پاسخ مسئله را پیدا کند.

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