Cod sursa(job #873905)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 7 februarie 2013 19:02:48
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
#include <vector>
#include <cstdlib>
using namespace std;

struct nod
{
	int inf;
	nod *adr;
}*l;

bool v[50001];
vector<int> graf[50001];
int n, m;

void citire()
{
	freopen("sortaret.in", "r", stdin);
	int i, a, b;
	scanf("%d%d", &n, &m);
	for (i=0; i<m; ++i)
	{
		scanf("%d%d", &a, &b);
		graf[a].push_back(b);
	}
}

void add(int x)
{
	nod *p = (nod*)malloc(sizeof(nod));
	p->inf = x;
	p->adr = l;
	l = p;
}

void dfs(int nod)
{
	v[nod] = 1;
	int i, size = graf[nod].size();
	for (i=0; i<size; ++i)
		if (!v[graf[nod][i]])
			dfs(graf[nod][i]);
	add(nod);
}

void afisare()
{
	freopen("sortaret.out", "w", stdout);
	while (l)
	{
		printf("%d ", l->inf);
		l = l->adr;
	}
}

int main()
{
	citire();
	for (int i=1; i<=n; ++i)
		if (!v[i])
			dfs(i);
	afisare();
}