Cod sursa(job #792138)

Utilizator MtkMarianHagrSnaf MtkMarian Data 26 septembrie 2012 16:13:16
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <stdio.h>
#include<vector>
using namespace std; 
vector<int > v;

int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	int n,m,**a,x,y,*pred,**succ,nr=0;
	scanf("%d %d",&n,&m);
	pred=new int[n+1];
	
	vector<int >*s;
	s=new vector<int>[n+1];

	memset(&pred[0],0,(n+1)*sizeof(int));

//	for(int i=1;i<=n;++i)printf("%d ",pred[i]);

	

	a=new int*[n+2];
	for (int i=1;i<=n;++i)
		a[i]=new int[n+2];

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


	while(v.size()>=1)
	{
		x=v.front();
		printf("%d ",x);
		for(int i=0;i<s[x].size();++i)
		{
			y=s[x][i];				
			pred[y]-=1;
			if(pred[y]==0)v.push_back(y);
				
		}
		v.erase(v.begin());		
		
	}


			
	return 0;
}