Cod sursa(job #2926412)

Utilizator RosianuRobertRosianu Robert RosianuRobert Data 17 octombrie 2022 19:11:52
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int n,x,y,i,j,m;
vector<int> rasp(10001);
vector<vector<int>> lista;
vector<int> grad(n+1,0);
queue<int> q;
void sortare_topologica()
{
                for (int i=1;i<=m;i++){
                    if (grad[i] == 0)
                        q.push(i);
                    while (q.size()) {
                        auto curr = q.front();
                        q.pop();
                        rasp.push_back(curr);
                        for (auto num: lista[curr]) {
                            if (--grad[num] == 0)
                                q.push(num);
                        }
                    }
                }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        lista[x].push_back(y);
        grad[y]++;
    }
sortare_topologica();
for(auto i : rasp)
    g<<i<< " ";
}