Cod sursa(job #2561390)

Utilizator LeperBearMicu Alexandru LeperBear Data 28 februarie 2020 19:24:46
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <vector>

#define MAXIM 50005

using namespace std;

int n,m,grext[MAXIM],viz[MAXIM],ord[MAXIM];
vector <int> G[MAXIM];

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

void citire(){
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        G[y].push_back(x); grext[x]++;
    }
}
void sortare(){
    int i;
    vector<int>::iterator iter;
    for (i=1;i<=n;i++)
        if (grext[i]==0 && G[i].size()>=1){ ord[++ord[0]]=i; cout<<i<<" ";}
    for (i=1;i<=n;i++){
        for (iter=G[ord[i]].begin();iter<G[ord[i]].end(); ++iter){
            grext[*iter]--;
            if (grext[*iter]==0){ ord[++ord[0]]=*iter; cout<<*iter<<" ";}
        }
    }
}

int main()
{
    citire();
    sortare();
    return 0;
}