Cod sursa(job #1111635)

Utilizator breta.ionutBreta Ionut breta.ionut Data 19 februarie 2014 00:13:28
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
using namespace std;

int main() {
	ifstream in("sortaret.in");
	ofstream out("sortaret.out");
	int n, m, **g, *c, i, j, x, y, cl = 0;

	in>>n>>m;
	g = new int*[n];
	c = new int[n];
	for (i = 0 ; i <= n ; i ++) {
		g[i] = new int[n];
		for (j = 0 ; j <= n ; j ++)
			g[i][j] = 0;
	}

	for (i = 0 ; i < m ; i ++) {
		in>>x>>y;
		g[x][y]++;
		g[0][y]++;
	}

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

	i = 0;
	while (i < cl) {
		x = c[i];
		for (j = 1 ; j <= n ; j ++)
			if (g[x][j] > 0) {
				g[x][j]--;
				g[0][j]--;
				if (g[0][j] == 0) {
					c[cl] = j;
					cl++;
				}
			}
		i++;
	}
	
	if (cl < n) {
		out<<0;

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

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

	return 0;
}