Cod sursa(job #2574699)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 6 martie 2020 09:00:48
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

int n, m;
vector<int> gra[50041];
int ingrad[50041];
void read(){
	fin >> n >> m;
	for(int i = 0; i < m; ++i){
		int a, b;
		fin >> a >> b;
		gra[a].push_back(b);
		ingrad[b]++;
	}
}

bool vi[50041];
queue<int> q;

void startitup(){
	for(int i = 1; i <= n; ++i){
		if(ingrad[i] == 0){
			q.push(i);
		}
	}
}

void topological(){
	startitup();
	while(!q.empty()){
		int a = q.front();q.pop();
		fout << a << " ";
		for(auto b : gra[a]){
			ingrad[b]--;
			if(ingrad[b] == 0){
				q.push(b);
			}
		}
	}
}

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