Cod sursa(job #144898)

Utilizator damaDamaschin Mihai dama Data 28 februarie 2008 08:49:48
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <stdio.h>
#include <vector>

using namespace std;


int n, m, cnt, sorted[50001], used[50001];
vector<int> v[50001];

void dfs(int);

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

	int i, a, b;

	scanf("%d %d", &n, &m);

	for(i = 1; i <= m; ++i)
	{
		scanf("%d %d", &a, &b);
		v[a].push_back(b);
	}

	for(i = 1; i <= n; ++i)
	{
		v[0].push_back(i);
	}
	cnt = n;
	dfs(0);

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

	return 0;
}

void dfs(int nod)
{
	int i, sz = v[nod].size();

	used[nod] = 1;

	for(i = 0; i < sz; ++i)
	{
		if(!used[v[nod][i]])
		{
			dfs(v[nod][i]);
		}
	}
	sorted[cnt] = nod;
	--cnt;
}