Cod sursa(job #2606500)

Utilizator RaduNichitaRadu Nichita RaduNichita Data 27 aprilie 2020 21:37:18
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.35 kb
#include <iostream>
	
#include <vector>
	
#include <fstream>
#include <queue>
	
using namespace std;
	
 
	
 
	
 
	
#define NMAX 100005
	
class Task {
	
    std::vector<int> matrix[NMAX];
    std::vector<bool> visited;
    std::vector<int> intern_degree;

	
    int N, M, S;
 
	
    void read_input() {
	
        std::ifstream in("sortaret.in");

        in >> N;
        in >> M;
        
        intern_degree = std::vector<int>(N + 1, 0);


        for (int i = 0; i < M; i++) {
	
            int x;
	
            int y;
	
            in >> x;
	
            in >> y;
            
         //   std::cout<<"y este"<<y<<"\n";
	
            matrix[x].push_back(y);
            intern_degree[y]++;
        }
	
        in.close();
	
    }
	
 
	
    void show_matrix() {
	
        for (int i = 0; i < N; i++) {
	
            std::cout<<i<<":";
	
            for (int j = 0; j < matrix[i].size(); j++) {
	
                std::cout<<matrix[i][j]<<" ";
	
            }
	
            std::cout<<"\n";
	
        }
	
    }

    void show_degree() {
        for (int i = 1; i <= N; i++) {
            std::cout<<"degree["<<i<<"] = "<<intern_degree[i]<<"\n";
        }
    }
	
 
    std::vector<int> topo() {
       // show_degree();
        std::vector<int> topological_order;
        std::queue<int> zero_degree_nodes;


        topological_order.push_back(0);

        for (int i = 1; i <= N; i++) {
            if (intern_degree[i] == 0) {
                zero_degree_nodes.push(i);
            }
        }

        while (!zero_degree_nodes.empty()) {
            auto x = zero_degree_nodes.front();
            zero_degree_nodes.pop();
            topological_order.push_back(x);
            for (auto const &elem : matrix[x]) {
                intern_degree[elem]--;
                if (intern_degree[elem] == 0) {
                    zero_degree_nodes.push(elem);
                }
            }
        }

        return topological_order;
    }
	
 
	
    void print(std::vector<int> topo) {
	
        std::ofstream out("sortaret.out");   
	

        for (int i = 1; i <= N; i++) {
           out<<topo[i]<<" ";
        }

        out<<"\n";
	
        out.close();
	
        return;
	
    }
	
 
	
 public:
	
    void solve() {
	
        read_input();
        print(topo());
	
    }
	
 
	
};
	
 
	
int main() {

    Task* task = new Task();
	
    task->solve();
	
    delete(task);
	
 
	
    return 0;
	
}