Ponti - output non corretti


#1

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 :sweat_smile:). Restituisce true se il collegamento fra a e b è presente, altrimenti false

Qualche suggerimento?


#2

Suggerirei di trovare in quanti sottoinsiemi di nodi si è scisso il grafo, dove per sottoinsieme di nodi intendo un insieme di nodi connessi direttamente o indirettamente fra loro.
Nell’esempio abbiamo 3 sottoinsiemi {3,1},{2,0},{4}
Dopodiché il problema è (quasi) risolto.


#3

Grazie, ora ci provo


#4

Ok, 100/100, grazie del suggerimento