[GIZ] Silnie Spójne Składowe – algorytm bez rekurencji

Algorytm Kosaraju do znajdowania silnie spójnych składowych w grafie ( http://www.algorytm.org/algorytmy-grafowe/silnie-spojne-skladowe.html – tu są 2 implementacje rekurencyjne i DOKŁADNY OPIS) zaimplementowałem w wersji bez rekurencji.

Dalej nie wygląda to za przejrzyście, ale jeśli ktoś ma problem ze rozumieniem rekurencji to może pomóc.

/*
"Program znajdujący silnie spójne składowe w grafie skierowanym - bez funkcji rekurencyjnych"
Jerzy Skalski (phoowned@wp.pl)
2017-05-15

Wymagania programu:
C++11 (opcja kompilatora) - można przepisać pętle po vectorach i listach tak, żeby nie był wymagany

Opis wejścia:
W pierwszej linii wejścia znajduje się jedna liczba dodatnia n - liczba wierzchołków grafu.
Dalej następuje n linii; i-ta spośród tych linii ma postać
k a1 a2 ... ak
gdzie a1, a2, ..., ak to numery wierzchołków, do których prowadzą krawędzie z i-tego, zaś k jest liczbą tych wierzchołków.

Przykładowe dane:
5
1 1
3 2 3 4
1 0
0
0

Rysunek grafu skierowanego:
  /<---< 2 <---<\
 /               \
0 >-------------> 1 >--> 3
                   \
                    \>-> 4

Wynik:
SSS ID: 0
1 2 0
SSS ID: 1
3
SSS ID: 2
4

*/
#include <iostream>
#include <map>
#include <vector>
#include <stack>
#include <list>

using namespace std;

int main()
{
    int iloscWezlow, iloscKrawedziWezla, wezel, wezelSasiedni, wezelStartowy, idSilnieSkladowej, i;
    vector<int>* listaSasiadowGraf;
    vector<int>* listaSasiadowGrafTransponowany;
    list<int> kolejnoscOdwiedzaniaDFSem;
	stack<int> wezlyDoOdwiedzenia;
    unsigned int* odwiedzoneWezly;

    cin >> iloscWezlow;

    // inicjujemy tablice
    listaSasiadowGraf = new vector<int>[iloscWezlow];
    listaSasiadowGrafTransponowany = new vector<int>[iloscWezlow];
	odwiedzoneWezly = new unsigned int[iloscWezlow];

    // ladujemy krawedzie do grafu i grafu transponowanego
    for (wezel = 0; wezel < iloscWezlow; ++wezel) {
        cin >> iloscKrawedziWezla;
        for (i = 0; i < iloscKrawedziWezla; ++i) {
            cin >> wezelSasiedni;
            listaSasiadowGraf[wezel].push_back(wezelSasiedni);
            listaSasiadowGrafTransponowany[wezelSasiedni].push_back(wezel);
        }
    }

    for (wezel = 0; wezel < iloscWezlow; ++wezel)
		odwiedzoneWezly[wezel] = 0;

    // przegladamy wezly grafu DFSem
    // zapisujemy czas przetworzenia (kolejnosc odwiedzania post order - dodajemy do listy jak sie 'cofamy')
	for(wezelStartowy = 0; wezelStartowy < iloscWezlow; ++wezelStartowy)
	{
		if(odwiedzoneWezly[wezelStartowy])
			continue;

		wezlyDoOdwiedzenia.push(wezelStartowy);
		while(!wezlyDoOdwiedzenia.empty()) {
			wezel = wezlyDoOdwiedzenia.top();
			wezlyDoOdwiedzenia.pop();

			if(odwiedzoneWezly[wezel]) {
				if(odwiedzoneWezly[wezel] == 1) {
					// push_front - powstanie lista od najwiekszego czasu przetworzenia
					kolejnoscOdwiedzaniaDFSem.push_front(wezel);
					odwiedzoneWezly[wezel] = 2;
				}
				continue;
			}
			odwiedzoneWezly[wezel] = 1;
			wezlyDoOdwiedzenia.push(wezel);
			for(int wezelSasiedni : listaSasiadowGraf[wezel]) {
				if(!odwiedzoneWezly[wezelSasiedni])
					wezlyDoOdwiedzenia.push(wezelSasiedni);
			}
		}
	}

    for (wezel = 0; wezel < iloscWezlow; ++wezel)
		odwiedzoneWezly[wezel] = 0;

    // przegladamy wezly grafu transponowanego DFSem od najwiekszego czasu przetworzenia DFSem
    // wszystkie przejrzane w ten sposob wezly naleza do jednej silnie spójnej składowej

	idSilnieSkladowej = 0;
	for(int wezelStartowy : kolejnoscOdwiedzaniaDFSem) {
		if(odwiedzoneWezly[wezelStartowy])
			continue;

		wezlyDoOdwiedzenia.push(wezelStartowy);
		cout << "SSS ID: " << idSilnieSkladowej << endl;
		// TUTAJ ZACZYNA SIE NOWA SSS
		while(!wezlyDoOdwiedzenia.empty()) {
			wezel = wezlyDoOdwiedzenia.top();
			wezlyDoOdwiedzenia.pop();

			if(odwiedzoneWezly[wezel]) {
				if(odwiedzoneWezly[wezel] == 1) {
					// przy ponownym wejsciu do wezla (cofajac sie DFS - post order) ustawiamy na 2
					odwiedzoneWezly[wezel] = 2;
					cout << wezel << " ";
					// TUTAJ NALEZY WYKONAC OPERACJE NA ELEMENCIE DANEJ SSS
				}
				continue;
			}
			// przy pierwszym wejsciu do wezla ustawiamy na 1
			odwiedzoneWezly[wezel] = 1;
			// dodajemy ten sam wezel ponownie na stos, zeby odwiedzic go podczas cofania
			wezlyDoOdwiedzenia.push(wezel);
			for(int wezelSasiedni : listaSasiadowGrafTransponowany[wezel]) {
				if(!odwiedzoneWezly[wezelSasiedni])
					wezlyDoOdwiedzenia.push(wezelSasiedni);
			}
		}
		cout << endl;
		// TUTAJ KONCZY SIE SSS
		idSilnieSkladowej++;
	}

    return 0;
}

Dla studentów którzy mają zadanie 'od babki’:

Jeśli chodzi o zadanie 'od babki’ to trzeba jeszcze dodać jednego 'for’ (może być z DFSem jak w drugim 'forze’ lub można w drugim 'forze’ wygenerować sobie 'mapę’ ze spisem wszystkich węzłów w każdej SSS) do policzenia ile każda silnie składowa spójna ma sąsiednich SSS, a potem jeszcze jeden 'for’ do wyświetlenia węzłów należących do tej SSS.

Algorytm który udostępniłem zakłada numerowanie węzłów od 0, a nie 1 jak w danych przykładowych od babki, więc należy przy wczytywaniu połączeń między węzłami zawsze zmieniać ’-1′ każde połączenie!