Cod sursa(job #560283)

Utilizator raica_cristiraica dumitru cristian raica_cristi Data 18 martie 2011 13:39:05
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include<queue.h>

using namespace std;
#define dim 101000

struct nod
{
    int el;
    nod *next ;
}*liste[dim];

int n,m;
int v[dim];
queue<int> q;
inline void add(int x,int y)
{
    nod *p=new nod;
    p->el=y;
    p->next=liste[x];
    liste[x]=p;
}
void read()
{
    int x,y;
    scanf("%d %d",&n,&m);
    for(int i=1 ; i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        add(x,y);
        v[y]++;
    }
}
inline void addq(int x)
{
    q.push(x);
    nod *p=liste[x];
    v[x]--;
    while ( p )
    {
        v[p->el]--;
        if ( v[p->el]==0 && p->el<x)
           {
               q.push(p->el);

               }
        p=p->next;
    }
}
void solve ()
{
    for(int i=1 ; i<=n;i++)
    {
        if ( v[i] == 0 )
        {
   //         printf("%d ",i );
            addq(i);
        }
    }
}
void afis ()
{
    for( ; !q.empty (); q.pop () )
    {
        printf("%d ",q.front());
    }
}
using namespace std;

int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
     read();
     solve();
     afis () ;
    return 0;
}