Problem
Size n köşeden oluşan bir ağaç (bağlı, asiklik, yönsüz bir grafik) veriliyor.
Maksimum eşleşmesinin boyutunu bulun (bitişik olmayan ikili kenarlar kümesi).
Giriş:
İlk satır, ağaçtaki köşelerin sayısı olan n sayısını içerir.
Ardından, her biri iki sayı a
i ve b
i içeren n-1 satır gelir (1 <= a
i, b
i <= n) - ağaç kenarları.
Çıktı:
Bir sayı yazdır - verilen ağacın maksimum eşleşmesinin boyutu.
Örnekler:
| Giriş |
Çıktı |
4
1 2
23
3 4 |
2 |
Açıklama:
Bu ağacın maksimum eşleşmesi 1-2 ve 3-4 kenarlarını içerecektir.