# PBinfo #4819 – aventura – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Gușteru’ a descoperit într-un dulap un vechi joc de aventură, numit Ijnamuj. Jocul inițial pornește de la nivelul 1, iar scopul este completarea a cât mai multor nivele. Fiecare nivel i are asociată o listă L(i) care conține alte nivele din joc. Pentru a completa nivelul i, Gușteru’ va trebui mai întâi să completeze toate nivelele din lista L(i), în orice ordine dorește el. După completarea oricărui nivel, el poate să completeze orice alt nivel a cărui listă conține numai nivele completate. Pentru că jocul începe de la nivelul 1, lista L(1) va fi mereu vidă, adică completarea lui nu este restricționată de niciun alt nivel.

Cerința
Care este numărul maxim de nivele pe care le poate completa Gușteru’?

Date de intrare
Pe primul rând din fișierul de intrare aventura.in se va afla numărul T, care reprezintă numărul de scenarii distincte din test.

Pentru fiecare dintre cele T scenarii, intrarea va fi de forma următoare:


pe primul rând se va afla N, numărul de nivele din scenariu;
pe următoarele N rânduri, se vor afla descrierile celor N liste: fiecare rând va începe cu k[i] (1 ≤ i ≤ N), care reprezintă numărul de nivele din lista nivelului i, urmat de k[i] numere, care reprezintă indicele nivelelor.

Date de ieșire
Pe linia i din fișierul de ieșire aventura.out se va afișa răspunsul la al i-lea scenariu (1 ≤ i ≤ T).

Restricții și precizări

1 ≤ T ≤ 5;
1 ≤ 𝑁 ≤ 500.000;
k[1 ] = 0;
0 ≤ k[i] ≤ N − 1;
i ∉ L(i), pentru oricare 1 ≤ i ≤ N;
Într-un scenariu, k[1] + k[2] + . . . + k[N] ≤ 4×N;
Per totalul celor T scenarii, suma tuturor sumelor k[1] + k[2] + . . . + k[N] nu depășește 5.000.000;
Definim o dependență circulară un șir de nivele a[1], a[2], ... , a[p] , 2 ≤ p ≤ N , cu proprietatea că a[1] ∈ L(a[2]), a[2] ∈ L(a[3]), … , a[p−1] ∈ L(a[p]),  a[p] ∈ L(a[1]).
datorită dimensiunilor mari ale fișierelor, nu au fost adăugate toate testele folosite în concurs!

Subtaskuri:


pentru anumite teste, 1 ≤ N ≤ 10
pentru anumite teste, dependențele circulare sunt de lungime exact 2, N ≤ 2.000
pentru anumite teste, 1 ≤ N ≤ 2.000
pentru restul testelor, fără restricții suplimentare

Exemplu:
aventura.in

2
5
0
1 1
1 2
2 3 5
1 4
6
0
2 4 6
2 2 5
1 3
1 1
1 5
aventura.out

3
3
Explicație
T = 2 deci se rezolvă două scenarii.

În primul scenariu, singurul nivel în care putem ajunge necondiționat este nivelul 1. Nivelul 1 deblochează nivelul 2, care la rândul său deblochează nivelul 3. Nu mai putem debloca nimic, pentru că nivelul 4 este condiționat și de nivelul 3, dar și de nivelul 5, care, la rândul său, este condiționat de nivelul 4. Astfel, putem debloca doar 3 nivele, respectiv nivelele 1, 2 și 3.

Al doilea scenariu se rezolvă similar cu primul. În acest caz putem debloca 3 nivele, respectiv nivele 1, 5 și 6.

## Cod sursă C++

```cpp
// OJI 2025 11-12 Ivan Andrei 
// Aventura ASSERT 1+2+3+4 
#include <fstream>
#include <vector>
#include <queue>
#include <cassert>
using namespace std; 
const int max_size = 5e5 + 5; 
vector <int> nxt[max_size]; 
int deg[max_size], sumall; 
queue <int> q; 
void solve () 
{ 
    int n; 
    scanf("%d", &n);
    assert(n <= 500000); 
    for (int i = 1; i <= n; i++) 
    { 
        nxt[i].clear(); 
    } 
    int sumk = 0; 
    for (int i = 1; i <= n; i++) 
    { 
        int k; 
        scanf("%d", &k); 
        sumk += k; 
        if (k == 0) 
        { 
            q.push(i); 
        } 
        deg[i] = k; 
        assert(deg[i] >= 0); 
        while (k--) 
        { 
            int x; 
            scanf("%d", &x); 
            nxt[x].push_back(i); 
            assert(x != i); 
        } 
    } 
    assert(sumk <= 4 * n); 
    int ans = 0; 
    sumall += sumk; 
    while (!q.empty()) 
    { 
        int nod = q.front(); 
        q.pop(); 
        ans++; 
        for (auto f : nxt[nod]) 
        { 
            deg[f]--; 
            if (deg[f] == 0) 
            { 
                q.push(f); 
            } 
        } 
    } 
    printf("%d", ans); 
    printf("\n"); 
} 
int main () 
{ 
    #ifdef LOCAL 
        freopen("test.in", "r", stdin); 
        freopen("test.out", "w", stdout); 
    #else 
        freopen("aventura.in", "r", stdin); 
        freopen("aventura.out", "w", stdout); 
    #endif 
    int t;
    scanf("%d", &t);
    assert(t <= 5); 
    //t = 1; 
    while (t--) 
    { 
        solve(); 
    } 
    assert(sumall <= 5000000); 
    return 0;    
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4819)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4819/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4819/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)