Nu aveti permisiuni pentru a descarca fisierul grader_test3.in
Inverseaza reviziile

Diferente pentru problema/drumuri5 intre reviziile #13 si #3

Diferente intre #2 si #3

Diferente intre titluri:

Drumuri5

drumuri5

Diferente intre continut:

== include(page="template/taskheader" task_id="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$.
 
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.

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

Fişierul de intrare $drumuri5.in$ ...

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

În fişierul de ieşire $drumuri5.out$ ...

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 |

| 5 4
1 2
3 2
2 4
4 5
| 3
2 4 5

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
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") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

1407