.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » drumuri2

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
drumuri2


Timp maxim de execuţie / test:
0.6s
Memorie totala disponibilă / stivă:
64MB / 8MB

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 dintre condiţiile:
1. X este accesibil din Y;
2. Y este accesibil din X.

Cerinţă

Dându-se cele două numere N şi M precum şi arcele grafului, să se afle care sunt nodurile populare din graf.

Date de intrare

Prima linie a fişierului drumuri2.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 de la X la Y.

Date de ieşire

Prima linie a fişierului drumuri2.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 ≤ 60 500
1 ≤ M ≤ 105 000
• Pentru 65% din teste, G este aciclic

Exemple

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

autor: Alexandru Cazacu
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la ONI 2013: split, momente, gradina1, secvente2, flori2, romb1, cumpanit, spider, zone, taxa, ausoara, confuzie, xnumere, bemo, aranjare2, showroom, cntgcd
De acelaşi autor: ripstick, sdmin, triunghi5, descompunere, vectori1
Despre graf: gropi, tgv, matrice2, miniasm, picnic, mere, circuit, soldati, arce, conflicte, desen, robot, furtuna, net, cuvinte, excursie, cadere, pioni, reinvent, kreg, flood, croco, johnie, matrice, arthur, kimberley, ro, sol, caravane, bete, honest, police, pcod, zmeu, auto2, grazing, datorii, trafic, sponsori, monede1, apm, bile1, caini, masina1, bomboane, turn1, shgraf, paintball, program1, tgraf, kgb, algola, felinar, joc6, tric, homeless, promo, turism, casute, joc10, prieteni1, traseu, zapezi, litoral, lover, trip, garaj, ziduri, tv, pact, echipe1, vitale, spion, trasee, bcolor, scara2, lant, ab3, soc, team, gard, rsp, graf, mexc, dep, albinuta1, atac2, cabane, drumuri, tj, grade, jungla, lanterna, magic5, coment, urgenta, fazan, lanturi, cfr, site, traseu1, trmv, graphgame, minuni, telefon, ubergraf, carray, pestera, chei, arbgraf, war, fluviu, drumuri1, entries, ubuntzei, pack, fotbal1, pamant, dag, razboi, benzina2, wg, neconex, asfalt1, kubus2, module, progresii, dfs, prieteni3, megascoala, grafxy, dineu, vot1, biperm, nrgraf, cristal, cartite, copaci3, dragoni, nuclee
Despre Sortare topologică: dezbateri, honest, pitici1
Despre conexitate: arce, flood, matrice, shgraf, trip, pact, echipe1, vitale, spion, bcolor, mexc, dep, fazan, cfr, chei, teme, entries, pamant, neconex, module, cristal, nuclee
surse trimise | ajutor