| Fişierul intrare/ieşire: | drumuri5.in, drumuri5.out | Sursă | ONI 2013 Clasele 11-12 |
| Autor | Alexandru Cazacu | Adăugată de |  Popescu Silviu •crushack |
| Timp execuţie pe test | 0.35 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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
- 1 ≤ N ≤ 150.000
- 1 ≤ M ≤ 300.000
- Pentru 50% din punctaj N ≤ 700, M ≤ 1100
- Pentru 65% din teste, G este aciclic
Exemplu
| drumuri5.in | drumuri5.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.
