Cod sursa(job #2087325)

Utilizator Tyler_BMNIon Robert Gabriel Tyler_BMN Data 13 decembrie 2017 13:30:59
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <vector>
#include <queue>
#include <map>

using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

int n, m;
map<int, int> deg;
vector<int> G[50001];
queue<int> Q;
 

void read() {
	fin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y;
		fin >> x >> y;
		deg[y]++;
		G[x].push_back(y);
	}
}
void solve() {
	for (int x = 1; x <= n; x++) {
		if (deg[x] == 0) {
			Q.push(x);
			fout << x << " ";
		}
	}
	while (!Q.empty()) {
		int x = Q.front();
		for (int i : G[x]) {
			deg[i]--;
			if (deg[i] == 0) {
				Q.push(i);
				fout << i << " ";
			}
		}
		Q.pop();
	}
}

int main() {
	read();
	solve();
	return 0;
}