Cod sursa(job #196600)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 27 iunie 2008 14:12:18
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <cstdio>
#include <vector>  
#define IN "sortaret.in"
#define OUT "sortaret.out"
#define N_MAX 1<<16
#define M_MAX 1<<17
#define pb push_back
#define FOR(i,a,b) for(int i=a;i<=b;++i)

using namespace std;
vector < vector <int> > a(N_MAX);

int n,m;
int sol[N_MAX],muchii[N_MAX];
bool viz[N_MAX];

void scan()
{
	int x,y;
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d%d\n", &n,&m);
	FOR(i,1,m)
		scanf("%d%d\n", &x,&y),
		++muchii[y],
		a[x].pb(y);
}

void solve()
{
	int x;
	FOR(i,1,n)
		if(!muchii[i])
			sol[++sol[0]]=i;
	FOR(i,1,n)
	{
		x=sol[i];
		int l=a[x].size();
		FOR(j,0,l-1)
		{
			if(muchii[a[x][j]])
				--muchii[a[x][j]];
			if(!muchii[a[x][j]])
				sol[++sol[0]]=a[x][j];
		}	
	}	
}

void print()
{
	FOR(i,1,n)
		printf("%d ",sol[i]);
}
		
int main()
{
	scan();
	solve();
	print();
	return 0;
}