Se consideră un arbore oarecare având N noduri, numerotate de la 1 la N. Nodurile arborelui se împart în două categorii: active şi inactive. Iniţial toate nodurile sunt inactive. În acest arbore, deplasarea de la nodul i la nodul j este posibilă doar dacă sunt îndeplinite simultan următoarele condiţii:
- nodul j este ascendent sau descendent direct al lui i (tată sau fiu);
- nodul j este inactiv;
După atingerea nodului j, va fi selectat unul dintre fiii inactivi ai săi (dacă există) şi va fi activat, împreună cu subarborele care îl are pe acest fiu drept rădăcină.
Orice drum în acest arbore are ca nod de plecare o frunză (nod terminal în arbore). Definim lungimea unui drum, parcurs în condiţiile de mai sus, ca fiind numărul de deplasări efectuate.
Cerinţă
Scrieţi un program care determină drumul de lungime maximă ce porneşte de la un nod terminal dat. Programul va afişa pentru fiecare nod de pe drum, nodul fiu ce a fost activat.
Date de intrare
Fişierul de intrare activ.in conţine pe prima linie numărul natural N. Următoarele N-1 linii conţin perechi de numere (i,j) cu semnificaţia ″nodul i este fiu al nodului j″. Ultima linie a fişierului de intrare conţine nodul de plecare.
Date de ieşire
Fişierul de ieşire activ.out va conţine pe prima linie numărul natural L reprezentând lungimea drumului maxim. Pe a doua linie se vor scrie L numere naturale, despărţite prin câte un spaţiu, reprezentând nodurile drumului, în ordinea în care acestea au fost traversate, exceptând nodul de plecare. Pe a treia linie, pentru fiecare nod din drumul afişat pe linia anterioară, se va scrie fiul său ales pentru activare. Dacă nodul respectiv nu are fii inactivi se va scrie cifra 0.