Lista de probleme 2

Se dă o matrice cu R linii şi C coloane de numere distincte de la 1 la R * C. Bemo, personajul emoţional, doreşte să urmărească cel mai bun drum din colţul superior stânga, de coordonate (1, 1), în colţul inferior dreapta, de coordonate (R, C). Un drum este o secvenţă de numere din matrice în care fiecare număr se găseşte în jos sau la dreapta numărului anterior, adică dacă (i, j) este poziţia unui număr de pe un drum, atunci următorul număr poate fi cel de pe poziţia (i + 1, j) sau cel de pe poziţia (i, j + 1). Pentru a determina dacă un drum A este mai bun decât un drum B, numerele fiecărui drum se vor sorta şi se va alege cel mai mic lexicografic.

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.
Dându-se cele două numere N si M cât si arcele grafului, să se afle care sunt nodurile populare din graf.