Enunțul problemei graf, de clasa a 11-a, dată în 2006 la OJI, se găsește pe PbInfo, .campion și InfoArena.

Rezumat graf

Se dă un graf neorientat conex, cu vârfurile etichetate de la 1 la n, precum și două vârfuri distincte, notate cu x și y. Trebuie să determinăm vârfurile care aparțin tuturor lanțurile optime (de lungime minimă) dintre x și y.

Soluție graf

Notăm cu lg(a, b) lungimea unui lanț optim între nodurile a și b. Observăm că un nod c aparține cel puțin unui lanț optim dintre a și b dacă și numai dacă lg(a, b) = lg(a, c) + lg(c, a). De asemenea, dacă nu mai există alte noduri d, cu lg(a, c) = lg(a, d), înseamnă că toate lanțurile optime de la a la b trec prin c.

Așadar, pentru a rezolva problema noastră, trebuie să căutăm toate nodurile ce îndeplinesc cele două condiții. Vom avea nevoie de niște parcurgeri în lățime pentru a calcula distanțele minime dintre noduri. O idee isteață este să facem doar două BFS-uri: Unul din x și altul din y. Asta pentru că orice lanț de a cărui lungime avem nevoie are măcar o extremitate în x sau în y. Ca să recapitulez:

    1. Facem BFS din x și din y, reținând rezultatele în vectorii dpX și dpY.
    2. Pentru fiecare nod i, dacă dpX[i] + dpY[i] == dpX[y], incrementăm frq[dpX[i]] (numărul nodurilor ce se află pe un lanț elementar și cu distanța minimă până la x egală cu dpX[i]).
    3. Parcurgem din nou nodurile pentru a vedea care are frq[dpX[i]] == 1. Acestea sunt nodurile ce aparțin tuturor lanțurilor optime dintre x și y. Le adăugăm la vectorul sol.
    4. Afișăm nodurile găsite la pasul anterior, precedate de numărul lor.

Sursă C++ graf

Dacă ai vreo nedumerire cu privire la problema graf, lasă un comentariu și te voi ajuta 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!