Cod sursa(job #784189)

Utilizator f.v.antonFlavius Anton f.v.anton Data 5 septembrie 2012 01:13:21
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <list>
#include <queue>
#include <vector>

using namespace std;
char** read(fstream& f, int& n, int& m, vector<int> &deg)
{
	int i, val1, val2;
	char **a;

	f >> n >> m;
	deg.resize(n+1);

	a = new char*[n+1];

	for (i = 1; i <= n; i++)
		a[i] = new char[n+1];

	for (i = 0; i < m; i++) {
		f >> val1 >> val2;
		a[val1][val2] = 1;
		deg[val2]++;
	}
	return a;
}

list<int> toposort(char **a, int n, vector<int> deg)
{
	list<int> l;
	queue<int> q;
	int i, node;

	for (i = 1; i <= n; i++)
		if (deg[i] == 0)
			q.push(i);

	while (!q.empty()) {
		node = q.front();
		q.pop();
		l.push_back(node);

		for (i = 1; i <= n; i++)
			if (a[node][i] == 1) {
				a[node][i] = 0;
				deg[i]--;
				if (!deg[i])
					q.push(i);
			}
	}
	return l;
}

void print(fstream& g, list<int> l)
{
	while(!l.empty()) {
		g << l.front() << " ";
		l.pop_front();
	}
}

void discard(char **a, int n)
{
	int i;
	for (i = 0; i < n+1; i++)
		delete[] a[i];

	delete[] a;
}

int main(void)
{
	fstream f("sortaret.in", ios::in), g("sortaret.out", ios::out);
	int n, m;
	char **a;
	vector<int> deg;
	list<int> l;
	
	 a = read(f, n, m, deg);

	/*for(i = 1; i <= n; i++) {
		for(j = 1; j <= n; j++)
			cout << a[i][j] << " ";
		cout << endl;
	}*/

	l = toposort(a, n, deg);
	print(g, l);

	discard(a, n);

	f.close();
	g.close();

	return 0;
}