Ocena użytkownikóww: ***** / 4
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;
}