Nu aveti permisiuni pentru a descarca fisierul grader_test9.in
Diferente pentru preoni-2007/runda-finala/solutii intre reviziile #12 si #11
Nu exista diferente intre titluri.
Diferente intre continut:
* _Propozitie 2_: Orice arbore DF care are doar muchii de arbore si muchii inainte indeplineste proprietatea (*).
Daca exista numai muchii de arbore si avem un triplet {$(A B C)$} care respecta ca exista drum de la $A$ la $C$ si de la $B$ la {$C$}, atunci si $A$ si $B$ se afla in lista predecesorilor lui {$C$}. Unul din nodurile $A$ sau $B$ trebuie sa apara primul in aceasta lista, deci vom avea drum fie de la $A$ la {$B$}, fie de la $B$ la {$A$}.
Daca exista numai muchii de arbore si avem un triplet {$(A B C)$} care respecta ca exista drum de la $A$ la $C$ si de la $B$ la {$C$}, atunci si $A$ si $B$ se afla in lista predecesorilor lui C. Unul din nodurile $A$ sau $B$ trebuie sa apara primul in aceasta lista, deci vom avea drum fie de la $A$ la {$B$}, fie de la $B$ la {$A$}.
Cand inseram muchiile inainte nu apar triplete noi pentru care sa existe drum de la $A$ la $C$ si de la {$B$} la {$C$}, deci propozitia a fost demonstrata.
