Cod sursa(job #922263)

Utilizator dariusgDarius Galis dariusg Data 22 martie 2013 00:21:10
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <cstdio>
#include <vector>
using namespace std;

FILE *f=fopen("sortaret,in","r");
FILE *g=fopen("sortaret,out","w");

#define Nmax 50002

int coada[Nmax],grad[Nmax];
int N,M,i,x,y;
vector <int> Nod[Nmax]; 
vector<int>::iterator it;

int main()
{
    fscanf(f,"%d%d",&N,&M);
    for(i=1;i<=M;++i)
    {
        fscanf(f,"%d%d",&x,&y);
        Nod[x].push_back(y);
        grad[y]++;
    }
    
    for(i=1;i<=N;++i)
        if(grad[i]==0)
            coada[++coada[0]]=i;//k++; coada[k]=...
    
    for(i=1;i<=N;i++)
    {
        x=coada[i];
        for(it=Nod[x].begin();it!=Nod[x].end();++it)
        {
            grad[*it]--;
            if(grad[*it]==0)
                coada[++coada[0]]=*it;
        }
    }
    
    for(i=1;i<=N;i++)
        fprintf(g,"%d ",coada[i]);
    
    fclose(f);
    fclose(g);
    
    return 0;
    
}