Cod sursa(job #1708741)

Utilizator liviu23Liviu Andrei liviu23 Data 27 mai 2016 21:24:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

struct nod {
    vector<int> succ;
    int grad;
};

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n,m;
nod noduri[50005];

void sortare_topologica() {
    queue<nod> coada;
    for(int i=1;i<=n;i++)
        if(noduri[i].grad==0) {
            coada.push(noduri[i]);
            fout<<i<<" ";
        }
    while(!coada.empty()) {
        nod curent=coada.front();
        for(int i=0;i<curent.succ.size();i++) {
            noduri[curent.succ[i]].grad--;
            if(noduri[curent.succ[i]].grad==0) {
                coada.push(noduri[curent.succ[i]]);
                fout<<curent.succ[i]<<" ";
            }
        }
        coada.pop();
    }
}

int main()
{
    fin>>n>>m;
    int a,b;
    for(int i=0;i<m;i++) {
        fin>>a>>b;
        noduri[a].succ.push_back(b);
        noduri[b].grad++;
    }
    sortare_topologica();
    return 0;
}