Imaginary Grasshopper (troppa memoria)

Ciao a tutti, ho implementato una soluzione per questo problema, in pratica si basa su un dfs modificato, il codice però sottomesso alla piattaforma restituisce 65/100 perché nel subtask 5 viene superata la memoria massima consentita dal problema. Per togliermi un dubbio ho provato anche con un bfs modificato, così non va fuori memoria ma prende tle.

#include <iostream>
#include <list>
#include <stack>
using namespace std;

list<pair<int,int>> liste[100000];
int visitato[100000];
stack <pair<int, int>> pila;
int N, M;

int visita_profondita()
{
	int ris = 1;
	while (!pila.empty())
	{
		pair<int, int> corrente = pila.top();
		pila.pop();
		if (corrente.second == 0)
		{
			for (pair<int, int> next : liste[corrente.first])
			{
				if (!visitato[next.first])
				{
					next.second++;
					pila.push(next);
				}
			}
		}
		else if(!visitato[corrente.first])
		{
			visitato[corrente.first] = true;
			ris++;
			for (pair<int, int> next : liste[corrente.first])
			{
				pila.push(next);
			}
		}
	}
	return ris;
}

int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(false);

	cin >> N >> M;
	for (int i = 0; i < N; i++)
		visitato[i] = false;
	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		liste[a].push_back(make_pair(b,0));
	}
	visitato[0] = true;
	for (pair<int, int> next : liste[0])
	{
		pila.push(next);
	}
	int ris = visita_profondita();
	cout << ris;
	return 0;
}

Aggiungo alla domanda, quando usare bfs e quando dfs? Mi son introdotto all’argomento dei grafi circa una settimana fa e devo ancora capire quando applicare uno e quando l’altro.

L’ho risolto anni fa quindi non ricordo bene e non metto la mano sul fuoco su ciò che segue però direi che sono importanti gli anelli (loop) di lunghezza dispari, compresi gli autoanelli (loop di lunghezza unitaria). In loro assenza sono raggiungibili solo i nodi a distanza pari dal nodo 0.

1 Mi Piace

Ok quindi dovrei fare due bfs, uno che mi controlla quali nodi sono a distanza pari dal nodo 0 ( dal primo bfs escluderei i loop) e uno che mi controlla quanti nodi i loop rendono raggiungibili? perché io l’ho pensata così però mi sembra facendo qualche prova che non cambi tantissimo in termini di tempo. Hai qualche suggerimento? Grazie per l’aiuto

Se può esserti utile, io questo esercizio l’ho risolto con una dfs modificata facendo queste considerazioni:

  • quando visito un nodo posso trovarmi in 2 possibili stati

  • con stato si intende se dal nodo 0 ho percorso un numero pari di archi, quindi in quel momento il nodo attuale è raggiungibile, oppure il numero di archi è dispari e allora in quel momento non lo è (sottolineo in quel momento perchè un nodo può essere visitato prima in uno stato e poi nell’altro)

Anch’io l’ho fatto in questo modo nella mia soluzione ma occupa troppa memoria, forse tu hai preso qualche accorgimento in più?

Il tuo codice non l’ho ancora capito molto bene, ma intanto potresti provare a implementare la dfs ricorsivamente (rispetto alla versione iterativa è molto più semplice e pulita). In questo libro a pagina 118 c’è l’implementazione che uso io di solito: https://cses.fi/book/book.pdf

Eccola implementata ricorsivamente, però prende TLE

#include <iostream>
#include <list>
using namespace std;

list<pair<int, int>> liste[100000];
int visitato[100000];
int N, M;

int visita_profondita(pair<int,int> nodo)
{
	int ris = 0;
	if (nodo.second == 0)
	{
		for (pair<int, int> next : liste[nodo.first])
		{
			if (!visitato[next.first])
			{
				next.second++;
				ris += visita_profondita(next);
			}
		}
	}
	else if (!visitato[nodo.first])
	{
		visitato[nodo.first] = true;
		ris++;
		for (pair<int, int> next : liste[nodo.first])
		{
			ris += visita_profondita(next);
		}
	}
	return ris;
}

int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(false);

	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		liste[a].push_back(make_pair(b, 0));
	}
	int ris = visita_profondita(make_pair(0,1));
	cout << ris;
	return 0;
}

Ho modificato il tuo codice e prende 100. Quando passi su un nodo raggiungibile dalla partenza (nodo.second = 1), lo setti a visitato e non ci passi più (giustamente). Lo stesso ragionamento devi farlo per quando passi su un nodo ma nodo.second = 0, quindi devi creare un altro array per tenere conto di questa cosa e modificare di conseguenza anche la funzione

1 Mi Piace

Oh, grazie mille non ci avevo pensato che potesse rivisitare più volte i nodi dispari

Suggerimento che arriva in ritardo, visto che hai già risolto grazie a quelli di @StoRovinato, è che se un nodo fa parte di un ciclo dispari, tutti i nodi a qualunque distanza da quel nodo diventano raggiungibili (compresi tutti gli altri del ciclo).
Per trovare se un nodo fa parte di un ciclo dispari basta vedere se a quel nodo si arriva in entrambi gli stati suggeriti da @StoRovinato.