Cod sursa(job #1170879)

Utilizator sorin2kSorin Nutu sorin2k Data 14 aprilie 2014 20:25:08
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector<int> adj[50000];
int n, m, grad[50000], sorted[50001];

void sortare_topologica() {
	int i, current;
	queue<int> next;
	for(i = 0; i < n; i++) {
		if(grad[i] == 0) {
			next.push(i);
		}
	}
	while(!next.empty()) {
		current = next.front();
		next.pop();
		sorted[++sorted[0]] = current;
		for(vector<int>::iterator it = adj[current].begin(); it != adj[current].end(); it++) {
			if(grad[*it] > 0) {
				grad[*it]--;
				if(grad[*it] == 0) next.push(*it);
			}
		}
	}
}

int main() {
	int i, u, v;
	fin >> n >> m;
	for(i = 0; i < m; i++) {
		fin >> u >> v;
		adj[u-1].push_back(v-1);
		grad[v-1]++;
	}
	sortare_topologica();
	for(i = 1; i <= sorted[0]; i++) {
		fout << sorted[i]+1 << " ";
	}
	return 0;
}