Cod sursa(job #480830)

Utilizator c_adelinaCristescu Adelina c_adelina Data 29 august 2010 18:58:48
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <cstdio>
#include <vector>
#include <deque>
#define pb push_back
#define f front
using namespace std;

vector <int> nod[50003];
deque <int> d;
int ok[50003];

int main()
{
	int n,m,i,a,b;
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (i=1;i<=m;++i)
	{scanf("%d %d",&a,&b);nod[a].pb(b);++ok[b];}
	for (i=1;i<=n;++i)
		if (!ok[i]) d.pb(i);
	while (!d.empty())
	{
		
		a=d.f();d.pop_front();
		printf("%d ",a);
		while (!nod[a].empty())
			{b=nod[a].back();
		     if (ok[b]==1)
				d.pb(b),ok[b]=0,nod[a].pop_back(); else
					--ok[b],nod[a].pop_back();
			}
	}
return 0;}