Cod sursa(job #630505)

Utilizator soriynSorin Rita soriyn Data 5 noiembrie 2011 17:40:42
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<cstdio>
#include<vector>
#include<stdlib.h>

#define maxn 50010

using  namespace std;
vector < int > A[maxn];
int grad[maxn],Q[maxn];
int n,m;

void read()
{
	freopen("sortaret.in","r",stdin);
	int a,b;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&a,&b);
		A[a].push_back(b);
		grad[b]++;
	}
}

void sortaret()
{
	int x;
	vector<int>::iterator it;
	for(int i=1;i<=n;i++)
		if(grad[i]==0) Q[++Q[0]]=i;
	for(int i=1;i<=n;i++)
	{
		x=Q[i];
	      for(it=A[x].begin();it!=A[x].end();it++)
		 {
					grad[*it]--;
					if(grad[*it]==0) Q[++Q[0]]=*it;
		  } 
	}
}	
		
void write()
{
	freopen("sortaret.out","w",stdout);
	for(int i=1;i<=n;i++)
		printf("%d ",Q[i]);
}

int main()
{
	read();
	sortaret();
	write();
	return 0;
}