Programozás‎ > ‎Feladatok‎ > ‎Független‎ > ‎

Megoldás

Algoritmusok

Mindkét megoldás az összefüggő komponensekben kiválasztott csúcsokat maximalizálja.

1. ötlet

A fa összes elsőfokú csúcsát bevesszük a kiválasztott pontok halmazába, a szomszédjaikat nem, és töröljük a szomszédokat, a belőlük induló élekkel együtt. Ezt addig folytatjuk, amíg van elsőfokú csúcs. Végül az összes megmaradt izolált csúcsot is bevesszük.

2. ötlet

A fákat valamelyik pontjukból mélységi bejárással bejárjuk. Minden csúcshoz két értéket számolunk ki:

  • azt, hogy ha őt bevesszük akkor "a belőle induló" legfeljebb hány csúcsa választható
  • és azt, amikor őt nem vesszük be

Kódok

1. ötlet

2. ötlet


Comments