Cod sursa(job #1589744)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 4 februarie 2016 13:11:24
Problema Sortare topologica Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <vector>
#include <queue>

#define NMax 50010

using namespace std;

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

int nodes, edges, degIn[NMax];
vector<int> G[NMax];
queue<int> QU;

void updateDeg(int node)
{
	for (vector<int>::iterator it = G[node].begin(); it != G[node].end(); it++) {
		if (degIn[*it] > 0)
			degIn[*it]--;

		if (degIn[*it] == 0)
			QU.push(*it);
	}
}

int main()
{
	f >> nodes >> edges;

	int n1, n2;
	for (int i = 1; i <= nodes; i++) {
		for (int j = 1; j <= nodes; j++) {
			f >> n1 >> n2;

			G[n1].push_back(n2);
			degIn[n2]++;
		}
	}

	for (int i = 1; i <= nodes; i++)
		if (degIn[i] == 0)
			QU.push(i);

	while (!QU.empty()) {
		int crtNode = QU.front();
		QU.pop();

		g << crtNode << " ";
		updateDeg(crtNode);
	}

}