Acest site foloseşte cookies. Navigând în continuare, vă exprimaţi acordul asupra folosirii cookie-urilor.

Lista de probleme 168

Filtrare

Dificultate

Operații intrare/ieșire

Etichete

#3451 drumuri_simple_k

Se dă un graf orientat cu n vârfuri și m arce prin lista arcelor și un număr natural k. Afișați în ordine lexicografică drumurile simple din graf care au lungimea egală cu k. Lungimea unui drum este egală cu numărul de arce pe care le conține.

Rezolvă

#3364 Unire

Gigel are un graf cu n noduri și m muchii, care nu este conex. El dorește să afle răspunsul la două întrebări:

1) Care este numărul minim de muchii ce trebuie ađugate astfel încât graful să devină conex?
2) Dacă costul adăugării unei muchii între nodurile a și b este a + b, care este costul total minim al muchiilor care trebuie adăugate astfel încât graful să devină conex?

Rezolvă

#3557 StarDust

O expediție spațială își propune să determine un traseu optim între două sisteme solare din galaxie, în urma căruia să se utilizeze o cantitate minimă de energie pentru propulsie. Determinați costul minim energetic suportat de aceasta, în cazul în care există.

Rezolvă

#3365 DigrafulCTC

Se dă un digraf (graf orientat) cu n noduri numerotate de la 1 la n. Graful componentelor tare conexe se obține astfel: se construiesc componentele tare conexe, apoi fiecare astfel de componentă devine nod în noul graf. Apoi din lista inițială de arce se păstrează în noul graf numai arcele care au extremitățile în componente tare conexe diferite. Să se afișeze listele de adiacență asociate noului digraf.

Folclorul informatic

Rezolvă

#3420 arce_inutile

Se dă un graf orientat cu n vârfuri și m arce prin lista arcelor. Se numește arc inutil un arc cu proprietatea că are extremitățile în componente tare conexe diferite. Afișați numărul de arce inutile și care sunt acestea.

Rezolvă

#3421 ctck

Se dă un graf orientat cu n vârfuri și m arce prin lista arcelor. Se numește arc inutil un arc cu proprietatea că are extremitățile în componente tare conexe diferite. Afișați numărul de arce inutile și care sunt acestea.

Rezolvă

#3422 dmink

Se dă un graf orientat cu n vârfuri și m arce prin lista arcelor și un număr natural k. Afișați vârfurile din graf care se află la distanță k față de vârful 1. Distanța dintre două vârfuri x și y este egală cu lungimea celui mai scurt drum care are ca extremitate inițială pe x și ca extremitate finală pe y

Rezolvă

#3339 disjoint1

Se consideră un graf cu N noduri numerotate de la 1 la N și M operații de trei tipuri:

  • 1 x y – se adaugă în graf muchia (x, y). Dacă muchia există deja, operația nu se efectuează
  • 2 x y – întrebare: nodurile x și y se află sau nu în aceeași componentă conexă?
  • 3 – care este numărul maxim de noduri dintr-o componentă conexă?

Trebuie să răspundeți la toate întrebările de tip 2 și 3.

Folclorul informatic

Rezolvă

#3423 ctcmax

Se dă un graf orientat cu n vârfuri și m arce prin lista arcelor. Afișați componentele tare conexe formate din număr maxim de vârfuri.

Rezolvă

#3450 gegik

Se dă un graf orientat cu n vârfuri și m arce prin lista arcelor și un număr natural k. Afișați vârfurile din graf care au suma gradelor (interior și exterior) egală cu k.

Rezolvă