Cod sursa(job #2018930)

Utilizator bcrisBianca Cristina bcris Data 6 septembrie 2017 13:37:39
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

#define NMAX 50100

vector<int> G[NMAX];
int Q[NMAX], IN_DEG[NMAX];

int main() {

	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);

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

	int a, b;
	for (int i = 1; i <= m; i++) {
		scanf("%d %d\n", &a, &b);
		G[a].push_back(b);
		IN_DEG[b]++;
	}

	for (int x = 1; x <= n; x++){
		if(IN_DEG[x] == 0) 
			Q[++Q[0]] = x;
	}

	int current;
	vector<int>::iterator it;
	for (int i = 1; i <= n; i++){
		current = Q[i];
		for (it = G[current].begin(); it != G[current].end(); ++it) {
			IN_DEG[*it]--;
			if (IN_DEG[*it] == 0) 
				Q[++Q[0]] = *it;
		}
	}

	for (int i = 1; i <=n; i++)
		printf("%d ", Q[i]);



	return 0;
}