Cod sursa(job #1759643)

Utilizator adina0822Ciubotaru Adina-Maria adina0822 Data 19 septembrie 2016 17:39:08
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
using namespace std;
#include <fstream>
#include <vector>

FILE *f=fopen ("sortaret.in","r");
FILE *g=fopen ("sortaret.out", "w");

vector <int> G[50001];
int q[50001],deg[50001];



int main()
{
    int n,m,x,y,i;

    fscanf(f,"%d%d",&n,&m);

    while(m--)
    {
        fscanf (f,"%d%d",&x,&y);
        G[x].push_back(y);
        deg[y]++;
    }

    for(i=1; i<=n; i++)
    {
        if(!deg[i])
        q[++q[0]]=i;


    }

    for(i=1; i<=n; i++)
    {
        x=q[i];
        vector <int>::iterator it;

        for(it=G[x].begin(); it!=G[x].end(); it++)
        {
            deg[*it]--;

            if(!deg[*it]) q[++q[0]]=*it;
        }
    }

    for(i=1; i<=q[0]; i++)
    fprintf(g,"%d ",q[i]);

    return 0;
}