Cod sursa(job #823728)

Utilizator horeste12Stoianovici Horatiu Andrei horeste12 Data 25 noiembrie 2012 16:26:55
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<deque>
#include<cstdio>
#include<malloc.h>

using namespace std;

void topologicalSort(int node, deque<int> *graf, int *visited, deque<int> &output);

int main()
{
	deque<int> *graf;
	deque<int> result;
	int *visited;
	int n, m;

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

	scanf("%d%d", &n, &m);
	graf = new deque<int>[n + 1];
	visited = (int *)calloc(n + 1, sizeof(int));

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

	topologicalSort(1, graf, visited, result);

	for(deque<int>::iterator i = result.begin(); i < result.end(); i++)
		printf("%d ", *i);
	puts("");

	return 0;
}

void topologicalSort(int node, deque<int> *graf, int *visited, deque<int> &output)
{
	visited[node] = 1;
	for(deque<int>::iterator i = graf[node].begin(); i < graf[node].end(); i++)
	{
		if(!visited[*i])
			topologicalSort(*i, graf, visited, output);
	}
	output.push_front(node);
}