Lista de probleme 607

Filtrare

Dificultate

Operații intrare/ieșire


Etichete

#585 Orase

Într-o țară oarecare sunt n orașe, numerotate de la 1 la n, între care există șosele unidirecționale. Președintele țării vrea să facă o vizită electorală prin mai multe orașe în felul următor: aterizează cu elicopterul în orașul p, merge până în orașul q folosind rețeaua de șosele existentă, de unde pleacă cu elicopterul. Din punct de vedere politic unele orașe sunt sigure (conduse de aliați politici ai președintelui), altele sunt nesigure (conduse de adversari), iar președintele dorește să parcurgă numai orașe sigure.

Consilierii președintelui i-au propus mai multe perechi de orașe p q care pot fi alese ca punct de plecare și de sosire pentru vizită. Președintele vă cere să verificați pentru fiecare pereche dată dacă există un drum care să treacă numai prin orașe sigure.

#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.

Se dă lista arcelor unui graf orientat. Construiți matricea drumurilor, folosind algoritmul lui Roy-Warshall.

Se dă un graf orientat cu n noduri. Să se determine câte componente tare conexe are graful dat.

Se dă un graf turneu cu n noduri. Să se determine un drum elementar care să conțină toate nodurile grafului.

Se dă un graf orientat cu n noduri și un nod p. Să se afișeze toate nodurile q ale grafului, diferite de p, cu proprietatea că există cel puțin un drum de la p la q și lungimea drumului minim este pară.

Se dă un graf orientat cu n noduri. Determinați, dacă există, un drum hamiltonian.

Se dă lista arcelor unui graf orientat. Să se afișeze, în ordine lexicografică, toate circuitele de lungime trei.

Se dă lista arcelor unui graf orientat. Să se afișeze, în ordine lexicografică, toate ciclurile de lungime trei.

Într-un grup sunt n persoane, numerotate de la 1 la n și o persoană poate cunoaște alte persoane – relație care nu este reciprocă. Să se determine persoana cea mai cunoscută.