Lista de probleme 48
Filtrare
#4154
ComponenteTC
Se dă un graf orientat cu n noduri. Să se determine câte componente tare conexe ale grafului sunt formate dintr-un singur nod.
Candale Silviu (silviu)
#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.
- Consola
-
Muresan Ciprian (mcip1977)
- Ciprian Muresan
- ușoară
- Clasa 11 Teoria Grafurilor Probleme diverse cu grafuri orientate
- Algoritmul lui Kosaraju
#4162
DrumuriMinime
Se consideră un graf orientat cu n vârfuri, numerotate de la 1 la n, şi m muchii. Definim distanţa minimă dintre două noduri x şi y ca fiind numărul minim de arce al unui drum elementar care uneşte x cu y.
Se dau k perechi de vârfuri x y. Determinați pentru fiecare pereche distanța minimă dintre x și y.
#4637
ctck11
Se dă un graf orientat cu n vârfuri și m arce prin lista arcelor și un număr natural k. Afișați numărul de componente tare conexe care sunt formate din k vârfuri.
- Consola
-
- Ciprian Muresan
- medie
- Clasa 11 Teoria Grafurilor Probleme diverse cu grafuri orientate
#3421
ctck
Se dă un graf orientat cu n vârfuri și m arce prin lista arcelor și un număr natural k. Afișați numărul de vârfuri ale componentei tare conexe în care se află vârful k.
- Consola
-
- Ciprian Muresan
- ușoară
- Clasa 11 Teoria Grafurilor Probleme diverse cu grafuri orientate
- Algoritmul lui Kosaraju
#4634
Ben10
Atunci când nu se luptă cu Vilgax, Ben și Gwen se joacă pe calculator sau pe telefon. Unul dintre jocurile lor preferate se numește CTC și presupune numărararea vârfurilor din componentele tare conexe ale grafurilor orientate. Mai exact, Ben numără câte componente tare conexe au număr par de vărfuri, iar Gwen numără câte componente tare conexe au număr impar de vârfuri. Stabiliți care dintre cei doi veri câștigă jocul.
- Consola
-
- Ciprian Muresan
- medie
- Clasa 11 Teoria Grafurilor Probleme diverse cu grafuri orientate
#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.
- Consola
-
- Ciprian Muresan
- ușoară
- Clasa 11 Teoria Grafurilor Probleme diverse cu grafuri orientate
- Algoritmul lui Kosaraju
#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
- Consola
-
Pracsiu Dan (dnprx)
- Dan Pracsiu
- medie
- Clasa 11 Teoria Grafurilor Probleme diverse cu grafuri orientate
- Algoritmul lui Kosaraju
#580
Roy-Warshall
Se dă lista arcelor unui graf orientat. Construiți matricea drumurilor, folosind algoritmul lui Roy-Warshall.
#584
Anunt
Într-o clasă sunt n elevi, numerotați de la 1 la n, iar unii dintre ei pot cunoaște numerele de telefon ale altor elevi. Dirigintele dorește să-i anunțe pe elevi despre un eveniment deosebit și pentru aceasta vrea să transmită informația unui singur elev din clasă, urmând ca acesta să-și anunțe colegii cărora le cunoaște numărul de telefon, aceștia să-și anunțe colegii cărora le cunosc numărul de telefon etc, astfel încât toți elevii să afle informația respectivă.
Determinați care sunt elevii din clasă care pot fi anunțați inițial astfel încât, toți elevii să fie în cele din urmă informați.