Cod sursa(job #2079575)

Utilizator ice_creamIce Cream ice_cream Data 1 decembrie 2017 16:01:10
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f ("sortaret.in");
ofstream g ("sortaret.out");

const int NMAX = 50000;

int n;
int grad[NMAX + 1];
vector <int> graf[NMAX + 1];

void citeste() {
	int m;
	f >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b;
		f >> a >> b;
		grad[b]++;
		graf[a].push_back(b);
	}
}

void rezolva() {
	queue <int> q;
	for (int i = 1; i <= n; i++)
		if (grad[i] == 0)
			q.push(i);

	while (!q.empty()) {
		int nod = q.front();
		q.pop();
		g << nod << ' ';

		int l = graf[nod].size();
		for (int i = 0; i < l; i++) {
			int fiu = graf[nod][i];
			grad[fiu]--;
			if (grad[fiu] == 0) q.push(fiu);
		}
	}
	g << '\n';
}

int main() {
	citeste();
	rezolva();
	return 0;
}