Cod sursa(job #1112238)

Utilizator breta.ionutBreta Ionut breta.ionut Data 19 februarie 2014 16:38:32
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int main() {
	ifstream in("sortaret.in");
	ofstream out("sortaret.out");
	int n, m, *gr, i, x, y, *c, cl = 0;
	vector<int> *v;
	vector<int>::iterator it;

	in>>n>>m;
	gr = new int[n + 1];
	c = new int[n + 1];
	v = new vector<int>[n + 1];
	for (i = 1 ; i <= n ; i ++)
		gr[i] = 0;

	for (i = 0 ; i < m ; i ++) {
		in>>x>>y;
		gr[y]++;
		v[x].push_back(y);
	}

	for (i = 1 ; i <= n ; i ++)
		if (gr[i] == 0) {
			c[cl] = i;
			cl++;
		}

	i = 0;
	while (i < cl) {
		x = c[i];
		for (it = v[x].begin() ; it != v[x].end() ; it ++) {
			gr[*it] --;
			if (gr[*it] == 0) {
				c[cl] = *it;
				cl ++;
			}
		}
		i ++;
	}

	for (i = 0 ; i < cl ; i ++) {
		out<<c[i]<<" ";
	}

	in.close();
	out.close();

	return 0;
}