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?

Sortowanie topologiczne - Implementacja w C/C++
Ocena użytkownikóww: *****  / 2
SłabyŚwietny
Nadesłany przez Emil Hotkowski, 06 kwietnia 2012 22:29
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.

sortowanie_topologiczne.cpp:
//Sortowanie topologiczne
//Emil Hotkowski
//www.algorytm.org

#include <cstdio>
#include <vector>
#define MX 10000

using namespace std;
vector < int > graf[MX];
 
int in[MX];
int kol[MX];
int pocz =1 ;
int kon =1;

int main(){

 int n , m;
 scanf("%d %d",&n,&m); //pobierz liczbe wierzcholkow oraz krawedzi   
 
 for(int i = 0 ; i <= n ;i++) in[i]=0;
 
 for(int i = 0 ; i < m;i++){
         int a ,b;
         scanf("%d %d",&a,&b); //pobierz od użtkownika krawedz
         in[b]++;              //zwieksz liczbe krawedzi wchodzacych dla wierzcholka b
         graf[a].push_back(b); //dodaj krawedz wychodzaca dla wierzcholka a
 }
 
 //wierzcholki bez krawedzi wchodzacych wrzuc do worka
 for(int i = 1 ; i <= n ;i++) if(in[i]==0) kol[kon++]=i; 
 
 for(int i = 1; i <=n;i++){
         int akt = kol[pocz]; //wez wierzcholek z worka
         pocz++;
         //dla wszystkich krawedzi wychodzacych
         while(!graf[akt].empty()){ 
                 //zmiejsz liczbe krawedzi wchodzacych do wierzcholka dla usuwanej krawedzi
                 in[graf[akt].back()]--; 
                 //jezeli po usunieciu krawedzi wierzcholek nie ma krawedzi wchodzacych dodaj go do worka
                 if (in[graf[akt].back()]==0) kol[kon++] = graf[akt].back();
                 //usun krawedz wychodzaca
                 graf[akt].pop_back();
         }
 }

 //wypisz wynik
 for(int i = 1 ; i <= n ; i++)printf("%d : %d\n",i,kol[i]);

 scanf("%d",&n);
 return 0;   
}
Dodaj komentarz