Cod sursa(job #2336517)

Utilizator Anime_LoverAnime Lover Anime_Lover Data 5 februarie 2019 10:46:08
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

vector <unsigned long> G[50060];
queue  <unsigned long> Q;

ifstream fi("sortaret.in");
ofstream fo("sortaret.out");

unsigned long deg[50060];

int main()
{
    unsigned long n,m;

    fi>>n>>m;

    for(unsigned long i=0;i<m;i++)
    {
        unsigned long x,y;
        fi>>x>>y;

        G[x].push_back(y);
        deg[y]++;
    }

    for(int i=1;i<=n;i++)
        if(!deg[i])
            Q.push(i);

    while(!Q.empty())
    {
        unsigned long nod=Q.front();
        Q.pop();

        fo<<nod<<" ";

        for(unsigned long i=0;i<G[nod].size();i++)
            {deg[G[nod][i]]--;
            if(!deg[G[nod][i]])
                Q.push(G[nod][i]);}
    }

    return 0;
}