Cod sursa(job #2660615)

Utilizator stanciucalinStanciu Calin stanciucalin Data 19 octombrie 2020 21:07:14
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

int n, m;
vector <int> * lv;

int * in_deg;

bool * removed;
queue <int> q;
vector <int> topological_order;

void topological_sort(){

    while(!q.empty()){

        int node = q.front();
        q.pop();
        removed[node] = 1;

        topological_order.push_back(node);

        for(int i = 0; i < lv[node].size(); i++){

            int next_node = lv[node][i];

            if(!removed[next_node]){

                in_deg[next_node] -= 1;

                if(!in_deg[next_node])
                    q.push(next_node);
            }
        }
    }
}

int main(){

    f >> n >> m;

    lv = new vector <int>[n + 1];
    in_deg = new int[n + 1];

    removed = new bool[n + 1];

    for(int i = 0; i <= n; i++){

        removed[i] = 0;
        in_deg[i] = 0;
    }

    int x, y;
    for(int i = 0; i < m; i++){

        f >> x >> y;
        lv[x].push_back(y);

        in_deg[y] += 1;
    }

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

    topological_sort();

    for(int i = 0; i < topological_order.size(); i++)
        g << topological_order[i] << " ";

    return 0;
}