Cod sursa(job #402587)

Utilizator andrei.sfrentSfrent Andrei andrei.sfrent Data 23 februarie 2010 23:06:55
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <stdio.h>
#include <vector>

using namespace std;

#define N 50000
#define M 100000

vector<int> g[N + 1];
int n, m;
int gradExt[N + 1];
int l[N + 1];

void citesteGraf()
{
	scanf("%d%d", &n, &m);
	int i, x, y;
	for(i = 0; i < m; ++i)
	{
		scanf("%d%d", &x, &y);
		g[x].push_back(y);
		gradExt[y]++;
	}
}

void scrieListaSortata()
{
	int i;
	for(i = 1; i <= n; ++i ) printf("%d ", l[i]);
	printf("\n");
}

void sortareTopologica()
{
	int i;
	vector<int> :: iterator it;
	for(i = 1; i <= n; ++i) if(gradExt[i] == 0) l[++l[0]] = i;
	for(i = 1; i <= n; ++i)
	{
		for(it = g[l[i]].begin(); it != g[l[i]].end(); ++it)
		{
			if(gradExt[*it] >= 1) gradExt[*it]--;
			if(gradExt[*it] == 0) l[++l[0]] = *it;
		}
	}
}

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

	citesteGraf();
	sortareTopologica();
	scrieListaSortata();

	return 0;
}