Buonasera a tutti,
premetto di non essere molto esperto in quanto a grafi, ma ho provato a fare l’esercizio ponti (https://training.olinfo.it/#/task/ponti/statement).
Ho ottenuto 5/100 con 9 testcase corretti su 20.
Allego il mio codice qui, qualcuno saprebbe dirmi come migliorarlo?
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
struct Nodo {
vector<int> ne; //next elements
};
int N, M;
Nodo g[10001];
bool marca[10001];
bool found[10001];
bool trova(int a, int b) {
queue<int> co;
co.push(a);
marca[a]=true;
do {
int n=co.front();
co.pop();
found[n]=true;
for(int i=0; i<g[n].ne.size(); i++)
{
int tmp = g[n].ne[i];
if(marca[tmp])
continue;
if(tmp==b)
return true;
co.push(tmp);
marca[tmp]=true;
}
} while(!co.empty());
return false;
}
int main() {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
scanf("%d %d", &N, &M);
int u, v;
for(int i=0; i<M; i++)
{
scanf("%d %d", &u, &v);
g[u].ne.push_back(v);
g[v].ne.push_back(u);
}
int conta=0;
int num=u;
for(int i=0; i<N; i++)
{
if(i==num || found[i])
continue;
if(!trova(num, i)) { //se non la trovo costruisco una strada
g[num].ne.push_back(i);
g[i].ne.push_back(num);
conta++;
//smarco tutto
for(int j=0; j<=N; j++) marca[j]=false;
}
}
printf("%d\n", conta);
return 0;
}
Spiegazione codice:
- il grafo è un vettore di nodi (per ogni nodo c’è un vettore ne nel quale sono contenuti i numeri dei nodi collegati)
- il vettore marca è il vettore dei nodi visitati (per evitare di passare due volte su uno stesso nodo)
- il vettore found tiene conto dei nodi già visitati, serve per ottimizzare i tempi
- dopo avere inizializzato il grafo prendo un numero num a caso (l’ultimo che rimane in u) fra quelli presenti in input.txt e faccio un for che va da 0 a N in cui:
-per ogni elemento verifico con la funzione trova() se esiste un collegamento fra il nodo num e il nodo i
-se non esiste un collegamento lo creo modificando il grafo e incremento la variabile conta (che stamperò da ultimo)
-la funzione trova() fa un BFS (o almeno credo che lo sia
). Restituisce true se il collegamento fra a e b è presente, altrimenti false
Qualche suggerimento?