un aiuto su ponti isole perchè ho 10/100
~~
#include
#include <stdlib.h>
#include
#include
using namespace std;
const int MAXN=10000;
const int MAXM=100000;
bool visitato[MAXN];
list adj[MAXN]; // array di lista
stack pila; int k;
//Esegue una visità in profondità
void visita (int nodo)
{ pila.push(nodo);
while (!pila.empty())
{ int corrente=pila.top();
pila.pop();
if (visitato[corrente]==false)
{ visitato[nodo]=true; k=k+1;
for (list :: iterator i=adj[corrente].begin(); i!=adj[corrente].end();i++)
pila.push(*i);
}
cout<<k;
}
}
int main()
{ freopen(“input.txt”,“r”,stdin);
freopen(“output.txt”,“w”,stdout);
int N,M;
cin>>N>>M;
for (int i=0;i<N; i++)
visitato[i]=false;
int da[M]; int a[M];
for (int i=0;i<M; i++)
{ cin>>da[i]>>a[i];
adj[a[i]].push_back(da[i]);
adj[da[i]].push_back(a[i]);
}
visita(0);
}
~~
Devi fare una funzione che visita i nodi adiacenti, a cui trasferisci un nodo di partenza, fai un contatore che conta quante volte richiami quella funzione per visitare tutti i nodi
Diciamo che ci sono alcune cose da rivedere:
-
Nella funzione visita()
-
Penso sia una svista ma dove c’è scritto visitato[nodo]=true; dovrebbe essere visitato[corrente]=true;
-
Non puoi mettere nella pila tutti i nodi collegati al nodo corrente ma solo alcuni che rispettano una certa condizione, altrimenti la maggior parte delle volte si crea un ciclo infinito.
-
Ti faccio poi notare che ad ogni iterazione del while tu scrivi sul file di output il valore della variabile k, e finita l’esecuzione del codice avrai apparentemente un numero ma in realtà sono i diversi valori di k non spaziati che tu stampi
Infine per arrivare alla soluzione bisogna fare una piccola osservazione.
Per aiutarti ti lascio questo input:
6 3
0 1
2 3
4 5
che rappresenta il seguente grafo:
e l’output sarà:
2
1 Mi Piace
