Pagini recente » Cod sursa (job #3126016) | Cod sursa (job #2929733) | Cod sursa (job #2381054) | Cod sursa (job #2667790) | Cod sursa (job #1182812)
/// TOPOLOGICAL SORT
#include <fstream>
#include <vector>
#include <list>
using namespace std;
class Graph {
private:
vector<list<unsigned> > adjList; /// !!! pop the edge (adjList[from].pop_front()) if ready
vector<unsigned> numEdgesInto;
unsigned numNodes, numEdges;
public:
Graph(ifstream&);
list<unsigned> getTopSort();
};
Graph::Graph(ifstream& inStr) {
inStr >> numNodes >> numEdges;
adjList.resize(numNodes);
numEdgesInto.resize(numNodes, 0);
unsigned from, to;
for(unsigned i=0; i<numEdges; i++) {
inStr >> from >> to;
adjList[--from].push_back(--to);
numEdgesInto[to]++;
}
}
list<unsigned> Graph::getTopSort() {
list<unsigned> nodesInOrder;
list<unsigned> nodes;
for(unsigned i=0; i<numNodes; i++)
if(numEdgesInto[i] == 0)
nodes.push_back(i);
unsigned current;
list<unsigned>::iterator it;
while(!nodes.empty()) {
current = nodes.front();
nodes.pop_front();
nodesInOrder.push_back(current);
for(it = adjList[current].begin(); it != adjList[current].end(); it++) {
numEdgesInto[*it]--;
if(numEdgesInto[*it] == 0)
nodes.push_back(*it);
}
}
return nodesInOrder;
}
void printList(ofstream& outStr, list<unsigned>& l) {
list<unsigned>::iterator it;
for(it=l.begin(); it!=l.end(); it++)
outStr << *it+1 << ' ';
outStr << '\n';
}
int main() {
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
Graph graph(fin);
list<unsigned> l = graph.getTopSort();
printList(fout, l);
}