Cod sursa(job #406042)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 1 martie 2010 09:16:54
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stdio.h>
#include <deque>
#define N 50010

using namespace std;

struct nod
{
    int inf;
    nod * next;
}*a[N];

int grad[N],n,m,p,x1,x2;
deque <int> Q;

void add(int x1,int x2)
{
    nod *q=new nod;
    q->inf=x2;
    q->next=a[x1];
    a[x1]=q;
}

void citire()
{
    scanf ("%d %d",&n,&m);
    for (int i=0;i<m;i++)
    {
        scanf ("%d %d ",&x1,&x2);
        add(x1,x2);
        grad[x2]++;
    }
}
void solve()
{
    for (int i=1;i<=n;i++)
        if (!grad[i])
        {
            Q.push_back(i);
            printf("%d ",i);
        }

    while (Q.size())
    {
        p=Q.front();
        Q.pop_front();
        for (nod *q=a[p];q;q=q->next)
        {
            grad[q->inf]--;
            if (grad[q->inf]==0)
            {
                Q.push_back(q->inf);
                printf("%d ",q->inf);
            }
        }
    }

}

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