Cod sursa(job #2660669)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 20 octombrie 2020 01:46:29
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");
struct nod
{
    int info;
    nod * urm;
}*pr[50001];
int c[50001], gr[50001];
void add(int x, int y)
{
    //il adaug pe y la superiorii lui x
    gr[y]++;
    nod * aux = new nod;
    aux->info=y;
    aux->urm=pr[x];
    pr[x]=aux;
}
int main()
{
    int n, m, i, p, u, x, y;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y;
        add(x, y);
    }
    p=1;
    u=0;
    for(i=1; i<=n; i++)
    {
        if(gr[i]==0)
        {
            u++;
            c[u]=i;
        }
    }
    while(p<=u)
    {
        nod * t = pr[ c[p] ];
        while(t!=NULL)
        {
            gr[t->info]--;
            if(gr[t->info]==0)
            {
                c[++u]=t->info;
            }
            t=t->urm;
        }
        p++;
    }
    for(i=1; i<=n; i++)
    {
        fout<<c[i]<<' ';
    }
}