Cod sursa(job #1936628)

Utilizator ScarymovieMocanu Alexandru Scarymovie Data 23 martie 2017 11:29:30
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <fstream>
#include<vector>
using namespace std;
int n,m,a,b,v[50001],k,ok=1;
vector< vector<int> > la;
vector<int> d;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int main()
{
    f>>n>>m;la.resize(n+1);d.resize(n+1);
    for(int i=1;i<=m;i++)
        {f>>a>>b;la[a].push_back(b);d[b]++;}
    for(int i=1;i<=n;i++)
        if(!d[i]) {v[++k]=i;g<<i<<' ';}
    ok-=(k==n);
    for(int i=1;i<=n && ok;i++)
        for(int j=0;j<la[v[i]].size() && ok;j++)
            {
                d[la[v[i]][j]]--;
                if(!d[la[v[i]][j]]) {v[++k]=la[v[i]][j];g<<la[v[i]][j]<<' ';}
                if(k==n) ok=0;
            }
    return 0;
}