Cod sursa(job #782766)

Utilizator nicu701Nicu Badescu nicu701 Data 29 august 2012 22:19:35
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
using namespace std;
fstream f("sortaret.in", ios::in),
        g("sortaret.out",ios::out);

struct Nod
{
    int info;
    Nod *next;
};

Nod *a[50000];
int c[50000], contor[50000], m, n, gasit,k;

void Adaug(int i, int j)
{
    contor[j]++;
   Nod *c, *d;
   c=a[i];
   d=new Nod;
   d->next=0;
   d->info=j;
   if(c==0)
        a[i]=d;
    else
    {
        while(c->next)
            c=c->next;
        c->next=d;
    }
}

void Actual(int i)
{
    Nod *c=a[i];
    while(c)
    {
        contor[c->info]--;
        c=c->next;
    }
}

int main()
{
    int i, j, nCopy;
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        contor[i]=0;
        a[i]=0;
    }
    for(int count=1;count<=m;count++)
    {
        f>>i>>j;
        Adaug(i,j);
    }
    nCopy=n;
    do
    {
        k=0;
        gasit=0;
        for(i=1;i<=n;i++)
        {
            if(contor[i]==0)
            {

                gasit=1;
                k++;
                c[k]=i;
                contor[i]=-1;
                nCopy--;
            }
        }
        for(i=1;i<=k;i++)
        {
            Actual(c[i]);
            g<<c[i]<<" ";

        }
    }while(gasit && nCopy);
    return 0;
}