Cod sursa(job #2747808)

Utilizator Casian_doispeChiriac Casian Casian_doispe Data 29 aprilie 2021 17:44:20
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <vector>
#include <deque>

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

vector<int> v[50009] ;

int frecv[100009], n ;

void topsort()
{

    deque<int> dq ;

    for(int f = 1 ; f <= n ; f ++)
        if(!frecv[f])dq.push_back(f), frecv[f] = -1 ;

    while(dq.size())
    {

        cout << dq.front() << " " ;

        int aux = dq.front() ;

        dq.pop_front() ;

        for(int f = 0 ; f < v[aux].size() ; f ++)
        {

            frecv[v[aux][f]] -- ;

            if(!frecv[v[aux][f]])dq.push_back(v[aux][f]), frecv[f] = -1 ;

        }

    }

}

int main()
{

    int m ;

    cin >> n >> m ;

    for(int f = 1 ; f <= m ; f ++)
    {

        /// calculam gradele interioare pentru fiecare nod

        int a, b ;

        cin >> a >> b ;

        v[a].push_back(b) ;

        frecv[b] ++ ;

    }

    topsort() ;

    return 0;
}