Cod sursa(job #1560762)

Utilizator geni950814Geni Geni geni950814 Data 3 ianuarie 2016 11:43:30
Problema Sortare topologica Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <vector>
#include <fstream>
#include <iostream>

using namespace std;

int N, M;

struct Node {
    int edges;
    vector<int> nextNodes;

    Node(int edges) {
        this->edges = edges;
    }

    void pushNext(int n) {
        nextNodes.push_back(n);
    }

    void incEdges() {
        this->edges++;
    }

    void decEdges() {
        this->edges--;
    }
};

int beginningNode(vector<Node>& nodes) {
    int e = -1;
    int i = 1;
    while(e != 0) {
        e = nodes[i].edges;
        i++;
    }
    return i-1;
}

ostream& operator<< (ostream& o, const Node& node) {
      o << "(" << node.edges << ", [";
      vector<int> list = node.nextNodes;
      for(int i = 0; i < list.size(); i++) {
          o << list[i] << " ";
      }
      
      return o << "])";
}

int main() {

    ifstream in("sortaret.in");
    ofstream out("sortaret.out");
    
    in >> N >> M;   
    int fst;
    int snd;

    vector<Node> nodes;
    for(int i = 0; i <= N; i++) {
        Node node(0);
        nodes.push_back(node);
    }

    for(int i = 0; i < M; i++) {
        in >> fst >> snd;
        nodes[fst].pushNext(snd);
        nodes[snd].incEdges();
    }
   
    for(int i = 0; i < N; i++) {
        int curr = beginningNode(nodes);
        nodes[curr].decEdges();
        out << curr << " ";
        vector<int> nexts = nodes[curr].nextNodes;
        for(int x : nexts) {
            nodes[x].decEdges();
        }
    }
        
    in.close();
    out.close();   

    return 0;
}