حداکثر تطبیق درخت
Problem
به شما یک درخت داده می شود (گراف غیر چرخه ای متصل و بدون جهت) متشکل از n راس.
اندازه حداکثر تطابق آن (مجموعه لبه های غیر مجاور دوتایی) را بیابید.
ورودی:
خط اول شامل عدد n - تعداد رئوس درخت است.
بعد n-1 خط می آید که هر کدام شامل دو عدد a
i و b
i است (1 <= a
i، b
i <= n) - لبه های درخت.
خروجی:
چاپ یک عدد - اندازه حداکثر مطابقت درخت داده شده.
مثال:
<بدن>
| ورودی |
خروجی |
4
1 2
23
3 4 |
2 |
توضیح:
حداکثر تطابق این درخت شامل لبه های 1-2 و 3-4 خواهد بود.