Ocena użytkownikóww: ***** / 6
Nadesłany przez Emil Hotkowski, 30 marca 2012 12:45
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.
silnie_spojne_skladowe.cpp:
// EMIL HOTKOWSKI
// Silne spójne składowe
// Bez list i setów , na vectorach
// www.algorytm.org
#include <cstdio>
#include <vector>
#define MX 10000
using namespace std;
vector <int> graf[MX];//tytaj mamy graf
vector <int> grafT[MX];//tu trzymamy graf odwrócony do SSS
vector <int> silna_vec[MX];//vector przechowujacy wierzchołki należace do SSS
int visited[MX];//do dfs
int visited2[MX];// do funkcji sss
int NR[MX];//Numer post order w DFS
int nr=1;//do numeracji
int silna=0;//do ilosci silni
void dfs(int v){//DFS
visited[v]=1;
while(!graf[v].empty()){
int z = graf[v].back();
graf[v].pop_back();
if(visited[z]==false){
visited[z]=1;
dfs(z);
}
}
NR[nr]=v;nr++;//post order !!! WAZNE
}
void sss(int v){
visited2[v]=1;//puszczamy takjakby dfs na odwrocony grafie .. ilosc dfs'ow to ilosc SSS
while(!grafT[v].empty()){
int z = grafT[v].back();
grafT[v].pop_back();
if(visited2[z]==false){
silna_vec[silna].push_back(z);
visited2[z]=1;
sss(z);
}
}
}
int main()
{
int n , m;
scanf("%d %d",&n,&m);//ile wierzchołkow ile krawdzei
for(int i = 0 ; i < m;i++){
int a,b;
scanf("%d %d",&a,&b);//uzupełniamy krawiędzi
graf[a].push_back(b); //graf
grafT[b].push_back(a); //graf odwrocony
}
for(int i = 1; i <= n ; i++) if(visited[i]==false) dfs(i);//puszczamy dfs(y)
for(int i = n; i >= 1 ; i--) if(visited2[NR[i]]==false) {
sss(NR[i]);
silna_vec[silna].push_back(NR[i]);
silna++;
}//wyszukujemy silna
printf("silne : %d\n",silna);//wyswietlmay ile jest silnych
for(int i = 0; i < silna ; i++) {//dodatkowe wyswietlanie tych silni
printf("%d : ",i);
while(!silna_vec[i].empty()){
printf(" %d ",silna_vec[i].back());
silna_vec[i].pop_back();
}
printf("\n");
}
scanf("%d",&n);//dla DEV-cpp zeby widziec wynik ;)
return 0;
}