Cod sursa(job #1980886)

Utilizator rockzoneCerneanu Valentin rockzone Data 14 mai 2017 12:30:03
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include<fstream>
using namespace std;
ofstream fout("sortaret.out");
struct nod
{
    int vf;
    nod *urm;
};
nod *prim[50000];
int n;
int gr[50000];
int c[50000], first, last;
void adauga(int x, int y)
{
    nod *p;
    p=new nod;
    p->vf=x;
    p->urm=prim[y];
    prim[y]=p;
}
void stergere_grade(int x)
{
    int i;
    nod *p;
    p=prim[x];
    while(p)
    {
        gr[p->vf]--;
        if(gr[p->vf]==0)
        {
            c[last]=p->vf;
            last++;
            fout<<p->vf<<" ";
        }
        p=p->urm;
    }
}
int main()
{
    ifstream fin("sortaret.in");

    int m, i, x, y;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y;
        adauga(y, x);
        gr[y]++;
    }
    first=last=1;
    for(i=1; i<=n; i++)
    {
        if(gr[i]==0)
        {
            fout<<i<<" ";
            c[last]=i;
            last++;
        }
    }
    while(first<=last)
    {
        stergere_grade(c[first]);
        first++;
    }
    return 0;
}