Cod sursa(job #2747855)

Utilizator Casian_doispeChiriac Casian Casian_doispe Data 29 aprilie 2021 18:13:06
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>
#include <deque>
#include <stack>

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

vector<int> v[50009] ;

int frecv[100009], n ;

deque<int> ck ;

void topsort(int x)
{

    frecv[x] = 1 ;

    ck.push_back(x) ;

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

        int curent = v[x][f] ;

        if(!frecv[curent])topsort(curent) ;

    }

}

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) ;

    }

    for(int f = 1 ; f <= n ; f ++)
        if(!frecv[f])topsort(f) ;

    while(ck.size())
        cout << ck.front() << " ", ck.pop_front() ;

    return 0;
}