# Problema depura

**URL:** <https://forum.olinfo.it/t/problema-depura/577>\
**Category:** Aiuto\
**Created:** [12 Aprile 2016, 5:13pm UTC](https://forum.olinfo.it/t/problema-depura/577 "2016-04-12T17:13:53Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![kmfrick](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/k/ba9def/32.png) [@kmfrick](https://forum.olinfo.it/u/kmfrick)\
**Post date:** [12 Aprile 2016, 5:13pm UTC](https://forum.olinfo.it/t/problema-depura/577/1 "2016-04-12T17:13:53Z")

</div>

Salve a tutti, ho un dubbio sul problema “depura”  
Per come l’ho pensato, visto che per inserire la sostanza 1 devi inserire prima tutte le sue dipendenze, e prima di inserire le dipendenze devi inserire prima le dipendenze delle dipendenze eccetera, il problema si può vedere come un grafo dove ogni sostanza è un nodo e i figli di ogni nodo sono le dipendenze. A questo punto l’algoritmo risolutivo è una semplice dfs che parte da 1 e aggiunge 1 alla risposta per ogni nodo che visita, ma considera già visitati i nodi corrispondenti alle sostanze già inserite. Ho testato questo algoritmo sulla carta e su altri testcase scritti da me, ma quando lo mando dà tre output non corretti. Ora, sono sicuro di aver fatto qualche errore stupido, ma non riesco a capire dove sia xD potete aiutarmi?

Questo è il mio codice:

```
#include <iostream>
#include <vector>

const int MAXN = 2000;

std::vector<std::vector<int>> G(MAXN);
std::vector<bool> vis(MAXN, false);

int ans;

void dfs(int u) {
    vis[u] = true;
    
    for (int v : G[u]) {
        if (!vis[v]) {
            ans++;
            dfs(v);
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::freopen("input.txt", "r", stdin);
    std::freopen("output.txt", "w", stdout);
    int R, K;
    int a, b, n;
    std::cin >> K >> R;

    for (int i = 0; i < K; i++) {
        std::cin >> a;
        vis[a] = true;
    }

    for (int i = 0; i < R; i++) {
        std::cin >> a >> n;

        for (int j = 0; j < n; j++) {
            std::cin >> b;
            G[a].push_back(b);
        }
    }

    dfs(1);
    std::cout << ans + 1;
    return 0;
}
```

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [13 Aprile 2016, 6:07pm UTC](https://forum.olinfo.it/t/problema-depura/577/2 "2016-04-13T18:07:25Z")

</div>

“Nel caso in cui non sia possibile purificare l’acqua, bisogna restituire il valore S = -1.” 😃

---

<div class="post-metadata">

**Author:** ![Twocondor](https://forum.olinfo.it/user_avatar/forum.olinfo.it/twocondor/32/213_2.png) [@Twocondor](https://forum.olinfo.it/u/Twocondor)\
**Post date:** [13 Aprile 2016, 9:05pm UTC](https://forum.olinfo.it/t/problema-depura/577/3 "2016-04-13T21:05:26Z")

</div>

mi sembra che manca anche il caso "Tale numero  
sara’ S = 0 se la sostanza 1 e gia’ presente nell’acqua