Correspondance maximale des arbres
Problem
On vous donne un arbre (un graphe non orienté acyclique connexe) composé de n sommets.
Trouvez la taille de sa correspondance maximale (l'ensemble des arêtes non adjacentes par paires).
Saisie :
La première ligne contient le nombre n - le nombre de sommets dans l'arbre.
Viennent ensuite n-1 lignes, chacune contenant deux nombres a
i et b
i (1 <= a
i, b
i <= n) - bords des arbres.
Sortie :
Imprimer un nombre - la taille de la correspondance maximale de l'arbre donné.
Exemples :
| Entrée |
Sortie |
4
1 2
23
3 4 |
2 |
Explication :
La correspondance maximale de cet arbre inclura les arêtes 1-2 et 3-4.