Cod sursa(job #652643)

Utilizator slycerdan dragomir slycer Data 25 decembrie 2011 16:45:46
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
/* 
 * File:   Sortaretopologica.cpp
 * Author: slycer
 *
 * Created on December 25, 2011, 4:28 PM
 */

#include <cstdlib>
#include <fstream>
#include <vector>
using namespace std;

/*
 * 
 */
class Nod{
        public:
    Nod( int v ){
        this->v = v; 
    }
    int v;
};

int main(int argc, char** argv) {

    ifstream input ( "sortaret.in" );
    ofstream output ( "sortaret.out" );
    int n,m; 
    input >> n >> m; 
    vector<Nod> graf [n+1];
    int grad[n+1];
    for ( int i=0; i<=n; i++){
        grad[i] = 0; 
    }
    for ( int i=0; i<m; i++){
        int a,b; 
        input >> a >> b;
        graf[a].push_back(  Nod(b) );
        grad[b]++;
    }
    vector<int> queue; 
    for ( int i=1; i<=n; i++){
        if ( grad[i] == 0 ){
            queue.push_back( i ); 
        }
    }
    
    while ( queue.size() > 0 ){
        int last = queue.back();
        queue.pop_back();
        output << last << " ";
        for ( int i=0; i<graf[last].size(); i++ ){
            int c = graf[last][i].v; 
            grad[c]--;
            if ( grad[c] == 0 ){
                queue.push_back( c );
            }
        }
    }
    
    return 0;
}