Cod sursa(job #1694018)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 24 aprilie 2016 15:52:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>

using namespace std;

class DirectedGraph {
    public:
    DirectedGraph(string filename) {
        ifstream fin(filename.c_str());
        int n, m;
        fin >> n >> m;
        this->vertices = n;
        this->edges = m;
        g.resize(n);
        while(m --) {
            int x, y;
            fin >> x >> y;
            -- x; -- y;
            g[x].push_back(y);
        }
    }
    vector <int> tsortQ() {
        queue <int> q;
        vector <int> deg(this->vertices, 0);
        for(int i = 0 ; i < this->vertices; ++ i) {
            for(auto it : g[i])
                ++ deg[it];
        }
        for(int i = 0 ; i < this->vertices ; ++ i)
            if(!deg[i])
                q.push(i);
        vector <int> ret;
        while(!q.empty()) {
            int node = q.front();
            ret.push_back(node);
            q.pop();
            for(auto it : g[node])
                if(--deg[it] == 0)
                    q.push(it);
        }
        return ret;
    }
    private:
    vector <vector <int> > g;
    int vertices, edges;
};

int main() {
    DirectedGraph g("sortaret.in");
    ofstream fout("sortaret.out");
    for(auto it : g.tsortQ())
        fout << it + 1 << ' ';
}