Problem #219

drumuri2

Time limit: 0.4s
Memory limit: 64MB
Input: drumuri.in
Output: drumuri.out

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.

Cerință

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 și precizări

  • 1 ≤ N ≤ 150 000
  • 1 ≤ M ≤ 300 000
  • Pentru 50% din punctaj N ≤ 700, M ≤ 1100
  • Pentru 65% din teste, G este aciclic

Exemplu:

drumuri.in

5 4
1 2
3 2
2 4
4 5

drumuri.out

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.

General info

Uploader: liviu

Author: Alexandru Cazacu

Source: ONI 2013 XI-XII: Ziua 2 Problema 2

Submissions