Cod sursa(job #2039412)

Utilizator Alex18maiAlex Enache Alex18mai Data 14 octombrie 2017 15:39:50
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

/*ifstream cin ("input");
ofstream cout ("output");*/

ifstream cin ("sortaret.in");
ofstream cout ("sortaret.out");

vector < vector  < int > > gr (50100);
vector  < int > top (50100);
queue < int > Q;

void bfs(){
    while (!Q.empty()){
        int now = Q.front();
        Q.pop();
        for (auto &x : gr[now]){
            top[x]--;
            if (top[x] == 0){
                cout<<x<<" ";
                Q.push(x);
            }
        }
    }
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int nodes , edges;
    cin>>nodes>>edges;

    for (int i=1; i<=edges; i++){
        int a , b;
        cin>>a>>b;
        gr[a].push_back(b);
        top[b] ++;
    }

    for (int i=1; i<=nodes; i++){
        if (top[i] == 0){
            cout<<i<<" ";
            Q.push(i);
        }
    }

    bfs();

    return 0;
}