Cod sursa(job #792169)

Utilizator MtkMarianHagrSnaf MtkMarian Data 26 septembrie 2012 17:40:45
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>
#include<vector>
#include<string.h>
using namespace std; 
//vector<int > v;

#define Max 50011
vector<int>s[Max];


int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	int n,m,x,y,pred[Max]={0},q[Max];
	vector<int>::iterator it;
	scanf("%d %d",&n,&m);
	q[0]=0;
	//memset(&pred[0],0,(n+1)*sizeof(int));
	for(int i=1;i<=m;++i)
	{

		scanf("%d %d",&x,&y);				
		s[x].push_back(y);
		pred[y]+=1;
	}
	
	for(int i=1;i<=n;++i)
	{
		if(!pred[i])q[++q[0]]=i;
	}


	for(int i=1;i<=n;++i)
	{
		x=q[i];
		printf("%d ",x);
		for(it=s[x].begin();it!=s[x].end();++it)
		{
						
			--pred[*it];
			if(pred[*it]==0)q[++q[0]]=*it;
				
		}
		
		
	}


			
	return 0;
}