Cod sursa(job #156465)

Utilizator snaked31Stanica Andrei snaked31 Data 12 martie 2008 16:14:46
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <deque>

using namespace std;

#define nm 50010
#define pb push_back
#define pf push_front

int n, m, i, x, y, j;
int ge[nm];
vector <int> v[nm];
deque <int> a;

void read()

{
	scanf("%d %d ", &n, &m);
	for (i=1; i<=m; ++i)
	{
		scanf("%d %d ", &x, &y);
		v[x].pb(y);
		++ge[y];
	}
}


void solve()

{
	for (i=1; i<=n; ++i)
		if (ge[i] == 0)
			a.pb(i);

	for (i=0; i<n; ++i)
	{
		for (j=0; j<v[a[i]].size(); ++j)
		{
			--ge[v[a[i]][j]];
			if (ge[v[a[i]][j]] == 0)
				a.pb(v[a[i]][j]);
		}
	}
}


void write()

{
	for (i=0; i<n; ++i)
	{
		printf("%d ", a[i]);
	}
}


int main()

{
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out","w",stdout);

	read();
	solve();
	write();

	return 0;
}