escalonamento_otimo.cpp

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define MAXN 50010
using namespace std;

int nodes,edges;
int grau[MAXN];
int marc[MAXN];
bool ciclo;
vector<int> myv[MAXN];
vector<int> resp;
priority_queue<int, vector<int>, greater<int> > heap;


void dfs(int x){
    marc[x] = 1;
    int l = myv[x].size();
    for(int i = 0;i<l;i++){
        if( marc[myv[x][i]] ) ciclo = 1;
        else dfs(myv[x][i]);
    }
    
}

int main(){
    
    scanf("%d %d",&nodes,&edges);
    
    memset(grau,0,sizeof grau);
    
    for(int i = 1;i<=edges;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        a++;
        b++;
        grau[b]++;
        myv[a].push_back(b);
        
    }
    
    for(int i = 1;i<=nodes;i++) if(!grau[i]) heap.push(i);
        
    int cont = 0;
    while( !heap.empty() ){
        
        cont++;
        int l = myv[heap.top()].size();
        int cara = heap.top();
        heap.pop();
        
        for(int i = 0; i < l; i++ ){
            grau[ myv[cara][i] ]--;
            if(!grau[myv[cara][i]]) heap.push(myv[cara][i]);
        }
        
        resp.push_back(cara);
        
    }
    
    if(cont < nodes) printf("*\n");
    else for(int i = 0;i<nodes;i++) printf("%d\n",resp[i]-1);
    
    return 0;
}