Cod sursa(job #2926301)

Utilizator mirceaspPetcu Mircea mirceasp Data 17 octombrie 2022 17:33:34
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int main() {
    int n,m,i,a,b;
    f>>n>>m;
    vector<vector<int>> lista;
    for(i = 1;i<=n;i++)
        lista.push_back({});
    map<int,int>indegres;
    for(i = 1;i<=n;i++)
        indegres[i] = 0;
    while (f>>a>>b)
    {
        lista[a].push_back(b);
        indegres[b] += 1;
    }
    queue<int> zeroIndegreeNodes;
    for(i = 1;i<=n;i++)
        if(indegres[i] == 0)
            zeroIndegreeNodes.push(i);
    vector<int>sol;
    while (!zeroIndegreeNodes.empty())
    {
        int front = zeroIndegreeNodes.front();
        sol.push_back(front);
        zeroIndegreeNodes.pop();
        for(i = 0;i<lista[front].size();i++) {
            indegres[lista[front][i]]--;
            if (indegres[lista[front][i]] == 0)
                zeroIndegreeNodes.push(lista[front][i]);
        }

    }
    for(auto i:sol)
        g<<i<<' ';

    return 0;
}