Cod sursa(job #468813)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 5 iulie 2010 11:06:48
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<cstdio>
#include<vector>
#include<queue>
#define N 1<<16
#define in "sortaret.in"
#define out "sortaret.out"
using namespace std;
vector<int> L[N];
int n,m,l,c,Q[N],pred[N];
void read()
{
    int x,y;
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        L[x].push_back(y);
        pred[y]++;
    }
}
void init()
{
    for(int i=1;i<=n;i++)
        if(pred[i]==0)
            Q[++l]=i;
}
void solve()
{
    c=0;
    while(c<l)
    {
        c++;
        for(vector<int>::iterator it=L[Q[c]].begin();it!=L[Q[c]].end();it++)
        {
            pred[*it]--;
            if(pred[*it]==0)
                Q[++l]=*it;
        }
    }
}
void afis()
{
    for(int i=1;i<=n;i++)
        printf("%d ",Q[i]);
}
int main()
{
    read();
    init();
    solve();
    afis();
    return 0;
}