Cod sursa(job #560266)

Utilizator raica_cristiraica dumitru cristian raica_cristi Data 18 martie 2011 13:35:17
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 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];
    while ( p)
    {
        v[p->el]--;
        p=p->next;
    }
}
void solve ()
{
    for(int i=1 ; i<=n;i++)
    {
        if ( v[i] == 0 )
        {
            printf("%d ",i );
            addq(i);
        }
    }
}
using namespace std;

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