Cod sursa(job #2335421)

Utilizator LucaSeriSeritan Luca LucaSeri Data 4 februarie 2019 08:09:35
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 10;

vector< int > gr[MAXN];
int deg[MAXN];

int main() {
	#ifdef BLAT
		freopen("input", "r", stdin);
	#else
		freopen("sortaret.in", "r", stdin);
		freopen("sortaret.out", "w", stdout);
	#endif

	int n, m;
	scanf("%d%d", &n, &m);

	for(int i = 0; i < m; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		gr[a].emplace_back(b);
		deg[b] ++;
	}

	queue< int > q;
	for(int i = 1; i <= n; ++i) if(!deg[i]) q.push(i);

	while(!q.empty()) {
		int node = q.front();
		q.pop();
		printf("%d ", node);
		for(auto &x : gr[node]) {
			deg[x] --;
			if(!deg[x]) q.push(x);
		}
	}
}