Sortowanie Topologiczne

Sortowanie Topologiczne to takie uporządkowanie wierzchołków acyklicznego skierowanego grafu, że gdyby ustawić je na poziomej linii to wszystkie krawędzie bylyby skierowane w prawo. Aby posortować topologicznie DAG (Skierowany Acykliczny Graf) należy wykonać na nim DFS. W chwili przetworzenia każdego wierzchołka, wrzucamy go na stos sortowania. Po zakończeniu przeszukiwania DFS, wierzchołki bedą posortowane na tym stosie.

Przykładowy kod:

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
vector<vector<int> > graf;
deque<int> stos, topologicznie;
vector<int> poprzednik, odwiedzenie, przetworzenie;
vector<bool> done;
int N, E, u, v, czas=0;
const int INF = 1000001;
 
void dfs_visit(int u){
    done[u]=true;
    odwiedzenie[u]=++czas;
    for(vector<int>::iterator it=graf[u].begin(); it!=graf[u].end(); it++){
        int v=*it;
        if(!done[v]){
            poprzednik[v]=u;
            dfs_visit(v);
        }
    }
    przetworzenie[u]=++czas;
    topologicznie.push_front(u); //po przetworzeniu wierzcholka u wrzucamy go na stos sortowania topologicznego
}
 
void dfs(){
    czas=0;
    for(int i=0; i<N; i++){
        if(!done[i])dfs_visit(i);
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin>>N>>E;
    graf.resize(N);
    done.resize(N);
    poprzednik.resize(N, INF);
    odwiedzenie.resize(N, INF);
    przetworzenie.resize(N, INF);
    for(int i=0; i<E; i++){
        cin>>u>>v;
        graf[u-1].push_back(v-1);
    }
    dfs();
    cout<<"Porzadek Topologiczny: \n";
    while(!topologicznie.empty()){ //wypisujemy wszystkie wierzcholki ze stosu zdejmujac je od gory czyli zaczynajac od wierzcholkow najpozniej przetworzonych
        int u=topologicznie.front();
        topologicznie.pop_front();
        cout<<u+1<<" ";
    }
    cout<<endl;
    system("pause");
    return 0;
}
//Przykladowe Wejscie
/*10 12
1 2
1 9
2 3
2 4
2 9
4 10
4 6
4 5
6 10
6 7
8 7
7 9*/