Cod sursa(job #1674833)

Utilizator teoceltareconstantin teodor teoceltare Data 4 aprilie 2016 21:32:42
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n,m,p,u;
int A[50001],d[50001];
struct nod
{
    int val;
    nod *urm;
} *v[50001], *c;
void citire()
{
    int a,b;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        v[i]=new(nod);
        v[i]->val=0;
    }
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b;
        c=new(nod);
        c->val=b;
        c->urm=v[a];
        v[a]=c;
        A[b]++;
    }
}
void parc()
{
    while(p<=u)
    {
        int x=d[p],y;
        while(v[x]->val)
        {
            y=v[x]->val;
            A[y]--;
            if(A[y]==0)
            {
                u++;
                d[u]=y;
            }
            v[x]=v[x]->urm;
        }
        p++;
    }
}
int main()
{
    p=1;u=0;
    citire();
    for(int i=1;i<=n;i++)
    {
        if(A[i]==0)
        {
            u++;
            d[u]=i;
        }
    }
    parc();
    for(int i=1;i<=u;i++)
    {
        fout<<d[i]<<" ";
    }
}