Cod sursa(job #2926435)

Utilizator vladadAndries Vlad Andrei vladad Data 17 octombrie 2022 19:34:58
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
vector <int> edges[50001];
vector <int> visited;
int deg[50001];
queue <int> myQ;
vector <int> result;
int i,j,n,m;
void init()
{
    f>>n>>m;
    for(i=0;i<n+1;i++)
        visited.push_back(0);
    for(i=0;i<m;i++)
    {
        int x,y;
        f>>x>>y;
        edges[x].push_back(y);
        deg[y]++;
    }
    for(i=1;i<=n;i++)
        if(deg[i]==0)
            myQ.push(i);
    while(!myQ.empty())
    {

        int node = myQ.front();
        result.push_back(node);
        myQ.pop();
        for(auto neighbour:edges[node])
        {
            deg[neighbour]--;
            if(deg[neighbour]==0)
                myQ.push(neighbour);
        }
    }
}
int main()
{
    init();
    for(auto el: result)
        g<<el<<" ";
  return 0;
}