Cod sursa(job #1604520)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 18 februarie 2016 13:06:34
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

void sortaret(const vector<vector<int>>& graf, vector<int>& rez){
    const int n = graf.size();
    vector<int> in_deg(n, 0), de_viz;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < graf[i].size(); ++j){
            ++in_deg[graf[i][j]];
        }
    }
    for(int i = 0; i < n; ++i){
        if(in_deg[i] == 0){
            de_viz.push_back(i);
        }
    }
    while(!de_viz.empty()){
        const int cur = de_viz.back();
        rez.push_back(cur);
        de_viz.pop_back();
        for(int i = 0; i < graf[cur].size(); ++i){
            --in_deg[graf[cur][i]];
            if(in_deg[graf[cur][i]] == 0){
                de_viz.push_back(graf[cur][i]);
            }
        }
    }
}

int main()
{
    ifstream f("sortaret.in");
    ofstream g("sortaret.out");
    int n, m;
    f >> n >> m;
    vector<vector<int>> graf(n);
    for(int i = 0, a, b; i < m; ++i){
        f >> a >> b;
        --a, --b;
        graf[a].push_back(b);
    }
    vector<int> rez;
    sortaret(graf, rez);
    for(int i = 0; i < rez.size(); ++i){
        g << rez[i]+1 << ' ';
    }
    return 0;
}