Ciao a tutti,
Ho recentemente studiato l’algoritmo di Tarjan per risolvere abc_paper. In generale, ho capito come funziona l’algoritmo e l’ho implementato. Purtroppo, la mia soluzione non ha funzionato. Dopo ore di ricerca (ed un utilissimo video su youtube) ho capito che mancava una singola riga di codice perché l’algoritmo facesse 100/100:
low[v] = id[n];
Questa va inserita mentre vengono rimossi dallo stack i nodi che fanno parte di una SCC, una volta arrivati ricorsivamente alla sua testa.
Non riesco a capire perché questo sia necessario. Il low viene già propagato durante la dfs se il nodo fa parte dello stack. Lascio qui il codice della dfs come riferimento.
void dfs(int n, vi adj[], int pre) {
// inizializzo id = low
id[n] = low[n] = counter++;
// aggiungo il nodo allo stackk
stackk.push(n);
onStack[n] = 1;
// controllo vicini
for(int vicino: adj[n]) {
// se non visitato visito
if(id[vicino] == -1) dfs(vicino, adj, n);
// controllo se fa parte stessa SCC
if(onStack[vicino] == 1) low[n] = min(low[vicino], low[n]);
}
// controllo se sono arrivato alla fine della SCC
if(low[n] == id[n]) {
while(true) {
// reset
v = stackk.top();
onStack[v] = 0;
low[v] = id[n]; // why
stackk.pop();
// fine della SCC
if(v == n) break;
}
}
last = n; // ultimo nodo chiuso --> parte SCC a monte
}
Non ho trovato delucidazioni su internet. Solamente una delle implementazioni che ho visto anche solo prevede questa linea di codice. Voi sapreste dirmi perché è necessaria?
Grazie mille.