Cod sursa(job #1097378)

Utilizator TBLam99Tran Bach Lam TBLam99 Data 3 februarie 2014 13:07:00
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include<stdio.h>
#include<vector>
#include<queue>
int n,k,x,y,i,tata;
int pred[50011];
using namespace std;
int main()
{
            freopen("sortaret.in","r",stdin);
            freopen("sortaret.out","w",stdout);
            vector<int>suc[50011];
            queue<int>q;
            scanf("%d%d",&n,&k);
            for(i=1;i<=k;++i)
                {
                    scanf("%d%d",&x,&y);
                    ++pred[y];
                    suc[x].push_back(y);
                }
            for(i=1;i<=n;++i)
                if(pred[i]==0)
                    {
                        printf("%d ",i);
                        q.push(i);
                    }
            for(i=1;i<=n;++i)
                if(pred[i]!=0)
                    q.push(i);
            while(q.empty()==0)
                    {
                        tata=q.front();
                        while(suc[tata].size()!=0)
                            {
                                if(pred[suc[tata].back()]!=0)
                                    {
                                        --pred[suc[tata].back()];
                                        if(pred[suc[tata].back()]==0)
                                            printf("%d ",suc[tata].back());
                                    }
                                suc[tata].pop_back();
                            }
                        q.pop();
                    }
            return 0;
}