Cod sursa(job #1821693)

Utilizator cosminmaneaCosmin Manea cosminmanea Data 3 decembrie 2016 14:44:51
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <cstdio>
#include <vector>

using namespace std;

int n,m,grad[50010],t[50010];
vector <int> v[50010];
vector <int>::iterator ii;

int main()
{
    FILE *f=fopen("sortaret.in","r");
    FILE *g=fopen("sortaret.out","w");
    fscanf(f,"%d%d",&n,&m);
    int i,a,b;
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d",&a,&b);
        v[a].push_back(b);
        grad[b]++;
    }
    a=0;
    for(i=1;i<=n;i++)
        if(grad[i]==0)
            t[++a]=i;
    for(i=1;i<=n;i++)
    {
        for(ii=v[t[i]].begin();ii!=v[t[i]].end();ii++)
        {
            grad[*ii]--;
            if(grad[*ii]==0)
                t[++a]=*ii;
        }
    }
    for(i=1;i<=a;i++)
        fprintf(g,"%d ",t[i]);
    return 0;
}