Buongiorno, stavo provando a risolvere dessert e mi sembrava di aver trovato una soluzione valida, tuttavia faccio solo trenta e non riesco a capire dove sia l’errore.
Il codice e’ il seguente:
#include <assert.h>
#include <stdio.h>
#include <assert.h>
#include <queue>
#include <vector>
#include <iostream>
#include <stdlib.h>
#include <set>
// constraints
#define MAXN 1000000
using namespace std;
// input data
int N, i, j;
int M, L[MAXN],F;
queue<int> Q;
vector<int> adj[MAXN];
int amiciOrdinato[MAXN] = {0};
int ordinato[MAXN] = {0}; // uso 0 per non ordinato, e 1 per ordinato
int main() {
// uncomment the following lines if you want to read/write from files
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int r = 0;
assert(1 == scanf("%d", &N));
for (i = 0; i < N; i++) {
assert(2 == scanf("%d %d", &M, &L[i]));
for (j = 0; j < M; ++j) {
assert(1 == scanf("%d", &F));
adj[F].push_back(i);
}
}
for (i = 0; i < N; i++) {
if (L[i] == 0) {
Q.emplace(i);
}
}
while (not Q.empty()) {
int top = Q.front();
// se abbastanza amici hanno ordinato, ordina
if (L[top] <= amiciOrdinato[top] && ordinato[top]==0) {
++r;
ordinato[top] = 1;
}
Q.pop();
if (L[top] <= amiciOrdinato[top]) {
for (int i : adj[top]) {
if (ordinato[i] == 0) {
// se non ha ancora ordinato
++amiciOrdinato[i];
Q.emplace(i);
}
}
}
}
printf("%d\n", r); // print the result
return 0;
}
L’idea che ho avuto è la seguente:
Creo un vettore di adiacenza adj in cui, adj[i] è un vettore contenente gli indici di tutti quelli che ritengono i un amico. Creo poi una coda Q, un vettore amiciOrdinato, di cui amiciOrdinato[i] mi dice quanti degli amici di i hanno ordinato, e ordinato, di cui ordinato[i] mi dice se i ha ordinato (0 per no e 1 per si).
All’inizio carico nella coda tutti quelli che hanno L=0, ossia possono ordinare subito, e per ogni persona nella coda guardo se abbastanza amici hanno ordinato, nel caso lo faccio ordinare e aumento il numero r di persone che hanno ordinato, inoltre se ordina metto nella coda tutti quelli che lo considerano amico poiché il fatto che abbia ordinato potrebbe far ordinare anche loro.
) è che se