Pagini recente » Cod sursa (job #1484551) | Cod sursa (job #2801627) | Cod sursa (job #2938542) | Cod sursa (job #1957238) | Cod sursa (job #499153)
Cod sursa(job #499153)
// http://infoarena.ro/problema/sortaret
#include <fstream>
#include <vector>
#include <list>
using namespace std;
int nodes,edges;
vector< list<int> > graph;
vector<bool> visit;
list<int> order;
void read();
void topologicalSort();
void depthFirst(int toVisit);
void write();
int main() {
read();
topologicalSort();
write();
return (0);
}
void read() {
ifstream in("sortaret.in");
int from,to;
in >> nodes >> edges;
graph.resize(nodes+1);
visit.resize(nodes+1);
for(int i=1;i<=edges;i++) {
in >> from >> to;
graph.at(from).push_back(to);
}
in.close();
}
void topologicalSort() {
for(int i=1;i<=nodes;i++)
if(!visit.at(i))
depthFirst(i);
}
void depthFirst(int toVisit) {
visit.at(toVisit) = true;
for(list<int>::iterator it=graph.at(toVisit).begin();it!=graph.at(toVisit).end();it++)
if(!visit.at(*it))
depthFirst(*it);
order.push_front(toVisit);
}
void write() {
ofstream out("sortaret.out");
for(list<int>::iterator it=order.begin();it!=order.end();it++)
out << *it << " ";
out << endl;
out.close();
}