[OPT2 Branch] Doesn't detect every case of "Not Isolated Node"

[fmrsabino]

Para o ponto 3 pensei no seguinte: como estamos a analisar em profundidade então quando chegamos sempre ao fim da stack (ie.: quando começamos a fazer pops) sabemos que o pai desses nós a que estamos a fazer pop não são isolados (porque levaram até ao SCC actual). Atenção que este if só corre quando estamos presente um nó raiz e por essa razão resulta para a maior parte dos casos.

Basicamente dizemos enquanto estamos a contruir um SCC que o nó anterior (que vai pertencer a um SCC não está isolado).

Neste exemplo ele põe na stack o 1 e o 2 e depois tira o 1 e o 2 da stack e depois passa para o 3 e para o 4. Na altura em que ele tira o 3 e o 4 ele deveria dizer que o nó anterior (na stack) não é isolodo. Como o 1 o 2 já não estão na stack considerei isso um SCC fantasma (um SCC que não é isolado mas que não está na stack) e quando ele detecta essa situação diz que existe mais um SCC não isolado (isolatedSCC--)

if((!nodeStack.empty() && nodes[fatherNode]->checkedIsolation == false) || (phantomSCC && nodeStack.empty()) || (fatherNode != -1 && nPops == 1 && !adjacencias[u].empty())) {
            std::cout << "SCC with node " << fatherNode <<" is not isolated!" << std::endl;
            nodes[fatherNode]->checkedIsolation = true;
            numberOfIsolatedSCC--;
}

Estive a pensar e penso que seja problema do fatherNode. Ou seja um SCC estar ligado a mais SCC's mas nesses SCC's o father node ser diferente e aí ele considera que existe um SCC Não Isolado a mais...

A terceira condição do if é quando um estamos a tirar um nó da pilha (que é o nó raiz) e que ele tem vizinhos e esse vizinhos não estão na pilha porque já forma visitados. (ver o nó 3 do teste 1 que os professores dão que é um exemplo desse caso).

[fmrsabino]

Possível solução: Marcar o nó como não isolado e ao fazer pops verificar apenas uma vez essa condição.