Cod sursa(job #760424)

Utilizator matei_cChristescu Matei matei_c Data 21 iunie 2012 12:17:16
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<cstdio>
#include<vector>
using namespace std;

#define maxn 50001

vector <int> vecini[maxn] ;
int n,m ;
int coada[maxn] ;
int even[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);
		vecini[a].push_back(b);
		vecini[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 )
		{
			printf("%d ",coada[i]);
			for(size_t j=0;j<vecini[coada[i]].size();++j)
			{	
				-- even[vecini[coada[i]][j]] ;
				if( even[vecini[coada[i]][j]] == 0 )
				{
					++ len ;
					coada[len] = vecini[coada[i]][j] ;
				}	
			}	
		}	
	}	
	
	printf("\n");
	
	return 0;
	
}