Cod sursa(job #2864835)

Utilizator newagear2Dragan Iulian newagear2 Data 8 martie 2022 11:44:38
Problema Sortare topologica Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int inDeg[50000];
int n,m;
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");
struct edge{
    int a,b;
};
queue<int> q;
vector<edge> edges;
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++){
        edge local;
        cin>>local.a>>local.b;
        inDeg[local.b]++;
        edges.push_back(local);
    }
    for(int i=1;i<=n;i++){
        //cout<<inDeg[i];
        if(inDeg[i]==0){
            q.push(i);
            //cout<<i;
        }
    }
    while(!q.empty()){
        for(auto it = edges.begin(); it != edges.end(); it++){
            if(it->a == q.front()){
                inDeg[it->b]--;
                if(inDeg[it->b]==0)q.push(it->b);
                edges.erase(it, it+1);
                it--;
            }
        }
        cout<<q.front()<<" ";
        q.pop();
    }
    
    return 0;
}