Cod sursa(job #2969482)

Utilizator ViAlexVisan Alexandru ViAlex Data 23 ianuarie 2023 11:34:39
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.68 kb
#include<iostream>
#include<deque>
#include<algorithm>
#include<vector>
#include<fstream>
#include<queue>
using namespace std;

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

const int mx = 50001;

int n,m;
vector<int> g[mx];
vector<int> result,indeg;


void read(){
	in>>n>>m;
	indeg.resize(n+1,0);
	int a,b;
	for(int i=0;i<m;i++){
		in>>a>>b;
		g[a].push_back(b);
		indeg[b]++;
	}
}

void solve(){
	queue<int> q;

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

	while(!q.empty()){
		int here = q.front();
		out<<here<<" ";
		q.pop();
		for(int k:g[here]){
			indeg[k]--;
			if(indeg[k]==0){
				q.push(k);
			}
		}
	}
}

int main(){
	read();
	solve();

	return 0;
}