Cod sursa(job #1097397)

Utilizator TBLam99Tran Bach Lam TBLam99 Data 3 februarie 2014 13:30:44
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 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)
                    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)
                                    q.push(suc[tata].back());
                                suc[tata].pop_back();
                            }
                        if(pred[tata]==0)
                            {
                                printf("%d ",tata);
                                pred[tata]=-1;
                            }
                        q.pop();
                    }
            printf("\n");
            return 0;
}