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;
}