algorytm.org

Implementacja w C/C++



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Silnie spójne składowe - Implementacja w C/C++
Ocena użytkownikóww: *****  / 6
SłabyŚwietny
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;    
}
Dodaj komentarz