Fişierul intrare/ieşire:drumuri5.in, drumuri5.outSursăONI 2013 Clasele 11-12
AutorAlexandru CazacuAdăugată decrushackPopescu Silviu crushack
Timp execuţie pe test0.35 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Drumuri5

Fie G un graf orientat cu N noduri şi M arce. Spunem că nodul Y este accesibil din nodul X dacă se poate ajunge de la X la Y mergând pe arce în sensul corespunzător al acestora. Spunem că nodul X este “popular” dacă pentru fiecare nod Y al grafului G se îndeplineşte cel puţin una din condiţiile:
1. X este accesibil din Y;
2. Y este accesibil din X.

Cerinta

Dându-se cele două numere N si M cât si arcele grafului, să se afle care sunt nodurile populare din graf.

Date de intrare

Prima linie a fişierului drumuri.in conţine numerele N şi M, cu semnificaţia din enunţ . Următoarele M linii conţin câte două numere X şi Y, semnificând faptul că există arc orientat de la X la Y.

Date de ieşire

Prima linie a fişierului drumuri.out conţine numărul NR, reprezentând numărul de noduri populare ale grafului. Următoarea linie va conţine cele NR noduri populare afişate în ordine crescătoare.

Restricţii

  • 1N150.000
  • 1M300.000
  • Pentru 50% din punctaj N700, M1100
  • Pentru 65% din teste, G este aciclic

Exemplu

drumuri5.indrumuri5.out
5 4
1 2
3 2
2 4
4 5
3
2 4 5

Explicaţie

Nodurile 2, 4 şi 5 sunt singurele noduri populare. Nodul 1, spre exemplu, nu este popular deoarece nu este accesibil din 3, iar nici nodul 3 nu este accesibil din 1.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content