Cod sursa(job #844462)

Utilizator matei_cChristescu Matei matei_c Data 29 decembrie 2012 13:00:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
 
#define maxn 50001
 
int n,m ;

int coada[maxn] ;
int even[maxn] ;

vector<int> graf[maxn] ;
 
int main()
{
     
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
     
    scanf("%d%d", &n, &m);
	
    for(int i = 1; i <= m; ++i )
    {
        int a, b ;
        
		scanf("%d%d",&a,&b);
        
		graf[a].push_back( b ) ;
        //graf[b].push_back( a ) ;
        
		++even[b] ;
    }   
     
    int len = 0 ;
	
    for(int i = 1; i <= n; ++i )
    {
        if( even[i] == 0 )
        {
            ++len ;
            coada[len] = i ;
        }   
    }   
     
    for(int i = 1; i <= len; ++i )
    {
        if( even[ coada[i] ] == 0 )
        {
			int nod = coada[i] ;
			
            printf("%d ",nod );
			
            for(size_t j = 0; j < graf[nod].size() ;++j )
            {   
				int nod_act = graf[nod][j] ;
				
                --even[ nod_act ] ;
                
				if( even[ nod_act ] == 0 )
                {
                    ++len ;
                    coada[len] = nod_act ;
                }   
            }   
        }   
    }   
     
    printf("\n") ;

    return 0 ;
	
}