Cod sursa(job #1420666)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 18 aprilie 2015 20:10:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
// Sortare Topologica - O(N+M)
#include <fstream>
#include <vector>
#include <bitset>
#define Nmax 50099
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int N,M,Tsort[Nmax],x,y;

vector < int > G[Nmax];
bitset < Nmax > viz;


void DFS(int node) {
    viz[node] = 1;
    for(vector <int>::iterator it = G[node].begin(); it != G[node].end(); ++it)
        if(!viz[*it]) DFS(*it);
    // S-au parcurs toti fii lui node, deci il pot adauga la sortare
    Tsort[++Tsort[0]]=node;
}

void SorteazaTopologic() {
    for(int i =1; i <= N; ++i)
        if(!viz[i]) DFS(i);

    //Solutia a fost generata invers, deci afisez pe dos
    for(int i =N; i >=1 ; --i) g << Tsort[i] << ' ';
    g << '\n';
}


int main() {
    f >> N >> M;
    for(int i = 1; i <= M; ++i)
        f >> x >> y , G[x].push_back(y); // ATENTIE CA E ORIENTAT!
    SorteazaTopologic();
    f.close();g.close();
    return 0;
}