Cod sursa(job #2561407)

Utilizator LeperBearMicu Alexandru LeperBear Data 28 februarie 2020 19:32:01
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
//#include <iostream>
#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[x].push_back(y); grext[y]++;
    }
}

void scriere(){
    for (int i=1;i<=n;i++)
        cout<<ord[i]<<" ";
}

void sortare(){
    int i;
    vector<int>::iterator iter;
    for (i=1;i<=n;i++)
        if (grext[i]==0) ord[++ord[0]]=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;
        }
    }
}

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