Cod sursa(job #1058891)

Utilizator gerd13David Gergely gerd13 Data 15 decembrie 2013 22:29:33
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std ;

ifstream cin("sortaret.in") ;
ofstream cout("sortaret.out") ;

const int NMAX = 50001 ;
vector <int> Graf[NMAX] ;
queue <int> Q;
int  Out[NMAX] ;
int N, M;


int main()
{

    cin >> N >> M ;

    for(int i = 0 ; i <= M ; ++ i)
    {
        int x, y ;
        cin >> x >> y ;
        Graf[x].push_back(y) ;
        ++ Out[y] ;
    }

    for(int i  = 1 ; i <= N ; ++ i)
    {
        if(Out[i] == 0)
        {
            Q.push(i) ;
            cout << i << ' ' ;
        }
    }

    while (!Q.empty())
    {
        int nod = Q.front();
        Q.pop();

        for(int i = 0 ; i < Graf[nod].size() ; ++ i )
        {
            int act_nod = Graf[nod][i] ;
            -- Out[act_nod];
            if(Out[act_nod] == 0)
            {
                Q.push(act_nod) ;
                cout << act_nod << ' ';
            }
        }
    }

    cin.close() ;
    cout.close() ;
    return 0;

}