Il testo dice:
Citazione
A numbering is beautiful if, for every node, its edges have the numbers 1, 2, . . . , d in some order
(where d is the degree of the node).
Non mi è chiaro cosa intende quando dice che un nodo di grado d deve avere gli archi …
Qualcuno può spiegare? Grazie
Non so se importa ma esistono soluzioni anche nel caso in cui la condizione del subtask 4 non è verificata.
Come dice il testo, un “numbering” è definito come l’assegnamento ad ogni arco della foresta di un intero positivo. Il testo qui intende che un “numbering” è anche “beautiful” se, per ogni nodo x della foresta, i numeri assegnati agli archi adiacenti ad x sono, in qualche ordine, 1, 2, ..., \deg x.
Confermo che esistono soluzioni anche se la condizione del subtask 4 non è verificata.
Grazie per il chiarimento, stando all’esempio del testo verrebbe da pensare che l’assegnazione di un numero ad un arco sia in base al degree del nodo di degree minore (o anche uguale) fra i due.
Evidentemente mi sbaglio, ma non capisco quale sia il criterio per assegnare questa sequenza di numeri agli archi adiacenti ad un nodo.
Non c’è nessun criterio particolare. Il problema chiede semplicemente se esistono o meno una foresta G=(V,E) e un numbering f: E \to \mathbb{Z}^+ tali che il numbering sia beautiful e ogni nodo abbia il grado specificato in input. Potrebbero esistere più foreste valide e, almeno in linea di principio, più beautiful numbering per la stessa foresta. L’importante è che esista almeno un beautiful numbering per la foresta restituita dal programma.
Ce ne ho messo per capire e hai dovuto spiegarmela due volte, ma alla fine penso di aver visto come effettuare la numerazione quando la condizione del subtask 4 non vale.
Grazie