Cod sursa(job #155786)

Utilizator DorinOltean Dorin Dorin Data 12 martie 2008 10:12:41
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
# include <stdio.h>
# include <vector>

using namespace std;

# define input "sortaret.in"
# define output "sortaret.out"

# define max 50001


int n,m,x,y,l,i,k,j;
int coada[max],inc[max];
vector < vector < int > > v;

int main()
{
    freopen(input, "r", stdin);
    freopen(output, "w", stdout);
    
    scanf("%d%d",&n,&m);
    
    v.resize(n+1);
    
    for(i=1;i<=m;i++)
    {
       scanf("%d%d",&x,&y);
       v[y].push_back(x);
       inc[x]++;
    }
    l = n;
    
    for(i=1;i<=n;i++)
        if(!inc[i])
           coada[l--] = i;
    int st = n;
    while(st)
    {
       i = coada[st];
       for(k=0;k<v[i].size();k++)
       {
          j = v[i][k];
          inc[j] --;
          if(inc[j] == 0)
                    coada[l--] = j;
       }
       st--;
    }
    
    for(i=1;i<=n;i++)
        printf("%d ",coada[i]);
    
    return 0;
}