Cod sursa(job #2668383)

Utilizator BeraedBeraed Beraed Data 4 noiembrie 2020 20:33:46
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <vector>
	
using namespace std;
	
 
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
	
	
vector <int> nod[50005];
vector <int> lista;
int n, m, grad_intern[50005];
	
 
void citire(){
	
    fin>>n>>m;
    int x, y;
	
    for(int i=1;i<=m;i++){
	
        fin>>x>>y;
        grad_intern[y]++;
        nod[x].push_back(y);
	
    }
	
}
	
void rezolvare(){
	
    int n2=n;
	
    while(n2){
	
        for(int i=1;i<=n;i++){
	
            if(grad_intern[i]==0){
	
                grad_intern[i]=-1;
                lista.push_back(i);
                n2--;
	
                for(int j=0;j<nod[i].size();j++){
	
                    grad_intern[nod[i][j]]--;
	
                }
            }
        }
    }
}
	
void afisare(){
	
    for(int i=0;i<lista.size();i++)
        fout<<lista[i]<<' ';
	
}
	
int main(){
	
    citire();
    rezolvare();
    afisare();
	
}