Cod sursa(job #560315)

Utilizator raica_cristiraica dumitru cristian raica_cristi Data 18 martie 2011 13:56:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 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],a[dim],dr;
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 addc(int x)
{
   dr++;
   a[dr]=x;
   printf("%d ",x);

}
inline void addq(int x)
{
    nod *p=liste[x];
    while ( p )
    {
        v[p->el]--;
        if ( v[p->el]==0)
        printf("%d ",p->el);
        p=p->next;
    }
}
void scan (int x )
{
    nod *p=liste[x];
    while (p)
    {
        v[p->el]--;
        if (v[p->el]==0)
            addc(p->el);
        p=p->next;
    }

}
void solve ()
{
    int x;
    for(int i=1 ; i<=n;i++)
        if ( v[i] == 0 )
           addc(i);
    for(int k=1 ; k<=dr ; k++)
    {
            scan(a[k]);
    }
}
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;
}