Cod sursa(job #903588)

Utilizator vld7Campeanu Vlad vld7 Data 1 martie 2013 23:00:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int MAX_N = 50005;

int n, m, v[MAX_N];
int IN[MAX_N];		// IN[x] = gradul interior al varfului x
vector <int> L[MAX_N];
queue <int> Q;

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

void solve() {
	for (int i = 1; i <= n; i++)
		if (IN[i] == 0)
			Q.push(i);
		
	while (!Q.empty()) {
		int nod = Q.front();	Q.pop();
		v[++v[0]] = nod;
		
		for (int i = 0; i < L[nod].size(); i++) {
			IN[L[nod][i]]--;
			if (IN[L[nod][i]] == 0)
				Q.push(L[nod][i]);
		}
	}
}

int main() {
	read();
	solve();
	
	for (int i = 1; i <= n; i++)
		g << v[i] << " ";
	
	f.close();
	g.close();
	
	return 0;
}