Cod sursa(job #2749653)

Utilizator AnastasiaStefanescuAnastasia Stefanescu AnastasiaStefanescu Data 7 mai 2021 17:40:17
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <iostream>
#include <queue>
#include <set>
#include <vector>

using namespace std;
ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");

int n, m, f[50001], ord_top[50001], t;
vector <int> l[50001];

void topsort(int nod)
{
    int i;
    f[nod] = 1;
    
    for (i = 0; i< l[nod].size(); i++)
        if(f[l[nod][i]] == 0)
            topsort(l[nod][i]);
    
    t++;
    ord_top[t] = nod;
}


int main()
{
    int i, x, y, aux;
    char k;
    
    fin >> n >> m;
    
    for (i = 1; i<= m; i++)
    {
        fin >> x >> y;
        l[x].push_back(y);
    }
    
    //sortam topologic
    for (i = 1; i<= n; i++)
        if(f[i] == 0)
            topsort(i);
    
    for (i = n; i>= 1; i--)
        fout << ord_top[i] << " ";
    
    return 0;
}