Cod sursa(job #2211241)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 9 iunie 2018 16:57:32
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define MAXN 50005

using namespace std;

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

vector<int>graf[MAXN];
int stiva[MAXN],deg[MAXN],n,m;

void sortare_topologica(){
    int cnt = 0;
    for(int nod = 1; nod <= n; nod++)
        if(deg[nod] == 0)
            stiva[++cnt] = nod;

    for(int i = 1; i <= n; i++){
        int nod = stiva[i];

        for(int vecin = 0; vecin < graf[nod].size(); vecin++){
            int curent = graf[nod][vecin];

            deg[curent]--;
            if(deg[curent] == 0)
                stiva[++cnt] = curent;
        }
    }

}

int main()
{
    in>>n>>m;
    for(int i = 1; i <= n; i++){
        int nod,muchie;
        in>>nod>>muchie;
        graf[nod].push_back(muchie);
        deg[muchie]++;
    }

    sortare_topologica();
    for(int i = 1; i <= n; i++)
        out<<stiva[i]<<" ";
    return 0;
}