Cod sursa(job #468816)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 5 iulie 2010 11:14:45
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 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);
        bool ok=false;
        for(vector<int>::iterator it=L[x].begin();it!=L[x].end();it++)
            if(*it==y)
                ok=true;
        if(ok==true)
        {
            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;
}