Cod sursa(job #1560908)

Utilizator geni950814Geni Geni geni950814 Data 3 ianuarie 2016 14:42:52
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.99 kb
#include <vector>
#include <fstream>
#include <iostream>
#include <set>
using namespace std;

int N, M;
set<int> initialNodes;

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

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

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

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

    void decEdges() {
        this->edges--;
        if(this->edges == 0) {
            initialNodes.insert(this->val);
        }
    }
};
/*
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++) {
        if(i != 0) {
            initialNodes.insert(i);
        }
        Node node(i);
        nodes.push_back(node);
    }

    for(int i = 0; i < M; i++) {
        in >> fst >> snd;
        nodes[fst].pushNext(snd);
        nodes[snd].incEdges();
        initialNodes.erase(snd);
    }
   
    for(int i = 0; i < N; i++) {
        vector<int> decEdgeNodes;
        for (set<int>::iterator it=initialNodes.begin(); it!=initialNodes.end(); ++it) { 
            int curr = *it;
            // initialNodes.erase(curr);
            out << curr << " ";
                 
            vector<int> nexts = nodes[curr].nextNodes;
            for(int x : nexts) {
                decEdgeNodes.push_back(x);
            }
        }
        initialNodes.clear();
        for(int x : decEdgeNodes) {
            nodes[x].decEdges();
        }
    }
        
    in.close();
    out.close();   

    return 0;
}