== include(page="template/taskheader" task_id="drumuri5") ==
Poveste şi cerinţă...
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$.
h2. Cerinta
Dându-se cele două numere $N$ si $M$ cât si arcele grafului, să se afle care sunt nodurile populare din graf.
h2. Date de intrare
Fişierul de intrare $drumuri5.in$ ...
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$.
h2. Date de ieşire
În fişierul de ieşire $drumuri5.out$ ...
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.
h2. 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
h2. Exemplu
table(example). |_. drumuri5.in |_. drumuri5.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 4
1 2
3 2
2 4
4 5
| 3
2 4 5
|
h3. 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$.
== include(page="template/taskfooter" task_id="drumuri5") ==
== include(page="template/taskfooter" task_id="drumuri5") ==
