Silnie spójne składowe

Algorytm wyznacza silnie spójne składowe w grafie skierowanym

Zasada działania algorytmu

Algorytm wyznacza grupy wierzchołków, które tworzą silnie spójne składowe w grafie skierowanym. Taka grupa charakteryzuje się tym, że z każdego wierzchołka w obrębie tej grupy istnieje ścieżka do każdego innego.

Kroki działania algorytmu.

• Uruchom DFS'a, aby wyznaczyć czasy przetworzenia kolejnych wierzchołków (wierzchołek jest przetworzony, gdy zostanie on obsłużony przez DFS i do niego już nie wrócimy), zapisując w tablicy numery wierzchołków w kolejności ich przetworzenia.
• Wykonaj transpozycje grafu, tzn. odwróć wszystkie krawędzie na przeciwne.
• Wykonaj DFS'a po grafie transponowanym począwszy od wierzchołka, który został przetworzony jako ostatni. Grupa odwiedzonych w ten sposób wierzchołków tworzy silnie spójne składowe grafu skierowanego.

Wejście

W pierwszym wierszu wprowadzamy dwie liczby naturalne n i k określające odpowiednio liczbę wierzchołków oraz liczbę połączeń w grafie. W kolejnych k wierszach po dwie liczby definiujące połączenie między wierzchołkiem o numerze a oraz wierzchołkiem o numerze b, 0 <= a, b < n.

Wyjście

W kolejnych wierszach grupy wierzchołków silnie spójne składowych

//silnie spójne składowe
//algorytm.edu.pl
#include<bits/stdc++.h>
using namespace std;

//tablica, w której będą przechowywane czasy przetworzenia kolejnych wierzchołków
int *czas_przetworzenia;
//stos będzie przechowywał kolejne grupy silnie spójnych składowych
stack <int> sss; 

struct Graf{
	vector <int> polaczenia;
	bool odwiedzony;
};

//faza_pierwsza = 1, gdy wyznaczamy czasy przetworzenia wierzchołków
//faza_pierwsza = 0, gdy wyznaczamy silnie spójne składowe
void DFS(int n, int &czas, Graf G[], bool faza_pierwsza)
{
	G[n].odwiedzony = true;
	
	for(int i=0; i<G[n].polaczenia.size(); i++)
		if(!G[G[n].polaczenia[i]].odwiedzony)
			DFS(G[n].polaczenia[i], czas, G, faza_pierwsza);
	
	if(faza_pierwsza)
		czas_przetworzenia[czas++] = n;
	else
		sss.push(n);	
}

int main()
{
	int n, k, a, b, czas = 0;
	cin>>n>>k;
	
	//przydzielamy pamięć na graf oraz jego transpozycję
	Graf *G = new Graf [n], *GT = new Graf[n];
	//tablica do przechowwyania czasów przetworzeń wierzchołków
	czas_przetworzenia = new int [n];
	
	for(int i=0; i<n;i++)
		G[i].odwiedzony = GT[i].odwiedzony = false;
	
	
	while(k--)
	{
		cin>>a>>b;
		//tworzymy połączenia grafu G
		G[a].polaczenia.push_back(b);
		//tworzymy transpozycję grafu G
		GT[b].polaczenia.push_back(a);
	}
	
	//wyznaczamy DFS'em czasy przetworzenia wierzchołków
	for(int i=0; i<n; i++)
		if(!G[i].odwiedzony)
			DFS(i, czas, G, 1);
	
	//for(int i=0;i<n;i++)
	//	cout<<czas_przetworzenia[i]<<' ';
	//	cout<<endl;
	
	//wyszukujemy silnie spójne składowe i je wypisujemy		
	for(int i=n-1; i>=0; i--)
		if(!GT[czas_przetworzenia[i]].odwiedzony)
		{
			DFS(czas_przetworzenia[i], czas, GT, 0);
			while(!sss.empty())
			{
				cout<<sss.top()<<' ';
				sss.pop();
			}
			cout<<endl;
		}
			
	return 0;
}