Cod sursa(job #521638)

Utilizator liviu12345Stoica Liviu liviu12345 Data 12 ianuarie 2011 23:37:40
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<cstdio>
#include<vector>
#define maxn 100001

using namespace std;
vector < vector < int > > lista;
int sel[ maxn ],coada[maxn],n,m;
int main()
{
  int i,j,k;
  freopen ( "sortaret.in" , "r" , stdin ) ;
  freopen ( "sortaret.out" , "w" , stdout ) ;
  scanf ( "%d%d" , &n , &m ) ;
  
  vector < int > temp;
  for( int i = 0; i <= n; ++i)
    lista.push_back( temp);
  while ( m-- )
  {
    scanf ( "%d%d" , &i , &j ) ;
    lista[i].push_back(j);
    sel[j]++;
    //lista[j].push_back(i);
    
  }
  int nr_elem = 0, coada[maxn];
  for( int i = 1; i <= n; ++i)
    if( sel[i] == 0)
      coada[ ++nr_elem] = i;
    for (i=1;i<=n;i++)
    {
      j = coada[i];
      int size = lista[j].size();
      for(k=0;k<size;k++)
      {
	sel[lista[j][k]]--;
	if( sel[lista[j][k]] == 0)
	{
	  coada[ ++nr_elem] = lista[j][k];
	}
      }
      
      
    }
    for(i=1;i<=n;i++)
      printf ( "%d " , coada[i] ) ;
    return 0;
    
}