Pagini recente » Cod sursa (job #2160442) | Cod sursa (job #1049036) | Cod sursa (job #2077670) | Cod sursa (job #2470474) | Cod sursa (job #499151)
Cod sursa(job #499151)
// 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 depthFirst(int toVisit); // include sortarea topologica
void write();
int main() {
read();
for(int i=1;i<=nodes;i++)
if(!visit.at(i))
depthFirst(i);
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 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); // sortarea topologica
}
void write() {
ofstream out("sortaret.out");
for(list<int>::iterator it=order.begin();it!=order.end();it++)
out << *it << " ";
/*for(int i=1;i<=nodes;i++)
if(!visit.at(i))
out << i << " ";*/
//out << endl;
out.close();
}