Cod sursa(job #2254702)

Utilizator mister_adyAdrian Catana mister_ady Data 5 octombrie 2018 19:58:45
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<fstream>
#include<vector>
#include<queue>
#include<iostream>

#define MAXN 50001
#define MAXM 100001

using namespace std;

vector<int> graph[MAXN];
int outDegree[MAXN];
int toRemove[MAXN];

int main() {

	int N, M;
	
	ifstream in("sortaret.in");
	ofstream out("sortaret.out");
		
	in >> N >> M;
	
	for (int k = 1; k <= M; k++) {
		int i, j;
		in >> i >> j;
		graph[i].push_back(j);
		outDegree[j]++;
	}

	int count = 1;

	for (int i = 1; i <= N; i++) {
		if (outDegree[i] == 0) {
			toRemove[count] = i;
			count++;
		}
	}

	for (int i = 1; i <= N; i++) {
		int current = toRemove[i];
		
		for (int j = 0; j < graph[current].size(); j++) {
			int currNeigh = graph[current][j];
			outDegree[currNeigh]--;
			if (outDegree[currNeigh] == 0) {
				toRemove[count] = currNeigh;
				count++;
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		out << toRemove[i] << " ";
	}

	return 0;
}