Cod sursa(job #1097424)

Utilizator TBLam99Tran Bach Lam TBLam99 Data 3 februarie 2014 13:46:23
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 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);
            while(q.empty()==0)
                    {
                        tata=q.front();
                        for(i=0;i<suc[tata].size();++i)
                            {
                                if(pred[suc[tata][i]]!=0)
                                    --pred[suc[tata][i]];
                                if(pred[suc[tata][i]]==0)
                                    q.push(suc[tata][i]);
                            }
                        printf("%d ",tata);
                        q.pop();
                    }
            printf("\n");
            return 0;
}