Cod sursa(job #1430965)

Utilizator muraru_georgeMuraru George Cristian 323CB muraru_george Data 8 mai 2015 22:27:24
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>
#include <iostream>
#include <list>
#include <vector>
#include <queue>

#define MAX 50000

using namespace std;

vector<list<int> > a_l;
vector<int> visited;
list<int> topo_sort;

void DFS(int node) {
	
	visited[node] = 1;

	list<int> l = a_l[node];
	for (list<int>::iterator it = l.begin(); it != l.end(); ++it)
		if (!visited[*it])
				DFS(*it);

	topo_sort.push_front(node);
}


int main(void) {
	
	int n, m;
	freopen("sortaret.in", "rt", stdin);
	freopen("sortaret.out", "wt", stdout);


	cin >> n >> m;
	int l, c;

	a_l.resize(n + 1);
	visited.resize(n + 1);

	for (int i = 0; i < m; ++i) {
		cin >> l >> c;
		a_l[l].push_back(c);
	}


	priority_queue<int> S;
	for (int i = 1; i <= n ; ++i) {
		if (!visited[i])
			DFS(i);
	}

	for (list<int>::iterator it = topo_sort.begin(); it != topo_sort.end(); ++it)
		cout << *it << " ";

}