Cod sursa(job #2425238)

Utilizator seba99Sebastian Balan seba99 Data 24 mai 2019 17:01:00
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;

vector<int> v[50002];
int grad_ext[50002];
int sol[50002];


int main() {

    ifstream f("sortaret.in");
    ofstream g("sortaret.out");

    int n,m,i,j,x,y;
    int ind_sol=1;

    f>>n>>m;
    for(i=0;i<m;i++)
    {
        f>>x>>y;
        v[y].push_back(x);
        grad_ext[x]++;
    }

    for(i=1;i<=n;i++)
        if(grad_ext[i]==0)
        {
            sol[ind_sol]=i;
            ind_sol++;

        }

     for(int k=1;k<ind_sol;k++)
     {
         i=sol[k];
         for(j=0;j<v[i].size();j++)
         {
             grad_ext[v[i][j]]--;
             if(grad_ext[v[i][j]]==0)
             {
                 sol[ind_sol]=v[i][j];
                 ind_sol++;
             }
         }
     }

     for(i=n;i>=1;i--)
         g<<sol[i]<< " ";
    f.close();
    g.close();
    return 0;
}